替换空格

先把字符串长度扩充，然后利用双指针，这样就不需要额外空间了

双指针翻转字符串

https://leetcode-cn.com/problems/reverse-words-in-a-string/

  1. class Solution {
  2. public:
  3.     string reverseWords(string s) {
  4.         reverse(s.begin(),s.end());
  5.         int index = -1;
  6.         for(int i=0;i<s.length();i++) {
  7. //                cout<<"-----"<<index<<' '<<i<<' '<<s<<endl;
  8.             while(i<s.length() && s[i]==' ') i++;
  9.             int l = i;
  10.             while(i<s.length() && s[i]!=' ') i++;
  11.             l = i-l;
  12.             if(l==0) continue;
  13.             index++;
  14.             reverse(s.begin()+index,s.begin()+i);
  15.             index += l;
  16. //        cout<<"+++++"<<index<<' '<<i<<' '<<s<<endl;
  17.         }
  18.         s.resize(index);
  19.         return s;
  20.     }
  21. };

字符串匹配-KMP

算法思想：当字符串不匹配时，利用之前一部分已经匹配的内容，避免再从头匹配。
next数组：是一个前缀表，表示i（包括i）之前最长相等的前后缀长度，这个数值可能会是应该跳到的下标-1
其他内容可以参考我写的博客https://blog.csdn.net/qq_38140099/article/details/78661127
这里给出《算法导论》中的代码，更容易理解，时间复杂度相同的

  1. class Solution {
  2. public:
  3.     void getNext(int* next, const string& s) {
  4.         int k=-1;
  5.         next[0]=k;
  6.         for(int i=1;i<s.length();i++) {// 注意i从1开始
  7.             while(k>=0 && s[i]!=s[k+1]) k = next[k];
  8.             if(s[i]==s[k+1]) {
  9.                 k++;
  10.             }
  11.             next[i] = k;
  12.         }
  13.     }
  14.     int strStr(string haystack, string needle) {
  15.         if(needle.length()==0) return 0;
  16.         int next[needle.length()];
  17.         getNext(next, needle);
  18.         int j=-1;// 因为next数组里记录的起始位置为-1
  19.         for(int i=0;i<haystack.length();i++) {
  20.             while(j>=0 && haystack[i]!=needle[j+1]) j=next[j];
  21.             if(haystack[i]==needle[j+1]) j++;
  22.             if(j+1 == needle.length()) return i-j;
  23.         }
  24.         return -1;
  25.     }
  26. };

字符串转整数

int res = atoi(str.c_str());