算法学习之字符串左移和右移

我会带着你远行 2022-08-14 03:41 192阅读 0赞

http://www.blogjava.net/guiying/archive/2012/08/08/385097.html

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)

代码实现如下：

该算法则实现了在线性时间内实现右移操作了。

编写主函数测试如下：

\#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  
\}