面试助力，算法 101：JavaScript 描述
搜索文档…
面试助力，算法 101：JavaScript 描述
目录
写在前面
学习指南
开篇——复杂度
字符串
翻转整数、有效的字母异位词和翻转整数
报数、反转字符串和字符串中的第一个唯一字符
验证回文字符串、实现 strStr() 、最长公共前缀和最长回文子串
数学
数组
链表
二叉树
动态规划
回溯算法
排序与搜索
栈和队列
结束篇
由 GitBook 提供支持
翻转整数、有效的字母异位词和翻转整数

翻转整数

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例
1
示例 1:
2
输入: 123
3
输出: 321
4
​
5
示例 2:
6
输入: -123
7
输出: -321
8
​
9
示例 3:
10
输入: 120
11
输出: 21
Copied!
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为
[−231,231−1][−2^{31}, 2^{31} − 1]
。请根据这个假设，如果反转后整数溢出那么就返回 0。

方法一 翻转字符串方法

思路
如果将数字看成是有符号位的字符串，那么我们就能够通过使用 JS 提供的字符串方法来实现非符号部分的翻转，又因为整数的翻转并不影响符号，所以我们最后补充符号，完成算法。
详解
  1. 1.
    首先设置边界极值；
  2. 2.
    使用字符串的翻转函数进行主逻辑；
  3. 3.
    补充符号
  4. 4.
    然后拼接最终结果
