面试题之O(n)内旋转字符串

样例:

字符串“abcd1234"左移3位结果为”234abcd1“

K:左移位数

L:字符串长度

方案1:暴力 O(K * L)

可以每次将数组中的元素左移一位,循环K次。

abcd1234  ->4abcd123 ->34abcd12->234abcd1

算法复杂度为O(K * L)

方案2:暴力+公式变形 O(N^2)

大家开始可能会有这样的潜在假设,K<L。事实上,很多时候也的确是这样的。但严格来说,我们不能用这样的“惯性思维”来思考问题。尤其在编程的时候,全面地考虑问题是很重要的,K可能是一个远大于L的整数,在这个时候,上面的解法是需要改进的。仔细观察循环左移的特点,不难发现:每个元素左移L位后都会回到自己的位置上。因此,如果K > L,左移K-L之后的数组序列跟左移K位的结果是一样的,进而可得出一条通用的规律:
左移K位之后的情形,跟左移K= K % N位之后的情形一样

方案三:巧妙三次翻转 0(N)算法:

三次翻转操作:

第一次:  adcd1变成1dcba

第二次:  234变成432

两此翻转之后结果是:1dcba432

第三次:  然后将得到的结果整体再翻转一次:234abcd1

注意:如果左移位数K大于字符串长度L,那么左移K位和左移K%L结果是一样的

code:

#include <bits/stdc++.h>
using namespace std;
void f(char str[],int x,int y)
{
for(;x<y;x++,y--)
{
char temp=str[y];
str[y]=str[x];
str[x]=temp;
}
}
int main()
{
char str[]={'a','b','c','d','','','',''};
int k=;//左移3位 即234abcd1
int l=; if(k>l)
k=k%l;//如果k>l 那么左移k位和左移k%l位结果是一样的 f(str,,l-k-);
cout<<str<<endl; f(str,l-k,l-);
cout<<str<<endl; f(str,,l-);
cout<<str<<endl; return ;
}
上一篇:ubuntu升级php版本


下一篇:jQuery中eq()方法用法实例