样例:
字符串“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 ;
}