面试助力，算法 101：JavaScript 描述
搜索文档…
面试助力，算法 101：JavaScript 描述
目录
写在前面
学习指南
开篇——复杂度
字符串
数学
数组
链表
二叉树
动态规划
最大子序和、爬楼梯和买卖股票的最佳时机
打家劫舍、零钱兑换和跳跃游戏
不同路径、Longest Increasing Subsequence和单词拆分
回溯算法
排序与搜索
栈和队列
结束篇
由 GitBook 提供支持
不同路径、Longest Increasing Subsequence和单词拆分

不同路径

一个机器人位于一个 m x n 网格的左上角，机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，问总共有多少条不同的路径？
示例 1
1
输入: m = 3, n = 2
2
输出: 3
3
解释:
4
从左上角开始，总共有 3 条路径可以到达右下角。
5
1. 向右 -> 向右 -> 向下
6
2. 向右 -> 向下 -> 向右
7
3. 向下 -> 向右 -> 向右
Copied!
示例 2
1
输入: m = 7, n = 3
2
输出: 28
Copied!

思路

1
A B C D
2
E F G H
Copied!
从点
(x=0,y=0)(x = 0,y = 0)
 出发，每次只能向下或者向右移动一步，因此下一点的坐标为
(x+1,y)(x + 1, y)
 或者
(x,y+1)(x, y + 1)
，一直到
(x=m,y=n)(x = m, y = n)
。在上图中，H 只能从 G 或者 D 达到，因此从 A 到 H 的路径数等于从 A 到 D 的路径与从 A 到 G 的路径之和。得出路径数量
T(m,n)=T(m−1,n)+T(m,n−1)T(m, n) = T(m-1, n) + T(m, n-1)
。
我们又发现，当$m = 1$ 或 $n = 1$ 时（只能一直往下或往右走），路径数量为1，这里得出跳出递归的条件。

方法一 递归

详解
由上面的分析可得，到达
(m,n) (m, n)
的路径数量为
(m,n−1) (m, n-1)
坐标的路径数量与
(m−1,n)(m-1, n)
坐标的路径数量之和 。可以使用最简单粗暴的递归方法
代码
1
/**
2
* @param {number} m
3
* @param {number} n
4
* @return {number}
5
*/
6
const uniquePaths = function (m, n) {
7
if (m === 1 || n === 1) {
8
return 1;
9
}
10
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
11
};
Copied!

方法二 动态规划

详解
根据以上思路，可以推出状态转移方程为
​
dp[i][j]=dp[i−1][j]+dp[i][j−1]dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
​
1
1
1
1
1
1
1
1
2
3
4
5
6
7
1
3
6
10
15
21
28
代码
1
/**
2
* @param {number} m
3
* @param {number} n
4
* @return {number}
5
*/
6
const uniquePaths = function (m, n) {
7
const dp = new Array(m);
8
for (let i = 0; i < m; i++) {
9
dp[i] = new Array(n);
10
}
11
for (let i = 0; i < m; i++) {
12
for (let j = 0; j < n; j++) {
13
if (i === 0 || j === 0) {
14
dp[i][j] = 1;
15
} else {
16
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
17
}
18
}
19
}
20
return dp[m - 1][n - 1];
21
};
Copied!
复杂度分析
  • 时间复杂度：
    O(m∗n)O(m * n)
上述解法中，对
mm
 和
nn
 进行了双重循环，时间复杂度跟数字的个数线性相关，即为
O(m∗n)O(m*n)
  • 空间复杂度：
    O(m∗n)O(m * n)
申请了大小为
m∗nm * n
的二维数组

方法三 动态规划优化

减少空间复杂度
详解
我们观察表格发现，下一个值等于当前值加上一行的值，利用这个发现，可以来压缩空间，用一维数组来实现
1
const uniquePaths = function (m, n) {
2
const dp = new Array(n).fill(1);
3
for (let i = 1; i < m; i++) {
4
for (let j = 1; j < n; j++) {
5
dp[j] = dp[j - 1] + dp[j];
6
}
7
}
8
return dp[n - 1];
9
};
Copied!
复杂度分析
  • 时间复杂度：
    O(m∗n)O(m * n)
  • 空间复杂度：
    O(n)O(n)
    ​

方法四 排列组合

详解
其实这是个高中数学问题。因为机器人只能向右或者向下移动，那么不论有多少中路径，向右和向下走的步数都是一样的。当
m=3，n=2m = 3，n = 2
时，机器人向下走了一步，向右走了两步即可到达终点。所以我们可以得到
路径 = 从右边开始走的路径总数 + 从下边开始走的路径总数，转化为排列组合问题
不包括起点和终点，共移动
N=m+n−2N = m + n - 2
，向右移动
K=m−1K = m - 1
，将
NN
 和
KK
 代入上述公式，可得
