字符串

作者: FifiZhuang | 来源:发表于2017-07-05 11:23 被阅读0次

    字符串循环左移问题

    • 1 问题描述:给定一个字符串S[0...N-1],要求把S的前k个字符移到S的尾部,如把S的字符串“abcded"前面的前两个字符“a”,“b”移到字符串的尾部,得到新字符串“cdefab”,即字符串循环左移2位。
    • 2 算法要求:时间复杂度为O(n),空间复杂度为O(1)。
    • 3 解题思路:三次翻转字符串解法比暴力求解复杂度小,
      假设

    X='ab'
    Y='cdef '
    X ' = 'ba'
    Y ' = ' fedc '
    ( X ' Y ' ) ' = ' cdefab

    • 4 代码
      #include<stdio.h>
      void reverseString(char s, int from , int to)
      {
      while(from<to)
      {
      char t = s[from];
      s[from++] = s[to];
      s[to--] = t;
      }
      }
      void leftRotateString(char
      s, int n, int m)
      {
      m %= n;
      reverseString(s,0,m-1);
      reverseString(s,m,n-1);
      reverseString(s,0,n-1);
      }
      int main()
      {
      char str[] = "abcdef";
      printf("The string:%s\n", str);
      leftRotateString(str, 6, 2);
      printf("After left shift:%s\n", str);
      return 0;
      }
    • 5 该问题可作为完美洗牌算法的子算法,未完待续......

    相关文章

      网友评论

          本文标题:字符串

          本文链接:https://www.haomeiwen.com/subject/khofhxtx.html