344. 反转字符串

使用双指针

541. 反转字符串 II

剑指 Offer 05. 替换空格

用双指针法可以不用额外空间
我的解法：

  1.     string replaceSpace(string s) {
  2.         string X;
  3.         for (int i = 0; i < s.size(); i++)
  4.         {
  5.             if (s[i] != ' ')
  6.                 X.push_back(s[i]);
  7.             else
  8.             {
  9.                 X.push_back('%');
  10.                 X.push_back('2');
  11.                 X.push_back('0');
  12.             }
  13.         }
  15.         return X;
  18.     }

151. 颠倒字符串中的单词

先去除头尾的空格，对字符串进行反转
再以空格为分界 对每个单词进行反转

剑指 Offer 58 - II. 左旋转字符串

我的：

  1.     string reverseLeftWords(string s, int n) {
  2.         vector<char> x;
  3.         int index,i;
  4.         for ( i = 0; i < n; i++)
  5.         {
  6.             x.emplace_back(s[i]);
  7.         }
  8.         for (index = 0; index + n < s.size(); index++)
  9.         {
  10.             s[index] = s[index + n];
  11.         }
  12.         for (i=0; index < s.size(); index++)
  13.         {
  14.             s[index] = x[i++];
  15.         }
  16.         return s;
  17.     }

参考：不申请额外空间

  1. class Solution {
  2. public:
  3.     string reverseLeftWords(string s, int n) {
  4.         reverse(s.begin(), s.begin() + n);
  5.         reverse(s.begin() + n, s.end());
  6.         reverse(s.begin(), s.end());
  7.         return s;
  8.     }
  9. };

KMP算法

由来：由这三位学者发明的：Knuth，Morris和Pratt，所以取了三位学者名字的首字母。所以叫做KMP
用途：KMP主要应用在字符串匹配上。
KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
用法：
image.png
求出模式串的前缀表 ，确定回退到的位置
前缀表求法：

  1.     vector<int> getNext(string s){
  2.         int len = static_cast<int> (s.size());
  3.         vector<int> next(len,0);
  4.         int i;
  5.         int j = 0;
  6.         for (i = 1; i < s.length(); i++){
  7.             while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作
  8.                 j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
  9.             }
  10.             if (s[i] == s[j]) {
  11.                 j++;
  12.             }
  13.             next[i] = j;
  14.         }
  15.         return next;
  16.     }

kmp算法：

  1.     int strStr(string haystack, string needle) {
  2.         if (needle.size() == 0)
  3.             return 0;
  4.         int len1, len2;
  5.         len1 = haystack.size();
  6.         len2 = needle.size();
  7.         int i, j;
  8.         vector<int> next;
  9.         next = getNext(needle);
  10.         j = 0;
  11.         for (i = 0; i < len1; i++){
  12.             cout << haystack[i] << " " << needle[j] << endl;
  14.             while (j > 0 && haystack[i] != needle[j]) {
  15.                 j = next[j - 1];
  16.             }
  17.             if (haystack[i] == needle[j]) {
  18.                 j++;
  19.             }
  20.             if (j ==len2 ) {
  21.                 return (i - len2 + 1);
  22.             }
  23.         }
  24.         return -1;
  25.     }

题目：

28. 实现 strStr()

459. 重复的子字符串

如果一个字符串可以由字字符串组成
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。