剑指Offer JavaScript-字符串专题

替换空格

1. 题目描述

请实现一个函数,把字符串中的每个空格替换成”%20”。

例如输入“We are happy.”,则输出“We%20are%20happy.”。

2. 解题思路

一种是正则表达式:直接使用正则表达式全局替换,这种方法取巧一些。

另一种是先计算出来替换后的字符串长度,然后逐个填写字符。这种方法的时间复杂度是$O(N)$。

3. 代码

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
/**
* 用正则表达式替换
* @param {String} str
*/

function repalceEmpty1(str) {
const re = / /g;
return str.replace(re, "%20");
}

/**
* 将空格替换为 %20
* @param {String} arr
*/
function repalceEmpty2(str) {
str = str.split("");

let count = 0,
i = 0,
j = 0;
for (let i = 0; i < str.length; ++i) {
str[i] === " " && ++count;
}

let length = str.length + count * 2; // 新的字符串的长度:%20比空格长度多2
let result = new Array(length);

while (i < result.length) {
if (str[j] === " ") {
result[i++] = "%";
result[i++] = "2";
result[i++] = "0";
j++;
} else {
result[i++] = str[j++];
}
}

return result.join("");
}

/**
* 测试代码
*/

console.log(repalceEmpty1("We are happy"));
console.log(repalceEmpty2("We are happy"));

字符串全排列

1. 题目描述

输入一个字符串,打印出该字符串中字符的所有排列。例如输入字符串 abc,则打印出由字符 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。

2. 思路分析

把集合看成 2 个部分,第一部分是第一个元素,第二部分是后面剩余元素。所有字符都要与当前集合的第一个元素交换,交换后的元素是固定的,也就是一种情况。

每次交换,都继续处理后面剩余元素,它们又可以分成 2 部分,和之前讲述的一样。就这样一直递归下去,直到最后一个元素,那么就排出了其中一种情况。所有情况放在一起,就是全排列的结果。

3. 代码实现

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
/**
* 交换数组指定坐标的2个元素
* @param {Array} arr
* @param {Number} i
* @param {Number} j
*/
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}

/**
* 检测arr[start, end)中, 是否有和arr[end]相等的元素
* @param {Array} arr
* @param {Number} start
* @param {Number} end
*/
function check(arr, start, end) {
for (let i = start; i < end; ++i) {
if (arr[end] === arr[i]) {
return false;
}
}
return true;
}

/**
* 全排列
* @param {Array} arr 元素集合
* @param {Number} n 起始位置
*/
function perm(arr = [], n = 0) {
const length = arr.length;
if (length === n) {
console.log(arr.join(" "));
return;
}

for (let i = n; i < length; ++i) {
if (check(arr, n, i)) {
swap(arr, n, i);
perm(arr, n + 1);
swap(arr, n, i);
}
}
}

/**
* 测试代码
*/
perm(["a", "b", "c"], 0);
console.log("*".repeat(10));
perm(["a", "b", "b"], 0);

翻转单词顺序

1. 题目描述

输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。

为简单起见,标点符号和普通字母一样处理。例如输入字符串”I am a student.”,则输出”student. a am I”。

2. 思路分析

进行 2 次不同层次的翻转。第一个层次的翻转,是对整体字符串进行翻转。第二个层次的翻转,是对翻转后字符串中的单词进行翻转。

3. 代码实现

注意:因为 js 按位重写字符,所以第一次整体字符串翻转后的每个字符,都放入了数组中。

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
/**
* @param {String} sentence
*/
function reverseSentence(sentence) {
// 第一次翻转:每个字符
const chars = sentence.split("").reverse();
let result = "",
last = []; // 保存上一个空格到当前空格之间的所有字符

chars.forEach((ch) => {
// 遇到空格,说明之前的字符组成了单词
// 进行第二次翻转:单词
if (ch === " ") {
result += last.reverse().join("");
last.length = 0; // 清空上一个单词
}

last.push(ch);
});

result += last.reverse().join("");
return result;
}

/**
* 测试代码,输出:
* student.a am I
*/
console.log(reverseSentence("I am a student."));

实现 atoi 函数

1. 题目描述

请你来实现一个  atoi  函数,使其能将字符串转换成整数。

首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。

注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。

在任何情况下,若函数不能进行有效的转换时,请返回 0。

说明:

假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为  [−2^31,  2^31 − 1]。如果数值超过这个范围,qing 返回  INT_MAX (2^31 − 1) 或  INT_MIN (−2^31) 。

题目来自 LeetCode,可以直接前往这个网址查看题目各种情况下要求的输出。

2. 思路分析

这种题目主要就是考察细心,要主动处理所有情况。所以一步步来即可:

  1. 找出第一个非空字符,判断是不是符号或者数字
  2. 如果是符号,那么判断正负号
  3. 如果符号后面跟的不是数字,那么就是非法的,返回 0
  4. 确定连续数字字符的起始边界
  5. 计算数字字符的代表的数字大小,并且判断是否越界
  6. 返回结果的时候注意符号

3. 代码实现

代码通过了 leetcode 的测试,成绩还不错,如下图:

1.png

代码如下:

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
const MIN_INT_ABS = Math.pow(2, 31);
const MAX_INT = MIN_INT_ABS - 1;

/**
* 判断char是否是符号
* @param {String} char
*/
function isSymbol(char) {
return char === "-" || char === "+";
}

/**
* 判断char是否是数字
* @param {String} char
*/
function isNumber(char) {
return char >= "0" && char <= "9";
}

/**
* 模拟atoi(str)
* @param {String} str
*/
function myAtoi(str) {
const length = str.length;

// 找出第一个非空字符,判断是不是符号或者数字
let firstNotEmptyIndex = 0;
for (
;
firstNotEmptyIndex < length && str[firstNotEmptyIndex] === " ";
++firstNotEmptyIndex
) {}
if (
!isSymbol(str[firstNotEmptyIndex]) &&
!isNumber(str[firstNotEmptyIndex])
) {
return 0;
}

// 如果是符号,那么判断正负号
let positive = true,
firstNumberIndex = firstNotEmptyIndex;
if (isSymbol(str[firstNotEmptyIndex])) {
positive = str[firstNotEmptyIndex] === "+";
firstNumberIndex += 1;
}

// 如果符号后面跟的不是数字,那么就是非法的,返回0
if (!isNumber(str[firstNumberIndex])) {
return 0;
}

// 确定连续数字字符的起始边界
let endNumberIndex = firstNumberIndex;
while (endNumberIndex < length && isNumber(str[endNumberIndex + 1])) {
++endNumberIndex;
}

// 计算数字字符的代表的数字大小
// 并且判断是否越界
let result = 0;
for (let i = firstNumberIndex; i <= endNumberIndex; ++i) {
result = result * 10 + (str[i] - "0");
if (positive && result > MAX_INT) {
return MAX_INT;
}
if (!positive && result > MIN_INT_ABS) {
return -1 * MIN_INT_ABS;
}
}

// 返回的时候注意符号
return positive ? result : -1 * result;
}

/**
* 以下是测试代码
*/

console.log(myAtoi(" +1.123sfsdfsd")); // 1
console.log(myAtoi(" -42")); // -42
console.log(myAtoi("words and 987")); // 0
console.log(myAtoi("-91283472332")); // -2147483648