童欧巴

[原题链接](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...

[原题链接](https://leetcode-cn.com/problems/reverse-string/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-ms3n/) 先明确题目要求： > 不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 ```javascript const reverseString = function(s) { s.reverse() } ``` 这道题可不是为了考察我们是否知道 `reverse()` 这个 API，我们来看不借助内置方法如何解题。 ## 双指针 1. 借助双指针left、right分别指向头尾。 2. 两个指针不断夹逼，进行交换位置完成反转。 ```javascript const reverseString = function...

[原题链接](https://leetcode-cn.com/problems/add-strings/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-k9n0/) 1. 模拟加法，先补 0 对齐。 2. 从右往左做加法，计算当前位 +num1[i] + +num2[i] + carry，使用 + 号将字符转换成数字。 3. 当前位：模10的结果 + res字符串。 4. carry 代表是否进位。 5. 如果 carry 等于 1，需要在 res 前添加 '1'。 ```js...

[原题链接](https://leetcode-cn.com/problems/climbing-stairs/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-u76p/) 虽然动态规划的最终版本 (降维再去维) 大都不是递归，但解题的过程还是离不开递归的。 如果你觉得你对递归理解的还不够透彻，请移步我的这篇专栏[你真的懂递归吗？](https://juejin.cn/post/6844904161872461831) 新手可能会觉得动态规划思想接受起来比较难，确实，动态规划求解问题的过程不太符合人类常规的思维方式，我们需要切换成机器思维。 使用动态规划思想解题，首先要明确动态规划的三要素。 ## 动态规划三要素 - 重叠子问题 - 最优子结构 - 状态转移方程 ### 重叠子问题 切换机器思维，自底向上思考。 爬第 n 阶楼梯的方法数量，等于两部分之和： - 爬上 n-1 阶楼梯的方法数量 - 爬上 n-2 阶楼梯的方法数量 ###...

[原题链接](https://leetcode-cn.com/problems/house-robber/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-nd0q/) > 先明确题意，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警，所以我们得隔着偷。 ## 最优子结构 从 n 个房子中能偷到的最大金额，f(n)。 1. 偷前 n - 1 间房子，最后一间房子不偷 2. 偷前 n - 2 间房子和最后一间房子 ## 状态转移方程 `Math.max(dp[i - 1], dp[i - 2] + nums[i...

[原题连接](https://leetcode-cn.com/problems/longest-palindromic-substring/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-cifm/) > 如果一个字符串 aba 是一个回文串，那么在它的左右分别添加一个相同的字符 a，那么它一定还是一个回文串 aabaa。 我们可以用 `dp[i][j]` 表示 s 中从 i 到 j (包括 i 和 j) 是否可以形成回文串，将上面这段话翻译成代码，列出状态转移方程。 - dp[i][j] === true 是回文串 - dp[i][j] === false 不是回文串...

[原题链接](https://leetcode-cn.com/problems/maximum-subarray/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-xep3/) ## 动态规划 遍历数组，以当前遍历到的每一个点为终点来计算当前子序列的最大和，每一个点的结果都是基于前一个点的最大子序列和计算得出的。 ### 状态转移方程 `res[i] = Math.max(res[i - 1] + cur[i], cur[i])` - cur: 当前最大连续子序和 - res: 最终结果 ```javascript const maxSubArray = function(nums) { const len = nums.length...

[原题链接](https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/qian-duan-shi-tang-ti-jie-dptan-xin-er-f-uzs0/) ### 什么是上升子序列？ 首先，我们需要对基本的概念进行了解和区分： - 子串：一定是连续的 - 子序列：子序列不要求连续 例如：[6, 9, 12] 是 [1, 3, 6, 8, 9, 10, 12] 的一个子序列 - 上升/递增子序列：一定是严格上升/递增的子序列 `注意：子序列中元素的相对顺序必须保持在原始数组中的相对顺序` ## 题解 ### 动态规划 关于动态规划的思想，还不了解的同学们可以移步我的这篇专栏入个门，[「算法思想」分治、动态规划、回溯、贪心一锅炖](https://juejin.im/post/6844904190578278414#heading-3) 我们可以将状态 `dp[i]`...

[原题链接](https://leetcode-cn.com/problems/longest-valid-parentheses/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-sfti/) ## 子问题 dp[i]: 表示以 s[i] 结尾的最长有效括号长度。 ## 状态转移方程 分情况讨论出所有可能：  `s[i] 可能为 '(' 或者 ')'`： 1. `s[i] === '('` 时，不可能组成有效的括号，所以 dp[i] = 0。 2. `s[i] === ')'` 时，需要查看 s[i...