leetcode-字符串

1.反转字符串LeetCode344. 20230911

难度为0，此处就不放代码了

1. 注意reverse和swap等一系列字符串函数什么时候该用，记一记库函数

• swap可以有两种实现，涨知识了，除了temp存值还可以通过位运算：s[i] ^= s[j]; s[j] ^= s[i]; s[i] ^= s[j];

• 2.反转字符串LeetCode541. 20230917

  这一题做的时候其实有点奇怪，想了好多方法都被自己否掉，然后看题解发现for里面i+=2k才恍然大悟，又看到reverse里面用了s.begin()+i这个用法，这才明白为啥本题本来很简洁被我写得那么复杂

  这个题在今天再重拾的时候觉得完全不用自己想，就按部就班地按着题意写就行了

  然后看到还有一个reverse的用法是reverse(s,i,i+k),第一个而是字符串，第二个和第三个是一个左闭右开的区间

  

  3.替换空格 剑指Offer 05. 20230917

  自己做的：开了一个string，if else地一个个字符加进去了。

  卡尔说的：可以先用resize函数将s先变长到最终的长度，然后用双指针法一个一个从后往前填字符。但是在写的时候犯了一个很蠢的错误，resize之后的长度已经变了，我还在用s.length()表示旧的，s.length()+ 2 *num 表示新的。下面是正确的代码。

  class Solution {
  public:string replaceSpace(string s) {int spacenum = 0;for(char i : s){if(i == ' ') spacenum++;}int size = s.length();int left = size - 1;s.resize(s.length() + 2*spacenum);      for(int right = size + 2*spacenum - 1; right > 0; right--){if(s[left] != ' '){s[right] = s[left];left--;}else{s[right] = '0';s[right - 1] = '2';s[right - 2] = '%';left--;right -= 2;}}return s;}
  };

  4.翻转字符串里的单词 LeetCode 151. 20230919-10/03

  思路还是蛮简单，就是写的时候老转不过弯。

  1. split函数似乎可以实现分割string里面的单词，不过C++里好像没有

  2. 学习了一下erase函数（没用到）：C++标准库中的erase函数通常用于从容器（例如std::vector、std::string、std::list等）中删除元素，例如

  std::vector<int> myVector = {1, 2, 3, 4, 5}; // 删除第三个元素（索引为2） myVector.erase(myVector.begin() + 2);

  std::string myString = "Hello, World!"; // 删除从索引6开始的5个字符 myString.erase(6, 5);

  std::vector<int> myVector = {1, 2, 3, 4, 5, 6}; // 删除第二个到第四个元素 myVector.erase(myVector.begin() + 1, myVector.begin() + 4);

  然而，erase背后的实现是O(N)的时间复杂度，如果外面再套一个for循环就是O(N²)的复杂度。

  3. 本题写的代码，显示自己定义一个闭区间倒置函数，然后经过两次倒转就可以。里面细节非常多，什么时候+1，什么时候到末尾要判断，什么时候-1，都很凌乱

  class Solution {
  public:void m_reverse(string &s, int a, int b){for(int i = 0; i < (b - a + 1)/2; ++i){swap(s[a + i], s[b - i]); }}string reverseWords(string s) {//去除空格int fast = 0, slow = 0;while(fast < s.length()){if(s[fast] != ' ')s[slow++] = s[fast++];else if(slow != 0){while(s[fast] ==' ' && fast < s.length()){fast++;}if(fast != s.length())s[slow++] =' ';}else{fast++;}}s.resize(slow);//全倒reverse(s.begin(),s.end());//闭区间m_reversefor(int i = 0, j = 0; i < s.length(); ++i){while(s[i] != ' ' && i < s.length())++i;m_reverse(s, j, i - 1);cout<<i<<" "<<j<<endl;cout<<s<<endl;j = i + 1;}return s;}
  };

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

  简单的做法就是使用substr函数，注意substr的第二个参数是“多长”而不是“到哪”。

  string substr1 = s.substr(0, n);
  s = s.substr(n, s.length() - n)+ substr1;
  return s;

  然后还有原地旋转的思路：

  先局部反转，再整体反转，很妙

          reverse(s.begin(), s.begin() + n);reverse(s.begin() + n, s.end());reverse(s.begin(), s.end());

  里面两个注意点:

  一个是reverse()里面的两个参数：

  • 首先，std::vector<int> vec = {1, 2, 3, 4, 5}; auto it = vec.begin() + 2; // it指向第三个元素，即3 std::cout << *it << std::endl; // 输出 3 因为vec.begin()指向第一个元素，也即vec.begin()+0，那么+2就是指向第三个元素
• 其次，如果是reverse(vec.begin(), vec.begin() + 2);要记住reverse的第一个参数是第一个元素，第二个参数是最后一个元素的下一个元素。也即，虽然begin()指的是1，begin()+2指的是3，但是反转的是1,2此处反转成为{2,1,3,4,5}

• 另一个是reverse、substr的内部实现，及它们的时间复杂度

  为什么要看内部实现，因为做题的时候会想着要把时间复杂度降低，但是使用库函数有的时候就会忽略掉本身这个函数自己实现的时候用的时间复杂度，所以在这里简单看一下

  reverse: 源码实现是while ((first!=last)&&(first!=--last)) { std::iter_swap (first,last); ++first; }，也就是只遍历一遍即可，而swap是之前讲过的，要么是疑惑，要么是temp存，总之是用temp和数组定位。最终合起来的结果也就是遍历一遍，对每个元素O(1)的时间复杂度，最后是O(N)。

  substr: 实现思路为创建一个新的字符串对象，将原始字符串中的子字符串复制到新的字符串中。复制的时间复杂度与子字符串的长度成正比，因此是 O(N)。

  6.找出字符串中第一个匹配项的下标-KMP LeetCode28. 20231019

  KMP居然是简单题吗，好吧

  将近一个月没写。

  这道题连着看了得有好几天了，但是依然不太会。今天终于约摸着把next数组和利用next数组进行匹配的代码写出来了，但是其实还是没有完全理解。

  class Solution {
  public:
  int strStr(string haystack, string needle) {
  //next数组
  int length = needle.length();
  int next[length];
  next[0] = 0;// 
  int j = 0;// 前缀末尾
  // 求next数组
  for(int i = 1; i < length; ++i){
  while(j > 0 && needle[i] != needle[j]){
  j = next[j-1];
  }
  if(needle[i]==needle[j]){
  j++;
  }
  next[i] = j;
  }
  int n = 0;
  //用next数组去做匹配
  for(int m = 0; m < haystack.length(); ++m){   
  while(n > 0 && haystack[m] != needle[n])
  n = next[n-1];      
  if(haystack[m] == needle[n])
  n++;
  if(n == length)
  return m - length + 1;
  }
  return -1;
  }
  };

  ---

  aabaa前缀（不带末尾）：针对a为空；针对aa为a；针对aab为a，aa；针对aaba为a，aa，aab；针对aabaa为a,aa,aab,aaba

  后缀（不带头）：针对a为空；针对aa为a；针对aab为b，ab；针对aaba为a，ba，aba;针对aabaa为a,aa,baa,abaa

  ---

  首先是求next数组。

  1）初始化的时候，next数组第一个必为0，这是因为位置0前后缀不可能相等（后缀位置0没有）。

  2）然后开始从i=1挨个填next数组，在填这个数组的时候就已经用到了kmp思想了。具体表现为填next[i]的时候，j也不是一直从头开始匹配的。j先为0，如果needle串s的s[i]!=s[j],此时说明j要往前移动，但是只移到next[j-1]那边（注意点：while、>0）；如果needle串的s[i]==s[j]，就j++;然后，next[i]=j，进行到next[i+1]。

  然后是利用next数组进行匹配。

  这个地方也就是遍历haystack串，与模式串匹配就两个指针都自动后移，不匹配就模式串的指针往前移（依旧是while、>0注意），然后这个地方还有一个根据题意返回一下结果。

  这个题让我自己想是完全不可能想出来的，感觉以后还得复习三遍才能记住

  7. 重复的子字符串 LeetCode 459. 20231019

  第一种解法的思想是两个s拼接起来如果去头去尾还含有s，那么s是可以由重复子串构成的。

  理解：

  [xx {xxxx][xx} xxxx] 如果{xxxxxx}=[xxxxxx]，证明[xx={xx；{xx=xx]；xx]=[xx}；而[xx}=[xx，所以

  [xx={xx=xx]=[xx}，所以xx为[xxxxxx]可用来重复的子串。大概这么理解吧，不再看严格数学证明。

  里面有两个亮点：erase函数删除特定位置的元素，以及string::npos代表没找到任何位置。

  class Solution {
  public:bool repeatedSubstringPattern(string s) {//方法1.移动匹配--具体表现为拼接-删除首尾-调用find库函数string ss = s+s;ss.erase(ss.length()-1,1);ss.erase(0,1);auto it = ss.find(s);if (it != string::npos)return 1;return 0;}
  };

  第二种解法是KMP，

  class Solution {
  public:bool repeatedSubstringPattern(string s) {//方法2.KMP--两个思路中的关键数学证明//1. 如果是由子串重复构成，那么最长相等前后缀不包含的那个子串就是所要求的子串。//2. 如果子串整除整个串，那么整个串就是由这个子串重复构成的。这个依然看我关于[xx {xxxx][xx} xxxx] 的理解，总而言之各个部分都相等。//下面，首先是算next数组，我们需要知道next[s.length()-1]等于多少，因为这个值就代表我们整个串的相等前后缀有多长。然后，用s.length()-next[s.length()-1] 除 s.length(), 如果能整除，就返回1，否则返回0。int length = s.size();//int next[length]={0};int next[s.length()];next[0] = 0;int j = 0;for (int i = 1; i < length; ++i){while(j > 0 && s[j]!=s[i])j = next[j-1];if(s[j]== s[i])j++;next[i] = j;}if(next[length-1] != 0 && (length % (length - next[length-1]) == 0))return 1;return 0;}
  };

  注1: next[length-1] != 0 要加，漏了完全没有相等前后缀的情形。

  注2:int next[s.length()];这种用法很奇怪，按本科讲的课来说应该写成int *next = new int[s.length()];才行。

  leetcode的奇怪机制：
  ·参数是(string s)，在函数体内定义一个数组int array[s.length()];可以过
  ·int array[s.length()]={0};过不了
  ·int array[s.length()]; for (int i = 0; i < s.length(); ++i) {array[i] = 0;}又能过

  其他：LeetCode刷题总结-字符串篇 - 舞动的心 - 博客园 (cnblogs.com) （还有什么题可刷）待看