344. 反转字符串

https://leetcode-cn.com/problems/reverse-string/

  • 双指针
    1.  public void reverseString(char[] s) {
    2.       int L = 0;
    3.       int R = s.length - 1;
    4.       while (L < R) {
    5.           char tmp = s[L];
    6.           s[L++] = s[R];
    7.           s[R--] = tmp;
    8.       }
    9.   }

541. 反转字符串Ⅱ

https://leetcode-cn.com/problems/reverse-string-ii/
这道题目其实也是模拟，实现题目中规定的反转规则就可以了。
一些同学可能为了处理逻辑：每隔2k个字符的前k的字符，写了一堆逻辑代码或者再搞一个计数器，来统计2k，再统计前k个字符。
其实在遍历字符串的过程中，只要让 i += (2 k)，i 每次移动 2 k 就可以了，然后判断是否需要有反转的区间。
因为要找的也就是每2 k 区间的起点，这样写，程序会高效很多。
*所以当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章。

  1.  public String reverseStr(String s, int k) {
  2.         char[] ch = s.toCharArray();
  3.         for (int i = 0; i < ch.length; i += 2 * k) {
  4.             // 1. 每隔 2k 个字符的前 k 个字符进行反转
  5.             // 2. 剩余字符小于2k但是大于或等于k个， 则反转前k个字符
  6.             if (i + k <= ch.length) {
  7.                 reverse(ch, i, i + k - 1);
  8.                 continue;
  9.             }
  10.             // 3. 剩余字符少于k个， 则将剩余字符全部反转
  11.             reverse(ch, i, ch.length - 1);
  12.         }
  13.         return new String(ch);
  14.     }
  16.     public void reverse(char[] chs, int begin, int end) {
  17.         int L = begin;
  18.         int R = end;
  19.         while (L < R) {
  20.             char tmp = chs[L];
  21.             chs[L++] = chs[R];
  22.             chs[R--] = tmp;
  23.         }
  24.     }

剑指Offer 05. 替换空格

https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

  • 法一： StringBuilder ```csharp public String replaceSpace1(String s) {
    1.   StringBuilder sb = new StringBuilder();
    2.   for (int i = 0; i < s.length(); i++) {
    3.       if (s.charAt(i) == ' ') {
    4.           sb.append("%20");
    5.       } else {
    6.           sb.append(s.charAt(i));
    7.       }
    8.   }
    9.   return sb.toString();
    }
  2. - 法二： 先扩容 再双指针
  4. 【来源：代码随想录】<br />如果想把这道题目做到极致，就不要只用额外的辅助空间了！<br />首先扩充数组到每个空格替换成"%20"之后的大小。<br />然后从后向前替换空格，也就是双指针法，过程如下：<br />i指向新长度的末尾，j指向旧长度的末尾。<br />![](https://cdn.nlark.com/yuque/0/2022/gif/2817263/1642471032070-b896cfd1-d969-44bc-85ee-27b9727c58d2.gif#clientId=ud94e42f6-1b19-4&crop=0&crop=0&crop=1&crop=1&from=paste&id=u46d5f212&margin=%5Bobject%20Object%5D&originHeight=346&originWidth=498&originalType=url&ratio=1&rotation=0&showTitle=false&status=done&style=none&taskId=u8b04ce54-d206-4191-8634-79b51059385&title=)<br />有同学问了，为什么要从后向前填充，从前向后填充不行么？<br />从前向后填充就是$O(n^2)$的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。<br />**其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。**<br />这么做有两个好处：
  6. 1. 不用申请新数组。
  7. 1. 从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。
  8. ```csharp
  9.  // 法二： 先扩容 再双指针
  10.     public String replaceSpace2(String s) {
  11.         char[] chs = s.toCharArray();
  12.         int count = 0; // 统计空格个数
  13.         int oldLen = chs.length;
  14.         for (char ch : chs) {
  15.             if (ch == ' ') {
  16.                 count++;
  17.             }
  18.         }
  19.         // 扩容
  20.         int newLen = oldLen + count * 2;
  21.         char[] str = new char[newLen];
  22.         for (int i = 0; i < oldLen; i++) {
  23.             str[i] = chs[i];
  24.         }
  25.         for (int i = newLen - 1, j = oldLen - 1; j < i; i--, j--) {
  26.             if (str[j] != ' ') {
  27.                 str[i] = str[j];
  28.             } else {
  29.                 str[i] = '0';
  30.                 str[i - 1] = '2';
  31.                 str[i - 2] = '%';
  32.                 i -= 2;
  33.             }
  34.         }
  35.         return new String(str);
  37.     }

