javascript-leetcode
javascript-leetcode copied to clipboard
Geekhyt
LeetCode 题解仓库🍖
[原题链接](https://leetcode-cn.com/problems/container-with-most-water/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-53jo/) 虽然是中等难度，但这道题解起来还是比较简单的，老规矩，我们看下符合第一直觉的暴力法： ## 暴力法 幼儿园数学题：矩形面积 = 长 * 宽 放到我们这道题中，矩形的长和宽就分别对应： - 长：两条垂直线的距离 - 宽：两条垂直线中较短的一条的长度 双重 for 循环遍历所有可能，记录最大值。 ```js const maxArea = function(height) { let max = 0 // 最大容纳水量 for...
[原题链接](https://leetcode-cn.com/problems/3sum/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-wl4o/) 先明确，题目不仅是要求 a + b + c = 0，而且需要三个元素都不重复。 所以我们可以先将数组从小到大排序，排序后，去除重复项会更加简单。 1.外层循环指针 i 遍历数组，题目要求三数之和为 0，考虑此次循环中的数若大于 0，另外两个数肯定也大于 0，则当前位置下无解。 2.去重，如果当前元素和前一个元素相同时，直接跳过即可。 3.内层循环借助双指针夹逼求解，两个指针收缩时也要去除重复的位置。 4.三数之和为 0 时，将当前三个指针位置的数字推入数组即所求。若当前和小于 0 则将左指针向右移动，若当前和大于 0 则将右指针向左移动。 ```js const threeSum = function(nums)...
[原题链接](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-a55b/) ## 双指针 题目要求原地删除重复出现的元素，不要使用额外的数组空间，返回移除后数组的新长度。 `先明确，这道题给我们提供的是排好序的数组，所以重复的元素必然相邻。` `所以实际上我们只需要将不重复的元素移到数组的左侧，并返回其对应的长度即可。` 1.借助双指针，i 从索引 0 开始，j 从索引 1 开始。 2.当前项 nums[j] 与前一位置 nums[j - 1] 相等时，j++ 跳过重复项。 3.当二者不相等时，意味着不是重复项，此时需要将 i 指针右移， 并将 nums[j] 复制到此时的 nums[i] 位置上，然后将指针 j...
[原题链接](https://leetcode-cn.com/problems/plus-one/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-duz4/) 加一，其实就是小学数学题，很简单，我们逐步来分析。 `数字 9 加 1 会进位，其他的数字不会。` 所以，情况无非下面这几种： 1. 1 + 1 = 2 末位无进位，则末位加 1 即可。 2. 299 + 1 = 300 末位有进位，首位加 1。 3. 999 + 1 =...
[原题链接](https://leetcode-cn.com/problems/move-zeroes/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-2jpr/) ## 双指针 题目要求将所有 0 移动到数组的末尾，同时还要保持非零元素的相对顺序。 在此基础上附加了两个条件： 1.必须在原数组上操作，不能拷贝额外的数组。 2.尽量减少操作次数。 我们可以借助双指针来进行求解，求解过程如下： 1.初始化双指针 i 、j 指向数组头部索引 0。 2.将 i 指针不断向右移动，j 指针负责提供交换的位置，当遇到非 0 数字时，将两个指针位置的数字交换，同时继续向右边移动两个指针。这样交换可以保证题目要求的非 0 数字相对顺序不变。 3.当遇到 0 时，向右移动 i 指针，j 指针不动。 4.循环完成时即可将所有的...
[原题链接](https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-oiae/) ## 链表基础知识 数组想必大家都很熟悉，几乎我们每天都会操作它，我们可以对比数组来学习链表。 首先要明确的是，链表和数组的底层存储结构不同，数组要求存储在一块连续的内存中，而链表是通过指针将一组零散的内存块串联起来。可见链表对内存的要求降低了，但是随机访问的性能就没有数组好了，需要 O(n) 的时间复杂度。 下图中展示了单链表及单链表的添加和删除操作，`其实链表操作的本质就是处理链表结点之间的指针`。  在删除链表结点的操作中，我们只需要将需要删除结点的前驱结点的 next 指针，指向其后继即可。这样，当前被删除的结点就被丢弃在内存中，等待着它的是被垃圾回收器清除。 为了更便于你理解，链表可以类比现实生活中的火车，火车的每节车厢就是链表的一个个结点。车厢之间相互连接，可以添加或者移除掉。春运时，客运量比较大，列车一般会加挂车厢。 链表的结点结构由数据域和指针域组成，在 JavaScript 中，以嵌套的对象形式实现。 ```js { // 数据域 val: 1, // 指针域 next: { val:2, next: ... }...
[原题链接](https://leetcode-cn.com/problems/linked-list-cycle/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-md8m/) 链表的基础知识可以移步[这个题解](https://leetcode-cn.com/problems/swap-nodes-in-pairs/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-oiae/)，这里不再赘述。 ## 快慢指针 1.使用快慢不同的两个指针遍历，快指针一次走两步，慢指针一次走一步。 2.如果没有环，快指针会先到达尾部，返回 false。 3.如果有环，则一定会相遇。 ```javascript const hasCycle = function(head) { if (!head || !head.next) return false; let fast = head.next; let slow = head; while (fast...
[原题链接](https://leetcode-cn.com/problems/reverse-linked-list/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-5g79/) ## 迭代 1.初始化哨兵节点 prev 为 null，及当前节点 curr 指向头节点。 2.开始迭代，记录 next 指针留备后用，反转指针。 3.推进指针继续迭代，最后返回新的链表头节点 prev。 ```javascript const reverseList = function(head) { let prev = null; let curr = head; while (curr...
[原题链接](https://leetcode-cn.com/problems/middle-of-the-linked-list/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-76rb/) ## 快慢指针 老套路，借助快慢指针，fast 一次走两步，slow 一次走一步，当 fast 到达链表末尾时，slow 就处于链表的中间点了。 ```js const middleNode = function(head) { let fast = head, slow = head; while (fast && fast.next) { slow = slow.next;...
[原题链接](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-c254/) 周树人先生曾经说过：学好树，数据结构与算法你就掌握了一半！ 食堂老板(童欧巴)：就算我们作为互联网浪潮中的叶子结点，也需要有蚍蜉撼树的精神，就算蚍蜉撼树是自不量力。因为就算终其一生只是个普通人，但你总不能为了成为一个普通人而终其一生吧。 今日菜谱，蚂蚁上树，下面介绍一下演员。 ## 树的相关名词科普 - 根节点 - 叶子节点 - 父节点 - 子节点 - 兄弟节点 - 高度 - 深度 - 层  A 是 `根节点`。C、D、F、G 是 `叶子节点`。A 是 B...