因此得出答案
Cm+n−2m−1C_{m + n -2}^{m - 1}
​
1
/**
2
* @param {number} m
3
* @param {number} n
4
* @return {number}
5
*/
6
const uniquePaths = function (m, n) {
7
const N = m + n - 2;
8
const K = n - 1;
9
let num = 1;
10
for (let i = 1; i <= K; i++) {
11
num = num * (N - K + i) / i;
12
}
13
return num;
14
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n)O(n)
    ​
  • 空间复杂度：
    O(1)O(1)
    ​

Longest Increasing Subsequence

给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例
1
输入: [10,9,2,5,3,7,101,18]
2
输出: 4
3
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
Copied!

方法一 动态规划

思路
  • 状态定义：res[i] 表示以 nums[i] 为当前最长递增子序列尾元素的长度
  • 转移方程：通过方程 res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1)，动态计算出各上升子序列的长度。
  • 倒序取值：res 数组进行倒序，第一个即为最大长度的值。
详解
  1. 1.
    如果给定数组长度小于等于 1，则最长上升子序列的长度等于数组长度。
  2. 2.
    初始化一个长度等于给定数组的长度，且元素都为 1 的数组 res。
  3. 3.
    当 nums[i] > nums[j] 时，nums[i] 可以作为前一个最长的递增子序列 res[j] 新的尾元素，而组成新的相对于 res[i] 能够拼接的更长的递增子序列 res[i] = res[j] + 1，因为新的 res[i] 能够拼接的最长长度取决于 nums[i] 这个新的尾元素，而这个 nums[i] 不一定大于 nums[j]，所以也不一定大于 res[j]，那么在 i ~ j 之间，最大的递增子序列为 Max(res[i], res[j]+1)；当 nums[i] <= nums[j]，长度为元素本身，即为 1。所以得出方程 res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1)，通过转移方程收集
    各上升子序列的长度。
  4. 4.
    通过 sort 函数对 res 倒序排列，第一元素值 res[0] 就是最长的上升子序列长度。
1
/**
2
* @param {number[]} nums
3
* @return {number}
4
*/
5
const lengthOfLIS = function (nums) {
6
const len = nums.length;
7
if (len <= 1) {
8
return len;
9
}
10
// 初始化默认全为1
11
const res = new Array(len).fill(1);
12
for (let i = 1; i < len; i++) {
13
for (let j = 0; j < i; j++) {
14
// 转移方程
15
res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1);
16
}
17
}
18
// 倒序
19
res.sort((a, b) => b - a);
20
return res[0];
21
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n2)O(n^2)
    ​
  • 空间复杂度：
    O(n)O(n)
    ​

方法二 二分查找

思路
  • 当前遍历元素大于前一个递增子序列的尾元素时（nums[i] > tail[end]），将当前元素追加到 tail 后面，这里解法其实和方法一中
    nums[i] > nums[j] 的解法一样。
  • 当 nums[i] <= tail[end] 时，寻找前一个递增子序列第一个大于当前值的元素，替换为当前值，查找用二分，最后左边的元素即为查找到的需要被替换的结果元素。
详解
1、如果给定数组长度小于等于 1，则最长上升子序列的长度等于数组长度。 2、初始化一个长度等于给定数组的长度，且第一个元素值等于给定数组的第一个元素值的数组 tail，tail 用来存储最长递增子序列的元素。 3、循环给定的数组，当前遍历元素大于前一个递增子序列的尾元素时（nums[i] > tail[end]），将当前元素追加到 tail 后面，这里解法 其实和方法一中nums[i] > nums[j] 的解法一样；当 nums[i] <= tail[end] 时，寻找前一个递增子序列第一个大于当前值的元素，替换为当前值，查找用二分，最后左边的元素即为查找到的需要被替换的结果元素。 4、循坏完之后，end + 1 即为最长的上升子序列长度。
1
/**
2
* @param {number[]} nums
3
* @return {number}
4
*/
5
const lengthOfLIS = function (nums) {
6
const len = nums.length;
7
if (len <= 1) {
8
return len;
9
}
10
const tail = new Array(len);
11
tail[0] = nums[0];
12
let end = 0;
13
for (let i = 1; i < len; i++) {
14
if (nums[i] > tail[end]) {
15
end += 1;
16
tail[end] = nums[i];
17
} else {
18
let left = 0;
19
let right = end;
20
// 二分查找
21
while (left < right) {
22
// 位运算，右移一位
23
const mid = left + ((right - left) >> 1);
24
if (tail[mid] < nums[i]) {
25
left = mid + 1;
26
} else {
27
right = mid;
28
}
29
}
30
tail[left] = nums[i];
31
}
32
}
33
return end + 1;
34
};
Copied!
复杂度分析
  • 时间复杂度：
    O(nlogN)O(nlogN)
    ​
    外层一个数组循环遍历，里面嵌套一个二分查找，所以是
    O(nlogN)O(nlogN)
    ​
  • 空间复杂度：
    O(n)O(n)
    ​
    创建的数组 tail 占用空间大小为 n，循环遍历中并没有分配新的空间

单词拆分

示例
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
  • 拆分时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。
  • 注意你可以重复使用字典中的单词。
