javascript-leetcode
javascript-leetcode copied to clipboard
Geekhyt
LeetCode 题解仓库🍖
[原题链接](https://leetcode-cn.com/problems/maximal-square/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-pwzp/) ## 状态转移方程 定义 dp[i][j]：以坐标 (i,j) 为右下角的最大正方形边长。 - (i,j) 为 0 时，无法构成正方形，`dp[i][j] = 0` - (i,j) 为 1 时，`dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j -...
[原题链接](https://leetcode-cn.com/problems/edit-distance/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-9lli/) ## 状态定义 定义 dp[i][j]：word1 的前 i 个字符和 word2 的前 j 个字符的编辑距离。 更通俗的说，就是 word1 的前 i 个字符，变成 word2 的前 j 个字符，最少需要多少步。 把大象放进冰箱需要几步？ ：） 举个例子： `word1 = "horse", word2 = "ros"`...
[原题链接](https://leetcode-cn.com/problems/coin-change/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-erm2/) > 题目仅要求出最少硬币数量，无须考虑硬币的组合和排列，所以不用考虑两个 for 循环的内外顺序。 ## 状态定义 dp[i]：凑足总额为 i 所需钱币的最少个数为 dp[i] ## 状态转移方程 `dp[i] = min(dp[j - coins[j]] + 1, dp[i])` ### 理解 不考虑第 j 个硬币时， 硬币数为 `dp[i]` 考虑第 j...
[原题链接](https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-myw2/) ## 状态定义 dp[i]：表示以 nums[i] 为结尾的连续子数组最大和。 ## 状态转移方程 连续子数组则必须包含 nums[i]，否则不符合题意。 当 `dp[i - 1] > 0` 时，`dp[i] = dp[i - 1] + nums[i]`，当 `dp[i - 1] res) { res =...
[原题链接](https://leetcode-cn.com/problems/word-break/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-3pkf/) ## 状态定义 `dp[i]`: 字符串 s 的前 i 个字符子串 `s[0..i-1]` 是否由单词表组成。 ## 状态转移方程 `dp[i] = dp[j] && check(s[j..i-1])` - 使用 j 对字符串进行分割，分割成 `[0..j-1]` (dp[j]) 和 `[j, i-1]`。 - `check(s[j..i-1])`：代表子串 `s[j..i-1]`...
[原题链接](https://leetcode-cn.com/problems/super-egg-drop/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-399v/) > 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。 > 已知存在楼层 f ，满足 0 0; i--) { dp[i] = dp[i] + dp[i - 1] + 1 } }...
[原题链接](https://leetcode-cn.com/problems/perfect-squares/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-ct3e/) ## 状态定义 `dp[i]`: 和为 i 的完全平方数的最少数量 ## 状态转移方程 `dp[i] = Math.min(dp[i], i - j * j + 1)` `dp[i]` 可以由 `dp[i - j * j] + 1` 推出，取二者中较小者。 ##...
1. [买卖股票的最佳时机](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-gpb4/) 2. [买卖股票的最佳时机II](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-s2hw/) 3. [买卖股票的最佳时机III](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-ku4r/) 4. [买卖股票的最佳时机 IV](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-wugy/) 5. [最佳买卖股票时机含冷冻期](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-o5yd/) 6. [买卖股票的最佳时机含手续费](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-hsc7/) 上面这 6 道题目可以归为一道题目来看，与现实略有不同，题目中添加了一些限制条件，读完题分析后不难发现。 1. 第一题只交易一次，也就是 k = 1。 2. 第二题不限制交易次数，也就是 k = +infinity。 3. 第三题只交易两次，也就是 k =...
 堆排序相比其他几种排序代码会有些复杂，不过没关系，我们先来看一些前置知识，可以帮助我们更好的理解堆排序。 堆排序顾名思义就是要利用堆这种数据结构进行排序。`堆是一种特殊的树，满足以下两点就是堆：` 1. 堆是一个完全二叉树 2. 堆中每一个节点的值都必须大于等于(或小于等于)其子树中的每个节点的值 每个节点的值都大于等于子树中每个节点值的堆，叫做`大顶堆`，每个节点的值都小于等于子树中每个节点值的堆，叫做`小顶堆`。 也就是说，`大顶堆中，根节点是堆中最大的元素。小顶堆中，根节点是堆中最小的元素`。 如果你对树这种数据结构还不是很了解，可以移步我的这篇专栏[“树”业有专攻](https://juejin.cn/post/6844904199050756110#heading-3) `堆如果用一个数组表示的话，给定一个节点的下标 i (i从1开始)，那么它的父节点一定为 A[i / 2]，左子节点为 A[2i]，右子节点为 A[2i + 1]。` > 堆排序包含两个过程，建堆和排序。首先构建一个大顶堆，也就是将最大值存储在根节点(i = 1)，每次取大顶堆的根节点与堆的最后一个节点进行交换，此时最大值放入了有效序列的最后一位，并且有效序列减 1，有效堆依然保持完全二叉树的结构，然后进行堆化成为新的大顶堆。重复此操作，直到有效堆的长度为 0，排序完成。 ```js const heapSort =...
[快速排序可视化视频](https://www.reddit.com/r/dataisbeautiful/comments/e9fb2k/oc_quicksort_visualization/) 快速排序也是分治法的应用，`处理过程是由上到下的，先分区，然后再处理子问题。` `快速排序通过遍历数组，将待排序元素分隔成独立的两部分，一部分记录的元素均比另一部分的元素小，则可以分别对这两部分记录的元素继续进行排序，直到排序完成。` 这就需要从数组中挑选出一个元素作为 `基准(pivot)`，然后重新排序数列，将元素比基准值小的放到基准前面，比基准值大的放到基准后面。 然后将小于基准值的子数组(left)和大于基准值的子数组(right)递归地调用 quick 方法，直到排序完成。 ```js const quickSort = function(arr) { const quick = function(arr) { if (arr.length > 1) const pivot = arr.splice(index, 1)[0] const left...