:::tips 作者：LemonCat🐱
时间：2023-8-2 :::

第四章字符串part01

:::info

344.反转字符串
1. 反转字符串II
剑指Offer 05.替换空格
151.翻转字符串里的单词
剑指Offer58-II.左旋转字符串 :::

344.反转字符串

:::tips 建议：本题是字符串基础题目，就是考察 reverse 函数的实现，同时也明确一下
平时刷题什么时候用库函数，什么时候不用库函数
题目链接：力扣 344. 反转字符串
文章讲解/视频讲解：代码随想录 :::

方法 - 经典双指针

在反转链表（LC 206.反转链表）中，使用了双指针的方法。
那么反转字符串依然是使用双指针的方法，只不过对于字符串的反转，其实要比链表简单一些。
因为字符串也是一种数组，所以元素在内存中是连续分布，而链表在内存中不是连续分布的，这就决定了反转链表和反转字符串方式上还是有所差异的。
对于字符串，我们定义两个指针（也可以说是索引下标）
1. 一个从字符串前面 - left
2. 一个从字符串后面 - right
3. 两个指针同时向中间移动，并交换元素。

以字符串hello为例，过程如下：
代码随想录 | 第四章 - 字符串 - 图1

/**
 * 方法 - 经典双指针
 */
class Solution555 {
    public void reverseString(char[] s) {
        int left = 0; // 左指针
        int right = s.length-1; // 右指针
        int i = 0; // 索引
        char tempC;
        // 反转字符 - 当 left < right
        while (left < right) {
            tempC = s[left];
            s[left++] = s[right];
            s[right--] = tempC;
        }
    }
}

优化 - 位运算交换

参考资料：位运算（&、|、^、~、>>、 | 菜鸟教程

我们采用位运算来完成交换
- ^ -> 两个位相同为0，相异为1
- ^ -> 自反性: a^b^b=a^0=a; ```java /**

双指针 - 位运算交换优化 */ class Solution { public void reverseString(char[] s) {

  int left = 0; // 左指针
  int right = s.length - 1; // 右指针
  // 位运算
  while (left < right) {
      s[left] ^= s[right];  //构造 a ^ b 的结果，并放在 a 中
      s[right] ^= s[left];  //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
      s[left] ^= s[right];  //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
      left++;
      right--;
  }

} } ```

541. 反转字符串II

:::tips 建议：本题又进阶了，自己先去独立做一做，然后在看题解，对代码技巧会有很深的体会。
题目链接：力扣 541. 反转字符串 II
文章讲解/视频讲解：代码随想录 :::

方法 - 双指针

思路基本与 344.反转字符串保持一致 -> 核心都是双指针
每隔2k个反转前k个
1. 尾数大于等于 k 时只反转前 k 个
2. 尾数不够 k 个时候全部反转

其实只需在遍历字符串的过程中

让 i += (2 k)，i 每次移动 2 k 就可以了 -> for (int i = 0; i < sChar.length; i += 2 * k)
然后判断是否需要有反转的区间

这样就会使得代码更加简洁

class Solution {
public String reverseStr(String s, int k) {
  char[] sChar = s.toCharArray();
  for (int i = 0; i < sChar.length; i += 2 * k) {
      int left; // 左指针
      int right; // 右指针
      // 进行判断结尾剩余情况
      // 给出合适的 左右指针
      if (sChar.length - i < k) { // 当结尾个数小于 k 时
          left = i; 
          right = sChar.length - 1; 
      } else { // 当结尾个数大于等于 k 时
          left = i;
          right = left + k - 1; 
      }
      // 位运算进行交换
      while (left < right) {
          sChar[left] ^= sChar[right];  //构造 a ^ b 的结果，并放在 a 中
          sChar[right] ^= sChar[left];  //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
          sChar[left] ^= sChar[right];  //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
          left++;
          right--;
      }
  }
  return new String(sChar);
}
}

时间复杂度: O(n)
空间复杂度: O(1)

小优化
判断尾数够不够 k 个来取决右指针的位置

原来写法：

// 方法一
if (sChar.length - i < k) { // 当结尾个数小于 k 时
    left = i; 
    right = sChar.length - 1; 
} else { // 当结尾个数大于等于 k 时
    left = i;
    right = left + k - 1; 
}

更加简洁的写法：

// 方法二
left = i;
right = Math.min(sChar.length - 1,left + k - 1);

剑指Offer 05.替换空格

:::tips 建议：对于线性数据结构，填充或者删除，后序处理会高效的多。好好体会一下。
题目链接：力扣剑指 Offer 05. 替换空格
文章讲解：代码随想录 :::

方法一 - 扩容 + 双指针法：

极致处理就是不使用额外的辅助空间了：

