旋轉(zhuǎn)字符串
題目描述：
給定一個(gè)字符串柱锹，要求把字符串前面的若干個(gè)字符移動(dòng)到字符串的尾部，如把字符串“abcdef”前面的2個(gè)字符'a'和'b'移動(dòng)到字符串的尾部丰包，使得原字符串變成字符串“cdefab”禁熏。請(qǐng)寫一個(gè)函數(shù)完成此功能，要求對(duì)長(zhǎng)度為n的字符串操作的時(shí)間復(fù)雜度為 O(n)邑彪，空間復(fù)雜度為 O(1)瞧毙。
分析和解法：
解法一：暴力位移法
首先，我看到題目的第一個(gè)想法就是可以通過暴力一位一位的挪移來(lái)實(shí)現(xiàn)題目要求寄症。
源代碼如下：
#include <iostream>
#include <cstring>
using namespace std;
void LeftShiftOne(char* s, int n) //完成當(dāng)前字符串的第一個(gè)字符到尾部
{
char t = s[0]; //保存當(dāng)前字符串的第一個(gè)字符
for (int i = 1; i < n; i++)
{
s[i - 1] = s[i];
}
s[n - 1] = t;
}
int main()
{
char str[100];
int m;
cin.getline(str,100); //用于輸入一行字符串宙彪，普通cin最多輸入“ abcd”
cin>>m;
while(m--)
{
LeftShiftOne(str, strlen(str));
}
cout<<str<<endl;
return 0;
}
分析：針對(duì)長(zhǎng)度為n的字符串來(lái)說(shuō)，假設(shè)需要移動(dòng)m個(gè)字符到字符串的尾部有巧，那么總共需要 m*n 次操作释漆，同時(shí)設(shè)立一個(gè)變量保存第一個(gè)字符，如此篮迎，時(shí)間復(fù)雜度為O(m * n)男图，空間復(fù)雜度為O(1)示姿，空間復(fù)雜度符合題目要求，但時(shí)間復(fù)雜度不符合逊笆，所以栈戳，得需要尋找其他更好的辦法來(lái)降低時(shí)間復(fù)雜度。
解法二：三步反轉(zhuǎn)法
（這個(gè)方法是我從書上學(xué)到的难裆，我一開始也沒想到子檀。。差牛。）
將一個(gè)字符串分成X和Y兩個(gè)部分命锄，在每部分字符串上定義反轉(zhuǎn)操作，如XT偏化，即把X的所有字符反轉(zhuǎn)（如脐恩，X="abc"，那么XT="cba"）侦讨，那么就得到下面的結(jié)論：(XTYT)^T=YX驶冒，顯然就解決了字符串的反轉(zhuǎn)問題。
例如韵卤，字符串 abcdef 骗污，若要讓def翻轉(zhuǎn)到abc的前頭，只要按照下述3個(gè)步驟操作即可：
- 首先將原字符串分為兩個(gè)部分沈条，即X:abc需忿，Y:def；
- 將X反轉(zhuǎn)蜡歹，X->XT屋厘，即得：abc->cba；將Y反轉(zhuǎn)月而，Y->YT汗洒，即得：def->fed。
- 反轉(zhuǎn)上述步驟得到的結(jié)果字符串XTYT父款，即反轉(zhuǎn)字符串cbafed的兩部分（cba和fed）給予反轉(zhuǎn)溢谤，cbafed得到defabc，形式化表示為(XTYT)^T=YX憨攒，這就實(shí)現(xiàn)了整個(gè)反轉(zhuǎn)世杀。
源代碼如下：
#include <iostream>
#include <cstring>
using namespace std;
void MyReverse(char* s, int from, int to) //自身反轉(zhuǎn)
{
while(from < to)
{
char t = s[from];
s[from++] = s[to];
s[to--] = t;
}
}
int main()
{
char str[100];
int n,m;
cin.getline(str, 100);
cin>>m;
n = strlen(str);
MyReverse(str, 0, m-1);
MyReverse(str, m, n-1);
MyReverse(str, 0, n-1);
cout<<str<<endl;
return 0;
}
分析：這就是把字符串分為兩個(gè)部分，先各自反轉(zhuǎn)再整體反轉(zhuǎn)的方法肝集，時(shí)間復(fù)雜度為O(n)玫坛，空間復(fù)雜度為O(1)，達(dá)到了題目的要求包晰。
特別注意：
- <string.h>是舊的C 頭文件湿镀，對(duì)應(yīng)的是基于char*的字符串處理函數(shù)，并無(wú)類伐憾，所以不能 string s1
- <cstring>是對(duì)應(yīng)于舊C 頭文件的std 版本勉痴，實(shí)際上只是在一個(gè)命名空間std中include了 <string.h>
- <string>是包裝了std 的C++頭文件，對(duì)應(yīng)的是新的string 類树肃，string s1就是建立一個(gè)string類的對(duì)象
- 漢字之所以亂碼蒸矛， 是因?yàn)闈h字是多字節(jié)的， 如果采用單字節(jié)翻轉(zhuǎn)胸嘴，必然就亂碼了雏掠。你需要判斷漢字是幾個(gè)字節(jié)（N）， 然后整體翻轉(zhuǎn)移動(dòng)這N個(gè)字節(jié)
- 這里我還想說(shuō)明一下關(guān)于C++輸入輸出流的問題劣像，有興趣的可以看一下C/C++輸入輸出流總結(jié)
參考資料：《編程之法》The Art of Programming By July
