此教程参考 代码随想录-字符串篇
感谢支持！

字符串 String

代码随想录-总汇 中包含字符串的基础知识

题目

344. 反转字符串

非常基本的双指针应用题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public void reverseString(char[] s) {
        // 双指针swap:
        int left = 0, right = s.length - 1;
        while (left < right) {
            swap(s, left, right);
            left++;
            right--;
        }
    }

    private void swap(char[] s, int left, int right) {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
    }
}

541. 反转字符串 II

本题难点在于问题转化：题干上：

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

如果直接模拟这两条规则的话会比较麻烦，但是其实这两条可以等价转化为如下的问题：

当剩余元素多于k个，反转前k个 (i, i + k)，否则反转后k个 (i, n - 1)

那么问题迎刃而解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public String reverseStr(String s, int k) {
      char[] s2char = s.toCharArray();

      // methodOne(k, s2char);
      // methodTwo:
      for (int left = 0; left < s2char.length; left += 2 * k) {
          swap(s2char, left, Math.min(left + k, s2char.length) - 1);
      }

      return String.valueOf(s2char);
  }

  private void methodOne(int k, char[] s2char) {
      for (int left = 0; left < s2char.length; left = left + k * 2) {
          if (left + k <= s2char.length) {
              // 元素在length里面不会取空
              swap(s2char, left, left + k - 1);
              continue;
          }
          // 若少于k个，翻转剩余全部字符
          swap(s2char, left, s2char.length - 1);
      }
  }

  private void swap (char[] s2char, int left, int right) {
      while (left < right) {
          char temp = s2char[left];
          s2char[left] = s2char[right];
          s2char[right] = temp;
          left++;
          right--;
      }
  }

剑指 Offer 05. 替换空格

此题的解法有两个分别是：

  1. 用到额外的空间 （非常简单，直接秒杀）

    1. 这里简单提一下StringBuilder 和 StringBuffer的区别
    2. StringBuilder 单线程，会快一些

  2. 不用额外的空间，原地修改

    替换空格-原地修改

    1. 其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。
    2. 这么做有两个好处：
      1. 不用申请新数组。
      2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
      public String replaceSpace(String s) {
          StringBuilder sb = new StringBuilder();
          for (char c : s.toCharArray()) {
              if (c == ' ') sb.append(" ").append(" ");
          }
          // older length
          int fast = s.length() - 1;
          s = s + sb;
          // newer length
          int slow = s.length() - 1;
          char[] sAsChar = s.toCharArray();
          while (fast >= 0) {
              if (sAsChar[fast] != ' ') {
                  sAsChar[slow] = sAsChar[fast];
                  fast--;
                  slow--;
              } else {
                  sAsChar[slow--] = '0';
                  sAsChar[slow--] = '2';
                  sAsChar[slow--] = '%';
                  fast--;
              }
          }
          return String.valueOf(sAsChar);
      }

      private String methodOneWithExtraSpace(String s) {
          StringBuilder sb = new StringBuilder();
          for (char c : s.toCharArray()) {
              if (c == ' ') {
                  sb.append("%20");
              } else {
                  sb.append(c);
              }
          }
          return sb.toString();
      }
  }

151. 反转字符串中的单词

依旧是两个解法：

  1. 使用库函数：

    1. String.trim()
      1. String.trim()
      2. eliminates leading and trailing spaces.
      3. Time: O(N)
    2. String.split(String reges, int limit)
      1. breaks a given string around matches of the given regular expression
      2. Time: O(N)
    3. 151_LC_解法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    private String methodOneUseLibrary(String s) {
        String[] elementsArr = s.trim().split(" ");
    //            Arrays.stream(elementsArr).forEach(e -> System.out.println(e + "/"));
        StringBuilder sb = new StringBuilder();
        int i;
        for (i = elementsArr.length - 1; i >= 1; i--) {
            if (Objects.equals(elementsArr[i], "")) continue;
            sb.append(elementsArr[i]).append(" ");
        }
        sb.append(elementsArr[i]);
        return sb.toString();
    }

  2. 双指针：

    1. 倒序遍历字符串 s ，记录单词左右索引边界 i, j
    2. 每确定一个单词的边界，则将其添加至单词列表 res ；
    3. 最终，将单词列表拼接为字符串，并返回即可。
1
2
3
4
5
6
7
8
9
10
11
12
public String reverseWords(String s) {
    s = s.trim(); // 删除首尾空格
    int left = s.length() - 1, right = s.length() - 1;
    StringBuilder sb = new StringBuilder();
    while (left >= 0) {
        while (left >= 0 && s.charAt(left) != ' ') left--; // 搜索首个空格
        sb.append(s, left + 1, right + 1).append(" "); // 添加单词
        while (left >= 0 && s.charAt(left) == ' ') left--; // 跳过单词间空格
        right = left; // right 指向下个单词的尾字符
    }
    return sb.toString().trim(); // 转化为字符串并返回
}

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

依旧是两个做法：

不使用额外空间：整体反转 + 局部反转

左旋转字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String reverseLeftWords(String s, int n) {
      // 局部反转 + 整体反转
      // 反转区间为前n的子串
      // 反转区间为n到末尾的子串
      // 反转整个字符串
      StringBuilder sb = new StringBuilder(s);
      swap(sb, 0, n);
      swap(sb, n, s.length());
      swap(sb, 0, sb.length());
      return sb.toString();
  }

  private void swap(StringBuilder sb, int left, int right) {
      while (left < right) {
          char temp = sb.charAt(left);
          sb.setCharAt(left, sb.charAt(right));
          sb.setCharAt(right, temp);
          left++;
          right--;
      }
  }

使用额外空间：

1
2
3
4
5
private String methodOneUserExtraSpace(String s, int n) {
    StringBuilder sb = new StringBuilder(s.substring(n));
    sb.append(s, 0, n);
    return sb.toString();
}