1.設計一個算法，把一個含有N個元素的數組循環右移K位，要求時間復雜度為O（N），
且只允許使用兩個附加變量。
方法一：
每次將數組中的元素右移一位，循環K次，則實現了右移K位。
例如，
原始字符串：abcd1234
右移一位：4abcd123
右移一位：34abcd12
右移一位：234abcd1
右移一位：1234abcd
循環4次，則實現了右移4次
實現函數如下：
void right_shift(char *str, int N, int K)
{
char temp;
K %= N; //目的是，當K > N時，移動K次與移動K-i*N次是一樣的。
while(K--)
{
t = str[N -1];
for(int i = N - 1; i > 0; i--)
str[i] = str[i - 1];
str[0] = t;
}
}
從上面的實現代碼可以看出，
由于K %= N， 所以while循環的K值是小于N的。所以時間復雜度最大為O(N^2), 空間復雜度為O(1)，不符合題目要求。
方法二：
對于原始字符串abcd1234，右移2位后為：34abcd12。
通過比較可以看出，有兩段子字符串的順序是不變的。abcd12和34。
則可發現，右移K位的過程就是把數組的兩部分交換的過程。
例如：abcd12|34.
對abcd12逆序排列：21dcba
對34逆序排列： 43
對全部的21dcba|43進行逆序排列：34abcd21.
得出如下結論：
將字符串S="abcd1234"分為兩部分X="abcd12"和Y="34"。那么S=(X, Y)
X逆序記為X'="21dcba"
Y逆序記為Y'="43"
則(X', Y')="21dcba43"整體再逆序為"34abcd12" = (Y, X)
即(X', Y')' = (Y, X)
代碼實現如下：
void reverse(char* str, int begin, int end)
{
char temp;
for( ; begin < end; begin++)
{
temp = str[end];
str[end] = str[begin];
str[begin] = temp;
}
}
void right_shift(char *str, int N, int K)
{
K %= N;
reverse(str, 0, N - K -1);
reverse(str, N - K, N - 1);
reverse(str, 0, N - 1);
}
該算法則實現了在線性時間內實現右移操作了。
編寫主函數測試如下：
#include <stdio.h>
#include <stdlib.h>
int main()
{
char str[] = "abcd1234";
printf("The initial string:%s\n", str);
right_shift(str, 8, 2);
printf("The string after right shift:%s\n", str);
system("pause");
return 0
}
2.實現對字符串進行左旋轉的函數，要求對長度為n的字符串操作的時間復雜度為O(n), 空間復雜度為O(1).例如，原始字符串：abcd1234，左旋轉2位后為：cd1234ab通過上面的1的分析，只是把右移改為左移。其他方法相同。代碼實現如下： void reverse(char* str, int begin, int end)
{
char temp;
for( ; begin < end; begin++)
{
temp = str[end];
str[end] = str[begin];
str[begin] = temp;
}
}
void right_shift(char *str, int N, int K)
{
K %= N;
reverse(str, 0, K -1);
reverse(str, K, N - 1);
reverse(str, 0, N - 1);
}
int main()
{
char str[] = "abcd1234";
printf("The initial string:%s\n", str);
right_shift(str, 8, 2);
printf("The string after right shift:%s\n", str);
system("pause");
return 0
}