首先扩充数组到每个空格替换成”%20”之后的大小。 ```java StringBuilder sb = new StringBuilder();

// 扩充空间，空格数量2倍 for (int i = 0; i < s.length(); i++) { if (‘ ‘ == s.charAt(i)) { sb.append(“ “); // 两个字符就是字符串了，所以用双引号 } }


2. 然后从后向前替换空格，也就是双指针法
   1. 过程如下：left 指向新长度的末尾，right 指向旧长度的末尾。
![](https://cdn.nlark.com/yuque/0/2023/gif/25477887/1691040770308-1e8ebed1-5593-4a07-8d45-8485e24b8d3c.gif#averageHue=%23fcfcfc&clientId=u07fac3f7-56dc-4&from=paste&id=u70c5edaa&originHeight=346&originWidth=498&originalType=url&ratio=1.5&rotation=0&showTitle=false&status=done&style=none&taskId=u23f86e9f-313d-4c1a-8873-298de0bfa8a&title=)
- 为什么要从后向前填充，从前向后填充不行么？
   - 从前向后填充就是 O(n2) 的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。
**其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。**<br />这么做有两个好处：
1. 不用申请新数组。
2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。
```java
/**
* 扩容 + 双指针
*/
class Solution {
    public String replaceSpace(String s) {
        // 提前返回
        if (s == null) {
            return s;
        }
        StringBuilder sb = new StringBuilder();
        // 扩充空间，空格数量2倍
        for (int i = 0; i < s.length(); i++) {
            if (' ' == s.charAt(i)) {
                sb.append("  "); // 两个字符就是字符串了，所以用双引号
            }
        }
        // 若是没有空格直接返回
        if (sb.length() == 0) {
            return s;
        }
        s += sb.toString();// 将原来的字符串扩容到预订大小
        int right = s.length() - 1; // 左指针：指向原始字符串最后一个位置
        int left = s.length() - sb.length() - 1; // 右指针：指向扩展字符串的最后一个位置
        char[] sChars = s.toCharArray();
        while (left >= 0) {
            if (sChars[left] == ' ') {
                sChars[right--] = '0';
                sChars[right--] = '2';
                sChars[right--] = '%';
            } else {
                sChars[right--] = sChars[left];
            }
            left--;
        }
        return new String(sChars); // 字符数组转化成字符串
    }
}

方法二 - StringBuilder

用 StringBuilder 遇到 ‘ ‘ 直接进行替换 ```java /**

StringBuilder */ class Solution {

public String replaceSpace(String s) {

  // 提前返回
  if (s == null) {
      return s;
  }
  // 选用 StringBuilder 单线程使用，比较快，
  StringBuilder sb = new StringBuilder();
  char[] sChar = s.toCharArray();
  // 使用 sb 逐个复制 s ，碰到空格则替换，否则直接复制
  for (int i = 0; i < sChar.length; i++) {
      if (sChar[i] == ' ') {
          sb.append("%20");
      } else {
          sb.append(sChar[i]);
      }
  }
  return sb.toString();

} } ```

151.翻转字符串里的单词

:::danger

这道题目综合考察了字符串的多种操作重点学习！！！ ::: :::tips 建议：这道题目基本把刚刚做过的字符串操作都覆盖了，不过就算知道解题思路，本题代码并不容易写，要多练一练。
题目链接：力扣 151. 反转字符串中的单词
文章讲解/视频讲解：代码随想录 :::
方法一 - 不使用Java内置方法实现

去除首尾以及中间多余空格
反转整个字符串
反转各个单词 ```java /**
- 方法一 - 不使用Java内置方法实现
- 1. 去除首尾以及中间多余空格
- 1. 反转整个字符串
- 1. 反转各个单词 */ class Solution1 { public String reverseWords(String s) {
    
    // 1.去除首尾以及中间多余空格 StringBuilder sb = removeSpace(s); // 2.反转整个字符串 reverseString(sb, 0, sb.length() - 1); // 3.反转各个单词 reverseEachWord(sb); return sb.toString(); }
  /**
  - 1. 去除首尾以及中间多余空格 *
  - @param s
  - @return */ private StringBuilder removeSpace(String s) {
    
    int start = 0; // 起始指针 int end = s.length() - 1; // 结束指针
    
    while (s.charAt(start) == ‘ ‘) start++; // 将起始指针移动到非空格字符 while (s.charAt(end) == ‘ ‘) end—; // 将结束指针移动到非空格字符
    
    StringBuilder sb = new StringBuilder();
    
    // 从开始指针 start 逐个遍历到 end while (start <= end) {
```
 char c = s.charAt(start);
 // 妙！即如果不是空格 或者 拼接的字符串结尾字符不是空格 -> 都进行拼接
 if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
     sb.append(c);
 }
 start++;
```
    } return sb; }
  /**
  - 1. 反转整个字符串 - 指定区间[start, end]的字符 *
  - @param sb
  - @param start
  - @param end */ private void reverseString(StringBuilder sb, int start, int end) {
    
    char tempC; // 临时字符
    
    while (start < end) {
```
 tempC = sb.charAt(start);
 sb.setCharAt(start, sb.charAt(end)); // setCharAt() -> 设置指定索引的数值
 sb.setCharAt(end, tempC);
 start++;
 end--;