151. 翻转字符串里的单词

https://leetcode-cn.com/problems/reverse-words-in-a-string/
这道题目可以说是综合考察了字符串的多种操作。
本题的难度：不要使用辅助空间，空间复杂度要求为$O(1)$。
不能使用辅助空间之后，那么只能在原字符串上下功夫了。
想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。
所以解题思路如下：

  • 移除多余空格
  • 将整个字符串反转
  • 将每个单词反转

举个例子，源字符串为：”the sky is blue “

  • 移除多余空格 : “the sky is blue”
  • 字符串反转：”eulb si yks eht”
  • 单词反转：”blue is sky the”

这样我们就完成了翻转字符串里的单词。

  1.  public String reverseWords(String s) {
  2.         if (s == null || s.length() == 0) {
  3.             return null;
  4.         }
  5.         if (s.equals(" ")) {
  6.             return " ";
  7.         }
  8.         char[] str = s.toCharArray();
  9.         int len = removeExtraSpaces(str);
  10.         reverse(str, 0, len - 1);
  12.         for (int i = 0; i < len; ) {
  13.             int j = i;
  14.             while (j < len && str[j] != ' ') {
  15.                 j++;
  16.             }
  17.             reverse(str, i, j - 1);
  18.             i = j + 1;
  19.         }
  20.         return new String(str, 0, len);
  21.     }
  23.     // 反转字符串s中左闭又闭的区间[start, end]
  24.     public void reverse(char[] s, int start, int end) {
  25.         int L = start;
  26.         int R = end;
  27.         while (L < R) {
  28.             char tmp = s[L];
  29.             s[L++] = s[R];
  30.             s[R--] = tmp;
  31.         }
  32.     }
  34.     // 移除冗余空格： 使用双指针 （快慢指针）
  35.     // 返回对应的有效长度
  36.     public int removeExtraSpaces(char[] str) {
  37.         int N = str.length;
  38.         int slow = 0;
  39.         int fast = 0;
  40.         // 去掉字符串前面的空格
  41.         while (fast < N && str[fast] == ' ') {
  42.             fast++;
  43.         }
  45.         for (; fast < N; fast++) {
  46.             // 去掉字符串中间部分的冗余空格
  47.             if (str[fast] == ' ' && str[fast] == str[fast - 1]) {
  48.                 continue;
  49.             } else {
  50.                 str[slow++] = str[fast];
  51.             }
  52.         }
  55.         if (str[slow - 1] == ' ') {
  56.             return slow - 1;
  57.         } else {
  58.             return slow;
  59.         }
  60.     }

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

不能申请额外空间，只能在本串上操作。
不能使用额外空间的话，模拟在本串操作要实现左旋转字符串的功能还是有点困难的。

这道题目依然可以通过局部反转+整体反转 达到左旋转的目的。
具体步骤为：

  1. 反转区间为前n的子串
  2. 反转区间为n到末尾的子串
  3. 反转整个字符串

