首页 > 代码库 > 左旋转字符串

左旋转字符串

题目描述:

定义字符串左旋转操作:把字符串前面的若干个字符移动到字符串尾部,如把字符串 abcdef 左旋转 2 位得到字符串 cdefab。请实现字符串左旋转的函数,要求对长度为 n 的字符串操作的时间复杂度为 O(n),空间复杂度为 O(1)。


解法一:暴力移位法

此方法就是将需要移动的字符串逐个移动到大字符串的末尾

移动一个字符(java方法)

	/**
	 * <p>
	 * 暴力移动,逐条移动法
	 * </p>
	 * @author zhangjunshuai
	 * @date 2014-5-13 下午4:43:37
	 * @param shift
	 * @return
	 * @throws Exception
	 */
	public static String[] volenceShift(String[] shift) throws Exception{
		
				String inite= shift[0];
				for(int i=0;i<shift.length-1;i++){
					shift[i] = shift[i+1];
				}
				shift[shift.length-1]= inite;
			
		
		
		return shift;
	}

如果需要移动多位时

for(int j=0;j<3;j++){
			inite = volenceShift(inite);
			for(int h=0;h<inite.length;h++)
				System.out.print(inite[h]);
			System.out.println();
		}

解法二:对称反转法

如字符串:abcdef,我们想移动abc到def之后,我们可以将abc做对称反转变成cba,def变成fed,整个字符串变成cbafed,反向读取则为defabc

/**
	 * 
	 * <p>
	 * 对称位移法
	 * </p>
	 * @author zhangjunshuai
	 * @date 2014-5-14 上午9:27:11
	 * @param s
	 * @param from
	 * @param to
	 * @return
	 */
	public static String[] exchange(String[] s,int from,int to){
		
		while(from<to){//使用此while判断,较好的解决了
			String temp = s[from];
			s[from++] = s[to];
			s[to--] = temp;
			
		}
		return s;
	}

调用此方法

public static void main(String[] args) throws Exception{
		
		
		//测试对称位移法
		String[] initeexchange ="a,b,c,d,e,f,g".split(",");
		
		initeexchange = exchange(initeexchange,0,2);
		initeexchange = exchange(initeexchange,3,initeexchange.length-1);
		for(int h=initeexchange.length-1;h>=0;h--)
			System.out.print(initeexchange[h]);
	}

PS:

本文是本人在学习http://taop.marchtea.com/  是的个人实践,算法思想来源于此地址,转载请注明