?主页详情：一名不会打字的程序员~的个人主页
?作者简介：?物联网领域创作者? and ?阿里专家博主? and ?华为云享专家?
✍️人生格言：最慢的步伐不是跬步，而是徘徊；最快的脚步不是冲刺，而是坚持。
??人生目标：成为一名合格的程序员，做未完成的梦：实现财富自由。
?技术方向：NULL
?如果觉得博主的文章还不错的话，请三连支持一下博主哦
?给大家介绍一个我一直在用的求职刷题收割offe?点击进入网站
文章目录
零钱兑换解法一 动态规划法解法二 递归 跳跃游戏方法一 贪心算法方法二 动态规划方法三 回溯 不同路径、Longest Increasing Subsequence和单词拆分不同路径思路方法一 递归方法二 动态规划方法三 动态规划优化方法四 排列组合 Longest Increasing Subsequence方法一 动态规划方法二 二分查找 单词拆分方法一 暴力破解法方法二 动态规划方法三 动态规划（优化版）
零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例1
输入: coins = [1, 2, 5], amount = 11输出: 3 解释: 11 = 5 + 5 + 1示例2
输入: coins = [2], amount = 3输出: -1解法一 动态规划法
思路
由于需要找到最少的硬币，所以需要列举出所有可能的结果（如题）
要凑够 amount 元硬币，可以从最 i -> amount 之前进行枚举 (counter) (下列出 最少次数)
amount = 1； counter[1] = 1 coins[1] = 1
amount = 2； counter[2] = 1 coins[2] = 2
amount = 3； counter[3] = 2 coins[1] + coins[2]
amount = 4； counter[4] = 2 coins[2] + coins[2]
amount = 5； counter[5] = 3 coins[2] + coins[2] + coins[1]
amount = 6； counter[6] = 3 coins[2] + coins[2] + coins[2]
amount = 7； counter[7] = 2 coins[5] + coins[2]
amount = 8； counter[8] = 3 coins[5] + coins[2] + coins[1]
amount = 9； counter[9] = 3 coins[5] + coins[2] + coins[2]
amount = 10； counter[10] = 2 coins[5] + coins[5]
amount = 11； counter[11] = 1 coins[5] + coins[5] + coins[1]
递增 i 并且记录下 能组合成 i 的 硬币数量 counter[i]
遍历 coins 数组，从 counter 中找到对应剩余金额（i - coins[j]）的最小次数 + 1
详解
需要计算出每一步的最佳次数，因此可以将每一步的次数保存在 counter 数组中counter中每一项的最大值应该是 amount / 1 次，此处默认填充 (amount / 1) + 1 次遍历amoount 数组 依次递增，在 coins 数组中找到满足 i 的最少硬币数，保存在 counter 中若 counter[i] 已经保存有最少的值，比较此次计算的最小次数，取两者较小重复 3，4 步骤 直到 amount 遍历结束const coinChange = (coins, amount) => { const counter = Array(amount + 1); counter.fill(amount + 1); counter[0] = 0; for (let i = 1; i <= amount; i ++) { for (let j = 0; j < coins.length; j ++) { if (i - coins[j] >= 0) { // i - coins[j] 能凑成 i 的上一步的 最小硬币数量 counter[i] = Math.min(counter[i], counter[i - coins[j]] + 1); } } } // 最坏结果应该是 counter[amount] = amount return counter[amount] > amount ? -1 : counter[amount];}复杂度分析
时间复杂度：O(Sn)O(Sn)
时间复杂度是 O(Sn)O(Sn)，S是 amount大小,需要迭代 Sn次
空间复杂度：O(S)O(S)
每次迭代时没有增加新的资源，O(1)O(1)
解法二 递归
思路
由于要获取最小奖金币次数，实质上就是能拿到的满足 amount 的面值尽可能大的银币的个数。例如：
coins = [11, 12, 5, 3] amount = 121;
则次数刚好是 121 / 11 = 11，其他的取法均大于 11 次。
若 amount = 124 则有次数 (121 / 11) + (3 / 3) = 12次
另外，在考虑最多次数时，应当满足有 amount / 1 = amount 次。
详解
amount 是总金额，要用最少的硬币数，应当是从最大的硬币开始拿起大的硬币可以多次拿取，就有 amount % coins[i] === 0 成立可以保存一个最少硬币数 mincounter 的状态，按coins数组最大的开始，依次向最小的硬币循环按照可以使用的最大硬币次数作为循环起始条件，依次减1直至为0，递归调用当剩余 amount / coins[n] > 当前次数 + mincounter 则直接退出循环当amount为0时，即可得到最优结果const coinChange = (coins, amount) => { // 假设 最少次数 最多不会超过 amount 次 let minCount = amount + 1; let coinsTemp = coins.sort((a, b) => b - a); // 防止有超过 amount 面值的硬币出现 const maxValueIndex = coinsTemp.findIndex(v => v <= amount); // 已经计算的次数，剩余的金额，coins，当前硬币位置 const calculateCountes = (count, amount, coins, index) => { if (amount === 0) { if (count < minCount) { // 每次递归的所有可能结果进行保存 minCount = count; } return; } let maxCountatIndex = parseInt((amount / coins[index]), 10); // 执行到超出数组边界 或者 预计最小次数大于已有 minCount 时 直接退出递归 if((index === coins.length) || maxCountatIndex + count >= minCount) { return; } // amount 最少是 amount / coins[index] 次 coins[index] 的 和 for (let j = maxCountatIndex; j >= 0 ; j --) { // 累计次数，剩余amount，银币数组，到达的coins数组下标 calculateCountes(count + j, amount - (coins[index] * j), coins, index + 1 ); } } calculateCountes(0, amount, coinsTemp, maxValueIndex); return minCount === amount + 1 ? -1 : minCount;}复杂度分析
时间复杂度：O(Sn)O(Sn)
空间复杂度：O(n)O(n)
nn 为递归调用的最大深度，即需要 O(n)O(n) 空间的递归堆栈。
跳跃游戏
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
示例1:
输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
示例2:
输入: [3,2,1,0,4] 输出: false 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
方法一 贪心算法
思路
贪心算法的思路就是每到一个位置，都跳跃到当前位置可以跳跃的最大距离。当最后跳跃的最远距离等于或大于最后一个位置的时候，我们就认为可以到达最后一个位置，返回true
详解
首先我们初始化最远位置为0，然后遍历数组；如果当前位置能到达，并且当前位置+跳数>最远位置，就更新最远位置；每次都去比较当前最远位置和当前数组下标，如果最远距离小于等于当前下标就返回false。const canJump = function (nums) { let max = 0; // 跳到最远的距离 for (let i = 0; i < nums.length - 1; i += 1) { // 找到能跳的最远的的距离 if (i + nums[i] > max) { max = i + nums[i]; } // 如果跳的最远的小于当前脚标，返回false if (max <= i) { return false; } } return true;};复杂度分析
时间复杂度：O(n)O(n)
只需要访问 nums 数组一遍，共 nn 个位置，nn 是 numsnums 数组的长度。
空间复杂度：O(1)O(1)
在 max 变量分配内存情况下，内存不会随着遍历有增长趋势，不需要额外的空间开销。
方法二 动态规划
思路
我们遍历数组，每到一个点 i，我们就去判断是否可以到达当前点；如果可以，就记录 true，否则为false，最后判断 是否可以到达(nums.length - 1)；
详解
遍历数组 nums，每到一个点 i，我们就判断时刻可以到达当前点；如果 i 之前某点 j 本身是可以到达的，并且与当前点可达，表示点 i 是可达的；我们遍完成后，直接判断(nums.length - 1)是否可以达到。const canJump = function (nums) { // 定义一个数组，用来记录nums的点是否是可以达到的 const list = [nums.length]; // 遍历nums for (let i = 1; i < nums.length; i++) { // 遍历list for (let j = 0; j < i; j++) { // 如果j点是可以到达的，并且j点是可以达到i点的 // 则表示i点也是可以达到的 if (list[j] && nums[j] + j >= i) { list[i] = true; // 如果i点可以达到，则跳出当前循环 break; } } } return list[nums.length - 1];};复杂度分析
时间复杂度：O(n^2)O(n2) 对于每个元素，通过两次遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n^2)O(n2) 的时间空间复杂度：O(n)O(n) 对于每次循环都需要给 j 重新分配空间，所以空间复杂度 O(n)O(n)方法三 回溯
思路
我们模拟从第一个位置跳到最后位置的所有方案。从第一个位置开始，模拟所有可以跳到的位置，然后判断当前点是否可以到达(nums.length - 1);当没有办法继续跳的时候，就回溯。
详解
我们每次传入一个下标 p，并且判断 p 是否可以达到最后的下标；如果传入的 p 等于(nums.length - 1),则表示可以到达，如果不行，则继续循环判断；如果存在 p 等于 (nums.length - 1)，则返回true，不存在则返回 false。 const canJump = function (nums) { return checkJumpPosition(0, nums); ;};function checkJumpPosition (p, nums = []) { // 定义p点可以到达的最远距离 let jump = p + nums[p]; // 如果p点可以到达nums.length - 1，则返回true if (p === nums.length - 1) { return true; } // 如果最远距离大于(nums.length - 1),我们就将(nums.length - 1),设为最远距离 if (p + nums[p] > nums.length - 1) { jump = nums.length - 1; } // 我们从p + 1开始到最远距离中间，找到(nums.length - 1) // 如果可以，则返回true，找不到则返回false for (let i = p + 1; i <= jump; i += 1) { if (checkJumpPosition(i, nums)) { return true; } } return false;}复杂度分析
时间复杂度：O(2^n)O(2n) 因为从第一个位置到最后一个位置的跳跃方式最多有 2^n 种，所以最多的耗时是 O(2^n)O(2n)空间复杂度：O(n)O(n) 对于每次循环都需要给 ii 重新分配空间，最大的长度是nums.length，所以空间复杂度 O(n)O(n) 不同路径、Longest Increasing Subsequence和单词拆分
不同路径
一个机器人位于一个 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从点 (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 m = 1 m=1 或 n = 1 n = 1 n=1 时（只能一直往下或往右走），路径数量为1，这里得出跳出递归的条件。
方法一 递归
详解
由上面的分析可得，到达 (m, n)(m,n)的路径数量为 (m, n-1)(m,n−1)坐标的路径数量与 (m-1, n)(m−1,n)坐标的路径数量之和 。可以使用最简单粗暴的递归方法
代码
/** * @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);};方法二 动态规划
详解
根据以上思路，可以推出状态转移方程为
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 |
代码
/** * @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];};复杂度分析
时间复杂度： O(m * n)O(m∗n)上述解法中，对 mm 和 nn 进行了双重循环，时间复杂度跟数字的个数线性相关，即为 O(m*n)O(m∗n)
空间复杂度： O(m * n)O(m∗n)申请了大小为 m * nm∗n的二维数组
方法三 动态规划优化
减少空间复杂度
详解
我们观察表格发现，下一个值等于当前值加上一行的值，利用这个发现，可以来压缩空间，用一维数组来实现
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];};复杂度分析
时间复杂度： O(m * n)O(m∗n)空间复杂度：O(n)O(n)方法四 排列组合
详解
其实这是个高中数学问题。因为机器人只能向右或者向下移动，那么不论有多少中路径，向右和向下走的步数都是一样的。当 m = 3，n = 2 m=3，n=2 时，机器人向下走了一步，向右走了两步即可到达终点。所以我们可以得到
路径 = 从右边开始走的路径总数 + 从下边开始走的路径总数，转化为排列组合问题
不包括起点和终点，共移动 N = m + n - 2N=m+n−2，向右移动K = m - 1K=m−1，将 NN 和 KK 代入上述公式，可得
因此得出答案 C_{m + n -2}^{m - 1}Cm+n−2m−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;};复杂度分析
时间复杂度：O(n)O(n)空间复杂度：O(1)O(1)Longest Increasing Subsequence
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例
输入: [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; } // 初始化默认全为1 const 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];};复杂度分析
时间复杂度：O(n^2)O(n2)空间复杂度：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 即为最长的上升子序列长度。
/** * @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;};复杂度分析
时间复杂度：O(nlogN)O(nlogN)
外层一个数组循环遍历，里面嵌套一个二分查找，所以是 O(nlogN)O(nlogN)
空间复杂度：O(n)O(n)
创建的数组 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；
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-21YkVzx9-1659870334689)(https://3811097299-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5_VgO7Aapcy5begC-C%2F-M6-I6m57X_LoOQxykgn%2F-M6-IbJwjVrcOtj76ywA%2Fimage.png?alt=media&token=e18dc987-f918-4880-9248-68395d352aea)]
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']，每一个字符都在字典中，此时递归的时间复杂度会达到 O(n^n) O(nn)，妥妥超时空间复杂度：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，则说明字符可由字段中的单词组合而成；
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CoPFRWQl-1659870334693)(https://3811097299-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M5_VgO7Aapcy5begC-C%2F-M6-I6m57X_LoOQxykgn%2F-M6-Ie1OD-shJ9PPcnsE%2Fimage.png?alt=media&token=0d6c4555-cbba-48e9-8f4c-30565a75e7a8)]
代码
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];};复杂度分析
时间复杂度：O(n^2)O(n2)
因为有两层循环，每层循环都从头遍历到尾。
空间复杂度：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，则说明字符可由字段中的单词组合而成；
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];};复杂度分析
时间复杂度：O(n^2)O(n2)
因为有两层循环，每层循环都从头遍历到尾。
空间复杂度：O(n)O(n)
因为最长只开辟了一个 nn 长度的数组。