```
    } }
  /**
  - 1. 反转各个单词 *
  - @param sb */ private void reverseEachWord(StringBuilder sb) { int start = 0; int end = 1; int length = sb.length(); while (start < length) {
```
 while (end < length && sb.charAt(end) != ' ') {
     end++;
 }
 reverseString(sb, start, end - 1); // 单个单词的反转
 start = end + 1;
 end = start + 1;
```
    } }

}

<a name="fwljh"></a>
### 方法二 - 创建新字符数组填充法
:::danger
- 整不动了 有时间再细细研究~
:::
```java
/**
* 方法二 - 创建新字符数组填充
*/
class Solution2 {
    public String reverseWords(String s) {
        //源字符数组
        char[] initialArr = s.toCharArray();
        //新字符数组
        char[] newArr = new char[initialArr.length + 1];//下面循环添加"单词 "，最终末尾的空格不会返回
        int newArrPos = 0;
        //i来进行整体对源字符数组从后往前遍历
        int i = initialArr.length - 1;
        while (i >= 0) {
            // 跳过空格
            while (i >= 0 && initialArr[i] == ' ') {
                i--;
            }  
            // 此时i位置是边界或!=空格，先记录当前索引，之后的while用来确定单词的首字母的位置
            int right = i;
            while (i >= 0 && initialArr[i] != ' ') {
                i--;
            }
            // 指定区间单词取出(由于i为首字母的前一位，所以这里+1,)，取出的每组末尾都带有一个空格
            for (int j = i + 1; j <= right; j++) {
                newArr[newArrPos++] = initialArr[j];
                if (j == right) {
                    newArr[newArrPos++] = ' ';//空格
                }
            }
        }
        //若是原始字符串没有单词，直接返回空字符串；若是有单词，返回0-末尾空格索引前范围的字符数组(转成String返回)
        if (newArrPos == 0) {
            return "";
        } else {
            return new String(newArr, 0, newArrPos - 1);
        }
    }
}

时间复杂度O(n)

方法 —- 其他方法
还有两种方式以后有时间再补充~

剑指Offer58-II.左旋转字符串

:::tips 建议：题解中的解法如果没接触过的话，应该会想不到
题目链接：力扣剑指 Offer 58 - II. 左旋转字符串
文章讲解：代码随想录 :::

方法一 - 局部反转 + 整体反转

用原始数组来进行反转操作：

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

例如：示例1中输入：字符串abcdefg，n=2
如图：

先整个字符串反转，再反转前面的，最后反转后面 n 个 ```java /**

方法一 - 局部反转 + 整体反转

不开辟新数组空间复杂度O(1) */ class Solution { public String reverseLeftWords(String s, int n) {

  char[] chars = s.toCharArray();
  reverse(chars, 0, chars.length - 1);
  reverse(chars, 0, chars.length - 1 - n);
  reverse(chars, chars.length - n, chars.length - 1);
  return new String(chars);

}

private void reverse(char[] sChar, int start, int end) {

  while (start < end) {
      sChar[start] ^= sChar[end];
      sChar[end] ^= sChar[start];
      sChar[start] ^= sChar[end];
      start++;
      end--;
  }

} } ```

空间复杂度 O(1)

第四章字符串part02

:::info

KMP 算法原理
1. 实现 strStr()
459.重复的子字符串
字符串总结
双指针回顾 :::

KMP 算法原理
:::tips 视频讲解：
最浅显易懂的 KMP 算法讲解_哔哩哔哩_bilibili
帮你把KMP算法学个通透！（理论篇）_哔哩哔哩_bilibili :::

28. 实现 strStr() （难）

KMP算法很难，一刷了解，二刷深入题目链接：力扣 28. 找出字符串中第一个匹配项的下标文章讲解：代码随想录视频讲解：帮你把KMP算法学个通透！（求next数组代码篇）_哔哩哔哩_bilibili
一刷过😿

459.重复的子字符串（难）

本题算是KMP算法的一个应用，KMP算法很难，一刷了解，二刷深入题目链接：力扣 459. 重复的子字符串文章讲解/视频讲解：代码随想录
一刷过😿

字符串总结
:::tips 比较简单，读一遍就行
题目链接/文章讲解：代码随想录 :::

双指针回顾

:::tips 文章讲解：代码随想录 :::

代码随想录 | 第四章 - 字符串

第四章 字符串part01

344.反转字符串

方法 - 经典双指针

优化 - 位运算交换

541. 反转字符串II

方法 - 双指针

小优化

剑指Offer 05.替换空格

方法一 - 扩容 + 双指针法：

方法二 - StringBuilder

151.翻转字符串里的单词

方法一 - 不使用Java内置方法实现

方法 —- 其他方法

剑指Offer58-II.左旋转字符串

方法一 - 局部反转 + 整体反转

第四章 字符串part02

KMP 算法 原理

28. 实现 strStr() （难）

459.重复的子字符串 （难）

字符串总结

双指针回顾

第四章字符串part01

第四章字符串part02

KMP 算法原理

459.重复的子字符串（难）