162
劍指Offer詳解之左旋轉字符串
（1）暴力移位法
這種方法可能是最直觀，最容易想出的方法。但這也是最壞的方法。時間複雜度挺高，用這種方法容易超時。
這種方法是一位一位的移動實現左旋轉操作。
【代碼】
#include <stdio.h>
#include <malloc.h>
#include <string.h>
char *str;
char* Reverse(char* str,int n){
if(str == NULL || n < 0){
return "";
}
int len = strlen(str);
int i;
char temp;
//循環左移n位
while(n--){
//左移
//保存第一個字符
temp = str[0];
for(i = 1;i < len;i++){
str[i-1] = str[i];
}
str[len-1] = temp;
}
return str;
}
int main() {
int i,n;
str = (char*)malloc(sizeof(char)*1001);
while(scanf("%s",str) != EOF){
scanf("%d",&n);
//左旋轉
str = Reverse(str,n);
//輸出
for(i = 0;i < strlen(str);i++){
printf("%c",str[i]);
}
printf("\n");
}//while
return 0;
}
UDBOJ 4對上述字符串循環左移4次，8次，12次。。。。。(n % len )效果是一樣的
左移次數：n % len n原始左移次數 len字符串長度
【代碼】
char* Reverse(char* str,int n){
if(str == NULL || n < 0){
return "";
}
int len = strlen(str);
int i;
char temp;
//對左移次數進行優化
n = n % len;
//循環左移n位
while(n--){
//左移
//保存第一個字符
temp = str[0];
for(i = 1;i < len;i++){
str[i-1] = str[i];
}
str[len-1] = temp;
}
return str;
}
（2）指針翻轉法
咱們先來看個例子，如下：
abcdefghi，若要讓abc移動至最後的過程可以是：abcdefghi->defabcghi->defghiabc
如此，我們可定義倆指針，p1指向ch[0]，p2指向ch[m]；
一下過程循環m次，交換p1和p2所指元素，然後p1++, p2++；。
第一步，交換abc 和def ，abcdefghi->defabcghi
第二步，交換abc 和ghi，defabcghi->defghiabc
整個過程，看起來，就是abc作為一組一步一步向後移動
abcdefghi
defabcghi
defghiabc
//最後的 複雜度是O（m+n）
abcdefghi，若要讓abc移動至最後的過程可以是：abcdefghi->defabcghi->defghiabc
如此，我們可定義倆指針，p1指向ch[0]，p2指向ch[m]；
一下過程循環m次，交換p1和p2所指元素，然後p1++, p2++；。
第一步，交換abc 和def ，abcdefghi->defabcghi
第二步，交換abc 和ghi，defabcghi->defghiabc
整個過程，看起來，就是abc作為一組一步一步向後移動
abcdefghi
defabcghi
defghiabc
//最後的 複雜度是O（m+n）
由上述例子九個元素的序列abcdefghi，您已經看到，m=3時，p2恰好指到了數組最後一個元素，每m個一組正好一一對應。於是，上述思路沒有問題。但是每m個一組有剩餘時怎麼辦？假設abcde，還能如上麵的方法解決嗎？這樣就不可以了，那樣就數組越界了。所以我們要特殊處理尾部不夠m個一組的元素。
就舉這個例子，對abcdefghij序列進行左旋轉操作：
如果abcdefghij要變成defghijabc：
1. defabcghij
2. defghiabcj //最後一個j不夠一組m個要單獨處理
3. defghiabjc //我們需要一次一次交換移至前麵
4. defghiajbc
5. defghijabc
下麵，再針對上述過程，畫個圖清晰說明下，如下所示：
如果abcdefghij要變成defghijabc：
1. defabcghij
2. defghiabcj //最後一個j不夠一組m個要單獨處理
3. defghiabjc //我們需要一次一次交換移至前麵
4. defghiajbc
5. defghijabc
下麵，再針對上述過程，畫個圖清晰說明下，如下所示：
總結：
1、首先讓p1=ch[0]，p2=ch[m]，即讓p1，p2相隔m的距離，可以理解為每m個一組，第一組和後每組對應交換；
2、判斷p2+m-1是否越界，即判斷最後一組是不是構成一組。如果不能構成一組就不能一一對應交換，如果沒有越界轉到3，否則轉到4。
3、不斷交換*p1與*p2，然後p1++，p2++，循環m次，然後轉到2。
4、此時p2+m-1已經越界，即最後一組不能構成一組，不能一一對應交換，需處理尾巴。
過程如下：
4.1 通過n-p2得到p2與尾部之間元素個數r，即我們要前移的元素個數。
4.2 以下過程執行r次：
ch[p2]<->ch[p2-1]，ch[p2-1]<->ch[p2-2]，....，ch[p1+1]<->ch[p1]；p1++；p2++；
所以，之前最初的那個左旋轉九個元素abcdefghi的思路在末尾會出現問題的（如果p2後麵有元素就不能這麼變，例如，如果是處理十個元素，abcdefghij?對的，就是這個意思），解決方法：
def ghi abc jk
當p1指向a，p2指向j時，由於p2+m越界，那麼此時p1，p2不要變
這裏p1之後（abcjk)就是尾巴，處理尾巴隻需將j,k移到abc之前，得到最終序列，代碼編寫如下：
1、首先讓p1=ch[0]，p2=ch[m]，即讓p1，p2相隔m的距離，可以理解為每m個一組，第一組和後每組對應交換；
2、判斷p2+m-1是否越界，即判斷最後一組是不是構成一組。如果不能構成一組就不能一一對應交換，如果沒有越界轉到3，否則轉到4。
3、不斷交換*p1與*p2，然後p1++，p2++，循環m次，然後轉到2。
4、此時p2+m-1已經越界，即最後一組不能構成一組，不能一一對應交換，需處理尾巴。
過程如下：
4.1 通過n-p2得到p2與尾部之間元素個數r，即我們要前移的元素個數。
4.2 以下過程執行r次：
ch[p2]<->ch[p2-1]，ch[p2-1]<->ch[p2-2]，....，ch[p1+1]<->ch[p1]；p1++；p2++；
所以，之前最初的那個左旋轉九個元素abcdefghi的思路在末尾會出現問題的（如果p2後麵有元素就不能這麼變，例如，如果是處理十個元素，abcdefghij?對的，就是這個意思），解決方法：
def ghi abc jk
當p1指向a，p2指向j時，由於p2+m越界，那麼此時p1，p2不要變
這裏p1之後（abcjk)就是尾巴，處理尾巴隻需將j,k移到abc之前，得到最終序列，代碼編寫如下：
#include <stdio.h>
#include <malloc.h>
#include <string.h>
char *str;
void Reverse(char* str,int n){
if(str == NULL || n <= 0){
return;
}
int len = strlen(str);
int pre = 0;
int p = n;
char temp;
//len % n n個一組，不夠一組的個數
//len - n - len % n 表示總個數減去最前一組減去最後不夠一組的個數
//交換次數
int count = len - n - len % n;
while(count--){
//交換
temp = str[pre];
str[pre] = str[p];
str[p] = temp;
pre++;
p++;
}
//處理最後尾部不夠一組的元素
//rear為尾部左移元素個數
int rear = len - p;
while(rear--){
//左移
int i = p;
while(i > pre){
temp = str[i];
str[i] = str[i-1];
str[i-1] = temp;
i--;
}
p++;
pre++;
}
}
int main() {
int i,n;
str = (char*)malloc(sizeof(char)*1001);
while(scanf("%s",str) != EOF){
scanf("%d",&n);
//左旋轉
//注意一下n需要取餘就可以了，不能超過字符串自身的長度
n = n % strlen(str);
Reverse(str,n);
//輸出
for(i = 0;i < strlen(str);i++){
printf("%c",str[i]);
}
printf("\n");
}//while
return 0;
}
（3）三步翻轉法
/*********************************
* 日期：2013-12-02
* 作者：SJF0115
* 題號: 題目1362：左旋轉字符串（Move!Move!!Move!!!）
* 來源：https://ac.jobdu.com/problem.php?pid=1362
* 結果：AC
* 來源：劍指Offer
* 總結：
**********************************/
#include <stdio.h>
#include <malloc.h>
#include <string.h>
char *str;
//反轉單詞
void ReverseWord(char* words,int begin,int end){
int temp;
if(words == NULL || begin > end || begin < 0){
return;
}
//反轉
while(begin < end){
temp = words[begin];
words[begin] = words[end];
words[end] = temp;
begin ++;
end --;
}
}
char* Reverse(char* str,int n){
if(str == NULL || n < 0){
return "";
}
int len = strlen(str);
//分成兩部分（1）前n項（2）剩餘項
//反轉前n個
ReverseWord(str,0,n-1);
//反轉剩餘
ReverseWord(str,n,len-1);
//全部反轉
ReverseWord(str,0,len-1);
return str;
}
int main() {
int i,n;
str = (char*)malloc(sizeof(char)*1001);
while(scanf("%s",str) != EOF){
scanf("%d",&n);
//左旋轉
//注意一下n需要取餘就可以了，不能超過字符串自身的長度
n = n % strlen(str);
str = Reverse(str,n);
//輸出
for(i = 0;i < strlen(str);i++){
printf("%c",str[i]);
}
printf("\n");
}//while
return 0;
}
自己按自己思路有改動。
最後更新：2017-04-03 14:54:29