字符串循环左移
程序员文章站
2022-07-14 20:37:21
...
已经字符串adbcefg123,给定位置 i,例如i=3,将整个字符串循环左移i位,得到cefg123adb
请编写程序实现如上 字符串循环左移算法
[b]算法一:[/b]
1.将第0个字符移动到最后个位置,之后将字符串从后往前移动一个字符
2.重复步骤1 i次
3.打印出最后结果字符串
[b]时间复杂度分析[/b]: o(n*i) 如果i=n-1,则为o(n^2)
思考并改进算法:
改进版本一:
由这个 第j个位置的字符移动到 (j-i+len)%len 的位置 的想法,则可以通过调整n个元素的位置来达到循环左移的目的
[b]时间复杂度[/b];o(n)
请编写程序实现如上 字符串循环左移算法
[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)
上一篇: nginx+uwsgi+django多站点配置过程及注意事项
下一篇: MFC-进程间消息传递