给定一个字符串S[0…N-1]，要求把S的前K个字符移动到S的尾部，三种办法。

题目描述

给定一个字符串S[0…N-1]，要求把S的前K个字符移动到S的尾部
如把”abcdef“其前面的2个字符”ab“移动到字符串的尾部，得新字符串”cdefab“，即字符串循环左移K。

1
2
3
注意：
1. 循环左移K位等价于循环右移N-K位(可以自己举个例子理解，比如K=2，N=5)
2. 时间复杂度要求为0(n),空间复杂度位0(l)

办法：

  1. 暴力法：

    1
    2
    每次循环左移1位，调用K次即可
    - 时间复杂度:O(KN),空间复杂度0(l)

  2. 拷贝法：

    1
    2
    3
    4
    S[0...K]->T[0...K]
    S[K+1...N-1]->S[0...N-K-1]
    T[0...K]->S[N-K...N-1]
    - 时间复杂度0(N),空间复杂度0(K)

    可以看出，上面两种办法都没有办法同时符合条件，下面给出一种比较灵性的解法。

    1. 倒转法：

      1
      2
      3
      4
      5
      6
      7
       原理：（X‘Y’）‘=YX
       举个栗子:
       字符串:abcdef
       X=ab  X'=ba
       Y=cdef  Y'=fedc
      （X‘Y’）‘=(bafedc)'=cdefab
      - 时间复杂度:0(N),空间复杂度0(l)

      代码：

      前面那两个代码就不贴出来，主要贴第三个办法的
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      #include<iostream>
      using namespace std;

      //字符串反转函数
      void reverse(char *s,int start,int end)
      {
      char t;
              while(start<end)
              {
              t=s[start];
              s[start++]=s[end];
              s[end--]=t;
              }
      }

      int main()
      {
      	//将字符串前面两位移到末尾
              char arr[]="abcdef";
              reverse(arr,0,1);
              reverse(arr,2,5);
              reverse(arr,0,5);
              cout << arr;
      	return 0;
      }