首页 > 代码库 > 算法设计--字符串偏移

算法设计--字符串偏移

最近准备校招,找了些设计题练练,顺便记录。

问题描述:将字符串向右偏移给定的偏移量,如abcd,偏移量2,则得到cdab。

思路:第一感觉是和数组插入很像。

数组插入过程:n长数组在i位置插入元素ele,从n-1下标开始逆向迭代,覆盖其下一个元素

for(int it=n;it>i;it--){

arr[it]=arr[it-1];

}

arr[i]=ele;

so,整理下思路,Java实现如下:

private static void shift(String s,int  offset){//向右偏移
		StringBuffer str=new StringBuffer(s);
		int len=str.length(),num=len;
		char start=str.charAt(0);//腾出数据偏移余地,保存原始数据
		offset=offset%len;		 //防止offset大于len
		
		int i=0;
		char tmp;
		while(--num>0){//循环len-1次
			tmp=str.charAt((i-offset+len)%len);//边界控制
			str.setCharAt(i, tmp);//将n-offset位置的数据覆盖到n位置
			i=(i-offset+len)%len;
		}
		str.setCharAt(i, start);//给腾出空间的0位置的数据安排房间
		System.out.println(str.toString());
	}
空间基本无消耗,时间复杂度为O(n)。

算法设计--字符串偏移