代码
1
/**
2
* @param {number} x
3
* @return {number}
4
*/
5
const reverse = (x) => {
6
// 非空判断
7
if (typeof x !== 'number') {
8
return;
9
}
10
// 极值
11
const MAX = 2147483647;
12
const MIN = -2147483648;
13
​
14
// 识别数字剩余部分并翻转
15
const rest =
16
x > 0
17
? String(x)
18
.split('')
19
.reverse()
20
.join('')
21
: String(x)
22
.slice(1)
23
.split('')
24
.reverse()
25
.join('');
26
​
27
// 转换为正常值，区分正负数
28
const result = x > 0 ? parseInt(rest, 10) : 0 - parseInt(rest, 10);
29
​
30
// 边界情况
31
if (result >= MIN && result <= MAX) {
32
return result;
33
}
34
return 0;
35
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    代码中 reverse 函数时间复杂度为
    O(n)O(n)
    ，
    nn
     为整数长度，因此时间复杂度为
    O(n)O(n)
    ，考虑到32位整数最大长度为 11，即 -2147483648，也可认为是常数时间复杂度
    O(1)O(1)
    。
  • 空间复杂度：
    O(n)O(n)
    ​
    代码中创建临时 String 对象，
    nn
     为整数长度，因此空间复杂度为
    O(n)O(n)
    ，考虑到32位整数最大长度为11，即-2147483648，因此空间复杂度为
    O(1)O(1)
    。

方法二 类似 欧几里得算法 求解

思路
我们借鉴欧几里得求最大公约数的方法来解题。符号的处理逻辑同方法一，这里我们通过模 10 取到最低位，然后又通过乘 10 将最低位迭代到最高位，完成翻转。
详解
  1. 1.
    设置边界极值；
  2. 2.
    取给定数值的绝对值，遍历循环生成每一位数字，借鉴欧几里得算法，从 num 的最后一位开始取值拼成新的数
  3. 3.
    同步剔除掉被消费的部分
  4. 4.
    如果最终结果为异常值，则直接返回 0；如果原本数据为负数，则对最终结果取反
  5. 5.
    返回最终结果
代码
1
/**
2
* @param {number} x
3
* @return {number}
4
*/
5
const reverse = (x) => {
6
// 获取相应数的绝对值
7
let int = Math.abs(x);
8
// 极值
9
const MAX = 2147483647;
10
const MIN = -2147483648;
11
let num = 0;
12
​
13
// 遍历循环生成每一位数字
14
while (int !== 0) {
15
// 借鉴欧几里得算法，从 num 的最后一位开始取值拼成新的数
16
num = (int % 10) + (num * 10);
17
// 剔除掉被消费的部分
18
int = Math.floor(int / 10);
19
}
20
// 异常值
21
if (num >= MAX || num <= MIN) {
22
return 0;
23
}
24
if (x < 0) {
25
return num * -1;
26
}
27
return num;
28
};
Copied!

复杂度分析：

  • 时间复杂度：
    O(n)O(n)
    ​
    代码中使用 for 循环，次数为
    nn
    ，即整数的长度，因此时间复杂度为
    O(n)O(n)
    。
  • 空间复杂度：
    O(1)O(1)
    ​
    算法中只用到常数个变量，因此空间复杂度为
    O(1)O(1)
    。

有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例1
1
输入: s = "anagram", t = "nagaram"
2
输出: true
Copied!
示例2
1
输入: s = "rat", t = "car"
2
输出: false
Copied!

方法一 利用数组sort()方法

思路
首先，对字符串字母进行排序，然后，比较两字符串是否相等。
详解
  1. 1.
    首先，将字符串转为数组。
  2. 2.
    利用数组 sort 方法进行排序。
  3. 3.
    然后，转为字符串进行比较，如果相等返回 true，反之返回 false。
代码
1
const isAnagram = (s, t) => {
2
const sArr = s.split('');
3
const tArr = t.split('');
4
const sortFn = (a, b) => {
5
return a.charCodeAt() - b.charCodeAt();
6
};
7
sArr.sort(sortFn);
8
tArr.sort(sortFn);
9
return sArr.join('') === tArr.join('');
10
};
Copied!
复杂度分析
  • 时间复杂度：
    O(nlogn)O(nlogn)
    ​
    JavaScript 的 sort 方法的实现原理，当数组长度小于等于 10 的时候，采用插入排序，大于 10 的时候，采用快排，快排的平均时间复杂度是
    O(nlogn)O(nlogn)
    。
  • 空间复杂度：
    O(n)O(n)
     算法中申请了 2 个数组变量用于存放字符串分割后的字符串数组，所以数组空间长度跟字符串长度线性相关，所以为
    O(n)O(n)
    。

方法二 计数累加方法

思路
声明一个对象记录字符串每个字母的个数，另外一个字符串每项与得到的对象做匹配，最后，根据计数判断是否相等。
详解
  1. 1.
    首先，声明一个变量，遍历其中一个字符串 s 或 t，对每个字母出现的次数进行累加。
  2. 2.
    然后，遍历另一个字符串，使每一个字母在已得到的对象中做匹配，如果匹配则对象下的字母个数减 1，如果匹配不到，则返回 false，如果最后对象中每个字母个数都为 0，则表示两字符串相等。
代码
1
const isAnagram = (s, t) => {
2
if (s.length !== t.length) {
3
return false;
4
}
5
const hash = {};
6
for (const k of s) {
7
hash[k] = hash[k] || 0;
8
hash[k] += 1;
9
}
10
for (const k of t) {
11
if (!hash[k]) {
12
return false;
13
}
14
hash[k] -= 1;
15
}
16
return true;
17
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
    算法中使用了 2 个单层循环，因此，时间复杂度为
    O(n)O(n)
    。
  • 空间复杂度：
    O(1)O(1)
    ​
    申请的变量 hash 最大长度为 256，因为 Ascii 字符最多 256 种可能，因此，考虑为常量空间，即
    O(1)O(1)
    。

字符串转换整数

atoi (表示 ascii to integer)是把字符串转换成整型数的一个函数，实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
示例
示例 1:
1
输入: "42
2
输出: 42
Copied!
示例 2:
1
输入: "-42"
2
输出: -42
Copied!
示例 3:
1
输入: "4193 with words"
2
输出: 4193
Copied!
示例 4:
1
输入: "words and 987"
2
输出: 0
Copied!
示例 5:
1
输入: "-91283472332"
2
输出: -2147483648
Copied!
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−2147483648) 。
说明：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。 你的算法的时间复杂度必须优于
O(nlogn)O(n log n)
 ,
nn
 是数组的大小。

方法一 正则匹配

思路
第一步，使用正则提取满足条件的字符，/^(-|\+)?\d+/g，(-|\+)?表示第一位是-或+或都不是，\d+ 表示匹配多个数字
1
const result = str.trim().match(/^(-|\+)?\d+/g);
Copied!
第二步，判断目标是否超过 Int 整形最大值或最小值
1
return result
2
? Math.max(Math.min(Number(result[0]), Math.pow(2,31)-1), -Math.pow(2,31))
3
: 0;
Copied!
代码
1
/**
2
* @param {string} str
3
* @return {number}
4
*/
5
const myAtoi = function (str) {
6
// 提取需要的字符
7
const result = str.trim().match(/^(-|\+)?\d+/g);
8
return result
9
? Math.max(Math.min(Number(result[0]), Math.pow(2, 31) - 1), -Math.pow(2, 31))
10
: 0;
11
};
Copied!
复杂度分析
  • 时间复杂度：
    O(1)O(1)
    ​
    上述解法中，代码在执行的时候，它消耗的时间并不随着某个变量的增长而增长，因此时间复杂度为
    O(1)O(1)
    ​
  • 空间复杂度:
    O(1)O(1)
    ​
    上述解法中，额外所分配的空间都不随着处理数据量变化，所以空间复杂度为
    O(1)O(1)
    ​

方法二 逐个判断

思路
第一步，去除字符串之中的空格
1
const news = str.trim();
Copied!
第二步，通过执行 parseInt 判断是否为数字，不是数字返回 0 ，是数组继续解析
1
if(parseInt(news)){
2
return retrunNum(parseInt(news));
3
} else {
4
return 0;
5
}
Copied!
第三步，判断目标是否超过 Int 整形最大值或最小值
1
const retrunNum = function (num) {
2
if (num >= -Math.pow(2, 31) && num <= Math.pow(2, 31) - 1) {
3
return num;
4
} else {
5
return num > 0 ? Math.pow(2, 31) - 1 : -Math.pow(2, 31);
6
}
7
};
Copied!
代码
1
/**
2
* @param {string} str
3
* @return {number}
4
*/
5
const myAtoi = function (str) {
6
const news = str.trim();
7
if (parseInt(news)) {
8
return retrunNum(parseInt(news));
9
} else {
10
return 0;
11
}
12
};
13
const retrunNum = function (num) {
14
if (num >= -Math.pow(2, 31) && num <= Math.pow(2, 31) - 1) {
15
return num;
16
} else {
17
return num > 0 ? Math.pow(2, 31) - 1 : -Math.pow(2, 31);
18
}
19
};
Copied!
复杂度分析
  • 时间复杂度：
    O(1)O(1)
    ​
    上述解法中，代码在执行的时候，它消耗的时间并不随着某个变量的增长而增长，因此时间复杂度为
    O(1)O(1)
    ​
  • 空间复杂度:
    O(1)O(1)
     上述解法中，额外所分配的空间都不随着处理数据量变化，所以空间复杂度为
    O(1)O(1)
    ​
以前
字符串
下一个
报数、反转字符串和字符串中的第一个唯一字符
最近更新 2yr ago
复制链接
内容
翻转整数
有效的字母异位词
字符串转换整数