最后就可以得到左旋n的目的，而不用定义新的字符串，完全在本串上操作。
例如 ：示例1中 输入：字符串abcdefg，n=
截图_20223718113716.png
截图_20223718113727.png

  1.  //额外空间复杂度O(1)
  2.     public String reverseLeftWords2(String s, int n) {
  3.         int len = s.length();
  4.         StringBuilder sb = new StringBuilder(s);
  5.         // 1. 反转区间为前n的子串
  6.         reverse(sb, 0, n - 1);
  7.         // 2. 反转区间为n到末尾的子串
  8.         reverse(sb, n, len - 1);
  9.         // 3. 反转整个字符串
  10.         reverse(sb, 0, len - 1);
  11.         return sb.toString();
  12.     }
  14.     public void reverse(StringBuilder sb, int start, int end) {
  15.         while (start < end) {
  16.             char tmp = sb.charAt(start);
  17.             sb.setCharAt(start++, sb.charAt(end));
  18.             sb.setCharAt(end--, tmp);
  20.         }
  21.     }

6. 实现strStr() （KMP）

https://leetcode-cn.com/problems/implement-strstr/

  • kmp算法见如下链接

https://www.yuque.com/docs/share/c0e96027-62d0-411b-abc1-c3e053609458?# 《27.⭐实现strStr() （KMP算法）》

  1.    // KMP算法
  2.     public int strStr(String haystack, String needle) {
  3.         if (haystack == null || needle == null || needle.length() > haystack.length()) {
  4.             return -1;
  5.         }
  6.         if (needle.length() == 0) {
  7.             return 0;
  8.         }
  10.         char[] str = haystack.toCharArray();
  11.         char[] match = needle.toCharArray();
  12.         int[] next = getNextArray(match);
  13.         int x = 0;
  14.         int y = 0;
  15.         while (x < str.length && y < match.length) {
  16.             if (str[x] == match[y]) {
  17.                 x++;
  18.                 y++;
  19.             } else if (next[y] == -1) { // y跳到0位置了
  20.                 x++;
  21.             } else {
  22.                 y = next[y];
  23.             }
  24.         }
  25.         /*  y不越界， x越界， -1
  26.          *  y越界， x不越界
  27.          *  y越界， x越界
  28.          * */
  29.         return y == match.length ? x - y : -1;
  30.     }
  32.     private int[] getNextArray(char[] match) {
  33.         if (match.length == 1) {
  34.             return new int[]{-1};
  35.         }
  36.         int[] next = new int[match.length];
  37.         next[0] = -1;
  38.         next[1] = 0;
  39.         int i = 2;
  40.         int cn = 0;
  41.         while (i < match.length) {
  42.             if (match[cn] == match[i - 1]) {
  43.                 next[i++] = ++cn;
  44.             } else if (cn > 0) {
  45.                 cn = next[cn];
  46.             } else {
  47.                 next[i++] = 0;
  48.             }
  49.         }
  50.         return next;
  51.     }

459. 重复的子字符串

  • 同样用到kmp

https://leetcode-cn.com/problems/repeated-substring-pattern/
如果len % (len - (next[len - 1] + 1)) == 0 ，则说明 (数组长度-最长相等前后缀的长度) 正好可以被 数组的长度整除，说明有该字符串有重复的子字符串

数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
强烈建议大家把next数组打印出来，看看next数组里的规律，有助于理解KMP算法

  1.  public static boolean repeatedSubstringPattern(String s) {
  2.         int len = s.length();
  3.         char[] str = s.toCharArray();
  4.         int[] next = getNextArray(str);
  5.         int i = next[len - 1];
  6.         if (i < 0) {
  7.             return false;
  8.         } else {
  9.             if (str[i] == str[len - 1] && len % (len - (next[len - 1] + 1)) == 0) {
  10.                 return true;
  11.             }
  12.         }
  13.         return false;
  14.     }
  18.     private static int[] getNextArray(char[] match) {
  19.         if (match.length == 1) {
  20.             return new int[]{-1};
  21.         }
  22.         int[] next = new int[match.length];
  23.         next[0] = -1;
  24.         next[1] = 0;
  25.         int i = 2;
  26.         int cn = 0;
  27.         while (i < match.length) {
  28.             if (match[cn] == match[i - 1]) {
  29.                 next[i++] = ++cn;
  30.             } else if (cn > 0) {
  31.                 cn = next[cn];
  32.             } else {
  33.                 next[i++] = 0;
  34.             }
  35.         }
  36.         return next;
  37.     }