首页 > 代码库 > 字符串循环移位
字符串循环移位
把字符串移动n位。可以一个一个移动,这样的话,要移动n次,每次移动len个。算法时间复杂度为O(n*len)。
也可以开辟一个新的内存,把移动的最终位置计算出来,直接放到那里即可,这样时间负责度为O(1),空间复杂度为O(len)。
除此之外,还有时间负责度为O(1),空间负责度也为O(1)的算法。
第二种方法是,先把前n个字符串反转,再把后面的反转。最后再把整个字符串反转
上面的移位都需要多次移位,有没有一种方法,一次性让移动的字符串到位。
看一下abcdefgh,左移3。我们可以一次计算出所有字符串最终的位置,移位即可。
把a保存起来,d移到a,g移到d,b移到g,e移到b,h移到e,c移到h,f移到c,a移到f,结束。
如果左移4呢,会出现死循环。这个与字符串长度和移位位数有关,要移动两者的最大公约数次数。
测试:
也可以开辟一个新的内存,把移动的最终位置计算出来,直接放到那里即可,这样时间负责度为O(1),空间复杂度为O(len)。
除此之外,还有时间负责度为O(1),空间负责度也为O(1)的算法。
第一种方法为把右边的向左移,每次移动n位。一直到末尾,再把末尾的反转好
//字符串左移n位 void shift(std::string &str, int n) { int len = str.length(); if (len <= 0) return; n = n%len; int start = 0;//交换起始位置 int end = n;//后面交换的起始位置 int mark = end;//记录这个位置 while (true) { while (start != mark&&end < len) { char temp = str[start]; str[start] = str[end]; str[end] = temp; ++start; ++end; //std::cout << str << std::endl; } if (start == mark) { if (end >= len) return; else mark = end;//更新mark } else if (end >= len) end = mark; } }
第二种方法是,先把前n个字符串反转,再把后面的反转。最后再把整个字符串反转
//反转[start end]之间字符串 void inversion(std::string& str, int start, int end) { char temp; while (start<end) { temp = str[start]; str[start] = str[end]; str[end] = temp; ++start; --end; } } void shift1(std::string& str, int n) { int len = str.length(); if (len <= 0) return; n = n%len; inversion(str, 0, n - 1);//反转前n半部分 inversion(str, n, len - 1);//反转后半部分 inversion(str, 0, len - 1);//整体反转 }
上面的移位都需要多次移位,有没有一种方法,一次性让移动的字符串到位。
看一下abcdefgh,左移3。我们可以一次计算出所有字符串最终的位置,移位即可。
把a保存起来,d移到a,g移到d,b移到g,e移到b,h移到e,c移到h,f移到c,a移到f,结束。
如果左移4呢,会出现死循环。这个与字符串长度和移位位数有关,要移动两者的最大公约数次数。
//计算公约数 int gcd(int max, int min) { if (min == 0) return max; return gcd(min, max%min); } void shift2(std::string& str, int n) { int len = str.length(); if (len <= 0) return; n = n%len; int GCD = gcd(len, n); int loop = len / GCD; for (int i = 0; i < GCD; ++i)//循环最大公约数次 { char temp = str[i]; int j; for (j = 0; j < loop - 1; ++j)//每次循环换loop个。 { str[(i + j*n) % len] = str[(i + j*n + n) %len ]; } str[(i + j*n) % len] = temp; } }
测试:
int main() { std::string str = "abcde"; shift(str, 3); std::cout << str << std::endl; shift1(str, 3); std::cout << str << std::endl; shift2(str, 3); std::cout << str << std::endl; return 0; }
字符串循环移位
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。