示例 1：
1
输入: s = "leetcode", wordDict = ["leet", "code"]
2
输出: true
3
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
Copied!
示例 2：
1
输入: s = "applepenapple", wordDict = ["apple", "pen"]
2
输出: true
3
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
Copied!
示例 3：
1
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
2
输出: false
Copied!

方法一 暴力破解法

思路
把字符串 s 的前缀从短到长拆出来进行判断是否在单词字典中，若在字典中则把前缀截取掉继续递归，直到字符串的长度为 0。在递归中若遇到字符串任何长度的前缀都无法匹配到字典中的单词，则回溯到上层递归。
详解
1、检查字典中是否有字符串的前缀； 2、若有的话，将字符串去掉这个前缀后继续遍历，重复步骤 1、2； 3、若某次调用发现整个字符串都已拆分并且都在字典内则返回 true；
1
const wordBreak = function (s, wordDict) {
2
if (s.length === 0) {
3
return true;
4
}
5
for (let i = 0; i < wordDict.length; i += 1) {
6
const startIndex = s.indexOf(wordDict[i]);
7
if (startIndex === 0) {
8
// 将字符串去掉这个匹配到的前缀后继续遍历
9
const temp = s.slice(startIndex + wordDict[i].length);
10
if (wordBreak(temp, wordDict) === true) {
11
return true;
12
}
13
}
14
}
15
return false;
16
};
Copied!
  • 时间复杂度：最坏情况下是
    O(nn)O(n^n)
    ，因为考虑 s = 'aaaaaaaaaaaaaaaa'， wordDict = ['a']，每一个字符都在字典中，此时递归的时间复杂度会达到
    O(nn) O(n^n)
    ，妥妥超时
  • 空间复杂度：
    O(1)O(1)
    ，循环中申请了 3 个临时变量，与输入的字符串的长度无关，空间占用属于常数阶，故空间复杂度为
    O(1)O(1)
    。

方法二 动态规划

思路
dp[i] 表示字符串 s 从开始到 i 位置是否可以由 wordDict 组成。使用 j 从头开始遍历，若 dp[i] 可由 wordDict 组成，并且 i 到 j 之间的单词可以在 wordDict中找到，则说明 dp[i] = true。
详解
1、第一层遍历：用 i 从头到尾遍历字符串； 2、第二层遍历：用 j 从头到 i 遍历字符串； 3、若 dp[j] = true 而且字典中存在字符串 s[i~j]，则说明 dp[i] = true； 4、继续步骤 1、2，直到整个字符串都遍历一遍； 5、若 dp[s.length()] = true，则说明字符可由字段中的单词组合而成；
代码
1
const wordBreak = function (s, wordDict) {
2
const len = s.length;
3
const dp = new Array(len + 1).fill(false);
4
dp[0] = true;
5
for (let i = 1; i <= len; i++) {
6
for (let j = 0; j < i; j++) {
7
if (dp[j] && wordDict.includes(s.substring(j, i))) {
8
dp[i] = true;
9
break;
10
}
11
}
12
}
13
return dp[len];
14
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n2)O(n^2)
    ​
    因为有两层循环，每层循环都从头遍历到尾。
  • 空间复杂度：
    O(n)O(n)
    ​
    因为只开辟了一个
    nn
    长度的数组。

方法三 动态规划（优化版）

思路
第二层遍历中不用每次遍历 i 的长度，只要遍历字典中最长单词的长度 maxStep 即可。
详解
1、第一层遍历：用 i 从头到尾遍历字符串； 2、第二层遍历：用 j 从 i - maxStep 到 i 遍历字符串； 3、若 dp[j] = true 而且字典中存在字符串 s[i~j]，则说明 dp[i] = true； 4、继续步骤 1、2，直到整个字符串都遍历一遍； 5、若 dp[s.length()] = true，则说明字符可由字段中的单词组合而成；
1
const wordBreak = function (s, wordDict) {
2
const len = s.length;
3
const dp = new Array(len + 1).fill(false);
4
dp[0] = true;
5
// 计算单词的最长长度
6
let maxStep = 0;
7
for (let i = 0; i < wordDict.length; i++) {
8
if (wordDict[i].length > maxStep) {
9
maxStep = wordDict[i].length;
10
}
11
}
12
for (let i = 1; i <= len; i++) {
13
const startOfJ = i - maxStep > 0 ? i - maxStep : 0;
14
for (let j = startOfJ; j < i; j++) {
15
if (dp[j] && wordDict.includes(s.substring(j, i))) {
16
dp[i] = true;
17
break;
18
}
19
}
20
}
21
return dp[len];
22
};
Copied!
复杂度分析
  • 时间复杂度：
    O(n2)O(n^2)
    ​
    因为有两层循环，每层循环都从头遍历到尾。
  • 空间复杂度：
    O(n)O(n)
    ​
    因为最长只开辟了一个
    nn
     长度的数组。
以前
打家劫舍、零钱兑换和跳跃游戏
下一个
回溯算法
最近更新 1yr ago
复制链接
内容
不同路径
Longest Increasing Subsequence
单词拆分