代码随想录算法训练营008|151.翻转字符串里的单词，344.反转字符串，541.反转字符串II，剑指Offer 05.替换空格

151. 反转字符串中的单词

题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/

解题思路

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

代码

/**
 * @param {string} s
 * @return {string}
 */
var reverseWords = function (s) {
  // 字符串转数组
  const strArr = Array.from(s);
  // 移除多余空格
  removeExtraSpaces(strArr);
  // 翻转
  reverse(strArr, 0, strArr.length - 1);

  let start = 0;

  for (let i = 0; i <= strArr.length; i++) {
    if (strArr[i] === " " || i === strArr.length) {
      // 翻转单词
      reverse(strArr, start, i - 1);
      start = i + 1;
    }
  }

  return strArr.join("");
};

// 删除多余空格
function removeExtraSpaces(strArr) {
  let slowIndex = 0;
  let fastIndex = 0;

  while (fastIndex < strArr.length) {
    // 移除开始位置和重复的空格
    if (
      strArr[fastIndex] === " " &&
      (fastIndex === 0 || strArr[fastIndex - 1] === " ")
    ) {
      fastIndex++;
    } else {
      strArr[slowIndex++] = strArr[fastIndex++];
    }
  }

  // 移除末尾空格
  strArr.length = strArr[slowIndex - 1] === " " ? slowIndex - 1 : slowIndex;
}

// 翻转从 start 到 end 的字符
function reverse(strArr, start, end) {
  let left = start;
  let right = end;

  while (left < right) {
    // 交换
    [strArr[left], strArr[right]] = [strArr[right], strArr[left]];
    left++;
    right--;
  }
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

344. 反转字符串

题目链接：https://leetcode.cn/problems/reverse-string/

解题思路

1. 双指针法

我们定义两个指针（也可以说是索引下表），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素

代码

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify s in-place instead.
 */
var reverseString = function (s) {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    [s[left], s[right]] = [s[right], s[left]];
    left++;
    right--;
  }
  return s;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

541. 反转字符串 II

题目链接：https://leetcode.cn/problems/reverse-string-ii/

解题思路

1. 模拟

在遍历字符串的过程中，只要让 i += (2 _ k)，i 每次移动 2 _ k 就可以了，然后判断是否需要有反转的区间。

代码

/**
 * @param {string} s
 * @param {number} k
 * @return {string}
 */
function reverse(arrS, start, end) {
  for (let i = start, j = end; i < j; i++, j--) {
    [arrS[i], arrS[j]] = [arrS[j], arrS[i]];
  }
}
var reverseStr = function (s, k) {
  const arrS = s.split(""); // javascript中字符串是不能改变的，使用数组
  const length = arrS.length;
  for (let i = 0; i < length; i += 2 * k) {
    // 1. 每隔 2k 个字符的前 k 个字符进行反转
    // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
    if (i + k <= length) {
      reverse(arrS, i, i + k - 1);
      continue;
    }
    // 3. 剩余字符少于 k 个，则将剩余字符全部反转。
    reverse(arrS, i, length - 1);
  }
  return arrS.join("");
};
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

剑指 Offer 05. 替换空格

题目链接：https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

解题思路

1. API

• replace 方法，str.replace(regexp|substr, newSubStr|function)
• 如果 pattern 是字符串，则仅替换第一个匹配项。

代码

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function (s) {
  if (!s || !s.length) return "";

  return s.replace(/\s/g, "%20");
};
1
2
3
4
5
6
7
8
9

2. 数组遍历，比较替换

将字符串转换为数组，比较替换

代码

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function (s) {
  if (!s || !s.length) return "";

  let arr = s.split("");
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === " ") {
      arr[i] = "%20";
    }
  }
  return arr.join("");
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3. 原地修改

因为字特串是不可变的，所以如果直接采用从头到尾遍历原字符串检查空格，并且做替换。那么每次检童到空格后，都需要重新生成字符串，整个过程时间复杂度是 O(n＾2)

优化的关键：提前计算替换后的字符串的长度，避免每次都对字符串做改动。

整体思路如下：

1）遍历原字特串，统计空格和非空格字符个数，计算替换后的新字符的长度
2）准备两个指针，指针i指向原字符串，指针j指向新字符串
3）i从头开始遍历原字符串
-str[i]是非空格，那么将 i 指向的字符放入新字符串的 j 位置，i 和 j 都增加 1。
-str[i]是空格，那么 j 指向的位置依次填入％、2、1。i 增加 1，j增加 3

时间复杂度是 O(n)。因为需要对新字符串开辟容器，空间复杂度是 O(n)

代码

/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function (s) {
  if (!s || !s.length) return "";

  let chNum = 0; // 非空格字符个数
  let emptyNum = 0; //空格字符个数

  // 遍历原字特串，统计空格和非空格字符个数，计算替换后的新字符的长度
  for (let i = 0; i < s.length; i++) {
    if (s[i] === " ") {
      emptyNum++;
    } else {
      chNum++;
    }
  }
  const len = 2 * emptyNum + chNum;

  const res = new Array(len);
  // 指针`i`指向原字符串，指针`j`指向新字符串
  for (let i = 0, j = 0; i < s.length; i++) {
    if (s[i] === " ") {
      res[j++] = "%";
      res[j++] = "2";
      res[j++] = "0";
    } else {
      res[j++] = s[i];
    }
  }

  return res.join("");
};
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