javascript-leetcode
javascript-leetcode copied to clipboard
Geekhyt
LeetCode 题解仓库🍖
[原题链接](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...
[原题链接](https://leetcode-cn.com/problems/minimum-path-sum/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-sr4g/) ## 状态定义 `dp[i][j]` 代表从 (0, 0) 走到 (i, j) 的最小路径和。 ## 状态转移方程 明确题意：只能向右或者向下走，也就是说终点 (i, j) 只能从 (i - 1, j) 或者 (i, j - 1) 走过来。 分为以下三种情况分别处理： 1. 左边或者上边都是边界时，终点也就是起点。...
[原题链接](https://leetcode-cn.com/problems/unique-paths/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-48a3/) # 动态规划 ## 定义状态 先明确题意，机器人只能选择向下或者向右走。 使用`dp[i][j]`来表示终点坐标(i, j)。 - 向下走: `dp[i-1][j]` - 向右走: `dp[i][j-1]` ## 状态转移方程 `dp[i][j] = dp[i-1][j] + dp[i][j-1]` ## 处理边界 - i 和 j 分别等于 0 时，不满足要求需要被忽略。...