欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

字符串循环左移

程序员文章站 2022-07-14 20:37:21
...
已经字符串adbcefg123,给定位置 i,例如i=3,将整个字符串循环左移i位,得到cefg123adb


请编写程序实现如上 字符串循环左移算法

[b]算法一:[/b]
1.将第0个字符移动到最后个位置,之后将字符串从后往前移动一个字符
2.重复步骤1 i次
3.打印出最后结果字符串


/**
* 字符串循环左移
* @param i
* @param source
* @return
*/
public String loopLeftShift(int i, String source)
{

if (source == null) {
return null;
}

int len = source.length();

if (i <= 0 || i >= len) {
return null;
}
StringBuilder sb = new StringBuilder(source);
for (int j = 0; j < i; j++) {
int begin=0;
int end=len-1;
char beginChar=sb.charAt(begin);
while (end > 0) {
beginChar= swap(end,beginChar,sb);
end =end-1;
}

swap(0,beginChar,sb);

}

return sb.toString();
}




[b]时间复杂度分析[/b]: o(n*i) 如果i=n-1,则为o(n^2)


思考并改进算法:

改进版本一:
由这个 第j个位置的字符移动到 (j-i+len)%len 的位置 的想法,则可以通过调整n个元素的位置来达到循环左移的目的


/**
* 循环左移动实现方法二
* @param i
* @param source
* @return
*/
public String loopLeftShift2(int i,String source)
{


if (source == null) {
return null;
}

int len = source.length();

if (i <= 0 || i >= len) {
return null;
}
StringBuilder sb = new StringBuilder(source);

//第j位直接移动 (j-i+len)%len 位
int next =0;
int begin=next;
char beginChar=sb.charAt(begin);

int count =0;

while(true)
{
next=(next-i+len)%len;
beginChar=this.swap(next,beginChar,sb);
count++;
if(count ==len){
break;
}
//解环
if(next ==begin){
next =next+1;
begin =next;
beginChar=sb.charAt(begin);
}

}
return sb.toString();
}


[b]时间复杂度[/b];o(n)
相关标签: 算法