一个机器人位于一个 m x n 网格的左上角,机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角,问总共有多少条不同的路径?
示例 1
输入: m = 3, n = 2输出: 3解释:从左上角开始,总共有 3 条路径可以到达右下角。1. 向右 -> 向右 -> 向下2. 向右 -> 向下 -> 向右3. 向下 -> 向右 -> 向右
示例 2
输入: m = 7, n = 3输出: 28
A B C DE F G H
从点 出发,每次只能向下或者向右移动一步,因此下一点的坐标为 或者,一直到。在上图中,H 只能从 G 或者 D 达到,因此从 A 到 H 的路径数等于从 A 到 D 的路径与从 A 到 G 的路径之和。得出路径数量 。
我们又发现,当$m = 1$ 或 $n = 1$ 时(只能一直往下或往右走),路径数量为1,这里得出跳出递归的条件。
详解
由上面的分析可得,到达的路径数量为坐标的路径数量与 坐标的路径数量之和 。可以使用最简单粗暴的递归方法
代码
/*** @param {number} m* @param {number} n* @return {number}*/const uniquePaths = function (m, n) {if (m === 1 || n === 1) {return 1;}return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);};
详解
根据以上思路,可以推出状态转移方程为
1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 2 | 3 | 4 | 5 | 6 | 7 |
1 | 3 | 6 | 10 | 15 | 21 | 28 |
代码
/*** @param {number} m* @param {number} n* @return {number}*/const uniquePaths = function (m, n) {const dp = new Array(m);for (let i = 0; i < m; i++) {dp[i] = new Array(n);}for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (i === 0 || j === 0) {dp[i][j] = 1;} else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m - 1][n - 1];};
复杂度分析
时间复杂度:
上述解法中,对 和 进行了双重循环,时间复杂度跟数字的个数线性相关,即为
空间复杂度:
申请了大小为 的二维数组
减少空间复杂度
详解
我们观察表格发现,下一个值等于当前值加上一行的值,利用这个发现,可以来压缩空间,用一维数组来实现
const uniquePaths = function (m, n) {const dp = new Array(n).fill(1);for (let i = 1; i < m; i++) {for (let j = 1; j < n; j++) {dp[j] = dp[j - 1] + dp[j];}}return dp[n - 1];};
复杂度分析
时间复杂度:
空间复杂度:
详解
其实这是个高中数学问题。因为机器人只能向右或者向下移动,那么不论有多少中路径,向右和向下走的步数都是一样的。当 时,机器人向下走了一步,向右走了两步即可到达终点。所以我们可以得到
路径 = 从右边开始走的路径总数 + 从下边开始走的路径总数,转化为排列组合问题
不包括起点和终点,共移动 ,向右移动,将 和 代入上述公式,可得
因此得出答案
/*** @param {number} m* @param {number} n* @return {number}*/const uniquePaths = function (m, n) {const N = m + n - 2;const K = n - 1;let num = 1;for (let i = 1; i <= K; i++) {num = num * (N - K + i) / i;}return num;};
复杂度分析
时间复杂度:
空间复杂度:
给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例
输入: [10,9,2,5,3,7,101,18]输出: 4解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
思路
状态定义:res[i] 表示以 nums[i] 为当前最长递增子序列尾元素的长度
转移方程:通过方程 res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1),动态计算出各上升子序列的长度。
倒序取值:res 数组进行倒序,第一个即为最大长度的值。
详解
如果给定数组长度小于等于 1,则最长上升子序列的长度等于数组长度。
初始化一个长度等于给定数组的长度,且元素都为 1 的数组 res。
当 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),通过转移方程收集
各上升子序列的长度。
通过 sort 函数对 res 倒序排列,第一元素值 res[0] 就是最长的上升子序列长度。
/*** @param {number[]} nums* @return {number}*/const lengthOfLIS = function (nums) {const len = nums.length;if (len <= 1) {return len;}// 初始化默认全为1const res = new Array(len).fill(1);for (let i = 1; i < len; i++) {for (let j = 0; j < i; j++) {// 转移方程res[i] = Math.max(res[i], nums[i] > nums[j] ? res[j] + 1 : 1);}}// 倒序res.sort((a, b) => b - a);return res[0];};
复杂度分析
时间复杂度:
空间复杂度:
思路
当前遍历元素大于前一个递增子序列的尾元素时(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 即为最长的上升子序列长度。
/*** @param {number[]} nums* @return {number}*/const lengthOfLIS = function (nums) {const len = nums.length;if (len <= 1) {return len;}const tail = new Array(len);tail[0] = nums[0];let end = 0;for (let i = 1; i < len; i++) {if (nums[i] > tail[end]) {end += 1;tail[end] = nums[i];} else {let left = 0;let right = end;// 二分查找while (left < right) {// 位运算,右移一位const mid = left + ((right - left) >> 1);if (tail[mid] < nums[i]) {left = mid + 1;} else {right = mid;}}tail[left] = nums[i];}}return end + 1;};
复杂度分析
时间复杂度:
外层一个数组循环遍历,里面嵌套一个二分查找,所以是
空间复杂度:
创建的数组 tail 占用空间大小为 n,循环遍历中并没有分配新的空间
示例
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明:
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
注意你可以重复使用字典中的单词。
示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"]输出: true解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2:
输入: s = "applepenapple", wordDict = ["apple", "pen"]输出: true解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
示例 3:
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]输出: false
思路
把字符串 s
的前缀从短到长拆出来进行判断是否在单词字典中,若在字典中则把前缀截取掉继续递归,直到字符串的长度为 0。在递归中若遇到字符串任何长度的前缀都无法匹配到字典中的单词,则回溯到上层递归。
详解
1、检查字典中是否有字符串的前缀; 2、若有的话,将字符串去掉这个前缀后继续遍历,重复步骤 1、2; 3、若某次调用发现整个字符串都已拆分并且都在字典内则返回 true;
const wordBreak = function (s, wordDict) {if (s.length === 0) {return true;}for (let i = 0; i < wordDict.length; i += 1) {const startIndex = s.indexOf(wordDict[i]);if (startIndex === 0) {// 将字符串去掉这个匹配到的前缀后继续遍历const temp = s.slice(startIndex + wordDict[i].length);if (wordBreak(temp, wordDict) === true) {return true;}}}return false;};
时间复杂度:最坏情况下是 ,因为考虑 s = 'aaaaaaaaaaaaaaaa', wordDict = ['a']
,每一个字符都在字典中,此时递归的时间复杂度会达到 ,妥妥超时
空间复杂度:,循环中申请了 3 个临时变量,与输入的字符串的长度无关,空间占用属于常数阶,故空间复杂度为 。
思路
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
,则说明字符可由字段中的单词组合而成;
代码
const wordBreak = function (s, wordDict) {const len = s.length;const dp = new Array(len + 1).fill(false);dp[0] = true;for (let i = 1; i <= len; i++) {for (let j = 0; j < i; j++) {if (dp[j] && wordDict.includes(s.substring(j, i))) {dp[i] = true;break;}}}return dp[len];};
复杂度分析
时间复杂度:
因为有两层循环,每层循环都从头遍历到尾。
空间复杂度:
因为只开辟了一个 长度的数组。
思路
第二层遍历中不用每次遍历 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
,则说明字符可由字段中的单词组合而成;
const wordBreak = function (s, wordDict) {const len = s.length;const dp = new Array(len + 1).fill(false);dp[0] = true;// 计算单词的最长长度let maxStep = 0;for (let i = 0; i < wordDict.length; i++) {if (wordDict[i].length > maxStep) {maxStep = wordDict[i].length;}}for (let i = 1; i <= len; i++) {const startOfJ = i - maxStep > 0 ? i - maxStep : 0;for (let j = startOfJ; j < i; j++) {if (dp[j] && wordDict.includes(s.substring(j, i))) {dp[i] = true;break;}}}return dp[len];};
复杂度分析
时间复杂度:
因为有两层循环,每层循环都从头遍历到尾。
空间复杂度:
因为最长只开辟了一个 长度的数组。