javascript-leetcode
javascript-leetcode copied to clipboard
Geekhyt
LeetCode 题解仓库🍖
[原题链接](https://leetcode-cn.com/problems/assign-cookies/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-8zmp/) ## 贪心算法+双指针 1. 给一个孩子的饼干应当尽量小并且能满足孩子，大的留来满足胃口大的孩子。 2. 因为胃口小的孩子最容易得到满足，所以优先满足胃口小的孩子需求。 3. 按照从小到大的顺序使用饼干尝试是否可满足某个孩子。 4. 当饼干 j >= 胃口 i 时，饼干满足胃口，更新满足的孩子数并移动指针 `gi++ sj++ res++`。 5. 当饼干 j < 胃口 i 时，饼干不能满足胃口，需要换大的 `sj++`。 ## 关键点 将需求因子...
[原题链接](https://leetcode-cn.com/problems/lemonade-change/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-wmie/) ## 贪心 这道题的场景和几年前的我们现实生活中很像，毕竟 2021 年的现在大家都用手机支付了，不过也刚好怀旧一波。 先明确，题目要求我们一开始是没有钱的，全靠老天爷赏饭吃。`江山父老能容我 不使人间造孽钱` 所以，分为 3 种情况来进行分析： 1. 顾客支付了 5 美元： 直接收下，不用找。 2. 顾客支付了 10 美元： 需要找回 5 元。 3. 顾客支付了 20 美元：需要找回 15元。有两种组合情况，一种是有一张 10 元和一张...
[原题链接](https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-vg7h/) ## 回溯法 使用回溯法进行求解，回溯是一种通过穷举所有可能情况来找到所有解的算法。 如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。 `究其本质，其实就是枚举。` 如果没有更多的数字需要被输入，说明当前的组合已经产生。 如果还有数字需要被输入： - 遍历下一个数字所对应的所有映射的字母。 - 将当前的字母添加到组合最后，也就是 `str + tmp[r]` 。 ```javascript const letterCombinations = function (digits) { if (!digits) { return [] } const...
[原题链接](https://leetcode-cn.com/problems/generate-parentheses/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-gocw/) ## 回溯法 题目要求我们生成所有可能的有效的括号组合，数字 n 代表生成括号的对数。 使用回溯法进行解题，从空字符串开始构造，做加法。 1. 当 l < r 时(构造用的左括号 < 构造用的右括号)，不满足条件，直接剪枝。 2. 当 l < n 时，可以一直插入左括号，最多插入 n 个。 3. 当 r < l (构造用的右括号 <...
[原题链接](https://leetcode-cn.com/problems/permutations/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-e1a4/) ## 回溯法 题目要求我们返回所有可能的全排列，我们就要考虑到所有的情况，可以使用回溯法解题。 回溯法的本质是枚举，并且还可以通过剪枝少走一些冤枉路。 `回溯：一条路走到黑，手握后悔药，可以无数次重来。(英雄联盟艾克大招无冷却)。` 关键点：在递归之前做选择，在递归之后撤销选择。 1. 借助 deepStack 栈暂存每一种枚举的可能情况。 2. 开启遍历枚举，已经选择过的数字不能再做选择。 3. 在递归之前做选择，在递归之后需要撤销选择，恢复状态。 4. 完成所有遍历时，将 deepStack 存入结果集 res。 ```javascript const permute = function(nums) { const len = nums.length,...
[原题链接](https://leetcode-cn.com/problems/combination-sum/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-ls45/) ## 回溯 先明确，元素可以重复使用，但是组合不能重复。 1. 使用回溯法，不符合条件的情况进行剪枝。 2. 当 `cur === target` 时，拷贝 arr 推进结果集。 3. 从 start 开始遍历可选数组，选择当前数字后递归时注意要基于当前状态 i 继续选择，因为元素是可以重复进入集合的。 4. 撤销选择，恢复状态。 ```js const combinationSum = (candidates, target) => {...
[原题链接](https://leetcode-cn.com/problems/combination-sum-ii/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-5eio/) ## 回溯 本题在 [39.组合总和](https://leetcode-cn.com/problems/combination-sum/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-ls45/) 题的基础上加了1个限制条件：元素不可以重复使用了。 解题思路还是和 39 题一样，只需要在代码中改动如下几点即可： 1. 题目要求元素不能重复，需要去重，去重就要排序，因为排序后去重更方便。 2. 在枚举过程中，遇到重复项直接跳过。 3. 递归时改成 `i + 1`，避免与当前 i 重复。 ```js const combinationSum2 = (candidates, target) => { candidates.sort((a, b)...
[原题链接](https://leetcode-cn.com/problems/combinations/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-fjzc/) ## 回溯 使用回溯法进行解题，在回溯的常规操作下注意以下两点： 1. 每次递归当选满 k 个数时，将其推入最终集合。 2. 回溯的过程中为了避免产生重复的组合，需要剪枝，通过指定下次递归的选择范围是 `i + 1` 来进行剪枝。 ```js const combine = function(n, k) { const res = [] const helper = function(start, cur)...
[原题链接](https://leetcode-cn.com/problems/subsets/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-h1wz/) ## 回溯 `你爱，或者不爱我。爱就在那里，不增不减。` 1. 对于数组中的每个元素都有两种选择：选或者不选。 2. 对于当前迭代的元素，选择它就将其 push 后，基于选择后的状态从 `start + 1` 递归。 3. 然后使用 pop 将其状态恢复，不选择当前迭代的元素从 `start + 1` 递归。 ```javascript const subsets = function(nums) => { const...
[原题链接](https://leetcode-cn.com/problems/valid-palindrome/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-w2fr/) ## 双指针 先明确题意，题目要求只考虑字母和数字字符，并且可以忽略大小写。 1.首先用正则去掉字符串中不是字母和数字的元素，并且都转换成小写。 2.借助双指针 left， right 进行夹逼比较。 3.如果 s[left] 和 s[right] 每一项都相等，则是回文串，否则就不是回文串。 ```javascript const isPalindrome = function (s) { s = s.replace(/[^0-9a-zA-Z]/g, '').toLowerCase() let n = s.length, left...