javascript-leetcode
javascript-leetcode copied to clipboard
Geekhyt
LeetCode 题解仓库🍖
[原题链接](https://leetcode-cn.com/problems/single-number/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-f434/) ## 位运算 1. 一个数和 0 做异或运算等于其本身 2. 一个数和它本身做异或运算等于 0 3. 异或运算满足交换律和结合律 数组中所有元素的异或运算结果就是数组中只出现一次的数字。 ```js const singleNumber = function(nums) { let ans = 0 for (const num of nums) { ans...
[原题链接](https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-slxe/) ## 数组 sort 排序 ```js const getLeastNumbers = function(arr, k) { return arr.sort((a, b) => a - b).slice(0, k) } ``` - 时间复杂度: O(nlogn) - 空间复杂度: O(logn) ## 大顶堆...
[原题链接](https://leetcode-cn.com/problems/longest-palindrome/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-sop6/) 1. 使用字母的 Unicode 编码和数组会比哈希表更优化 2. 初始化存放字母出现次数的数组，默认都为 0 次 3. 遍历字符串，统计字母出现的次数，65 是字母 A 的 Unicode 编码，这样可以从索引 0 开始计数 4. time 的偶数次(time / 2)可以成为构造回文的一部分，再乘 2，可以得到次数 5. 如果最后计算出的长度小于字符串的长度，则是奇数长度的回文，需要加 1 ```js const longestPalindrome...
[原题链接](https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-lm88/) ## 栈 1. 扫描过的字符入栈暂存 2. 如果扫描的当前字符与栈顶元素相同，则将栈顶元素出栈 3. 将栈中剩余的字符转换成字符串 ```js const removeDuplicates = function(s) { const stack = [] for (const i of s) { if (stack.length && stack[stack.length -...
[原题链接](https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-25nl/) ## 递归 1. 二叉搜索树的中序遍历是升序的，本题中给出的数组刚好是升序的，相当于通过中序遍历恢复二叉搜索树 2. 可以选择升序序列中的任意位置的元素作为根节点，该元素左边的升序序列构建左子树，右边的升序序列构建右子树 3. 题目又要求高度平衡，所以我们需要选择升序序列的中间位置的元素作为根节点即可 ```js const sortedArrayToBST = function (nums) { const buildTree = (Arr, left, right) => { if (left > right) return null...
[原题链接](https://leetcode-cn.com/problems/diameter-of-binary-tree/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-s12u/) ## 递归 dfs - 一棵二叉树的直径长度是任意两个结点路径长度中的最大值 - 这条路径可能穿过也可能不穿过根结点 两个公式： 1. 最长路径 = 左子树最长路径 + 右子树最长路径 + 1 (根结点) 2. 高度(最大深度) = 左右子树中的最大深度 + 1 (根结点) ```js const diameterOfBinaryTree = function(root)...
[原题链接](https://leetcode-cn.com/problems/path-sum/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-jvuc/) ## 递归 1. 处理边界，节点不存在时返回 false 2. 左右子树都不存在时代表是叶子结点，判断是否符合条件 3. 递归左右子树时进行转换，看能否找到 `targetSum - root.val` 的路径 ```js const hasPathSum = (root, targetSum) => { if (root === null) return false if (root.left...
[原题链接](https://leetcode-cn.com/problems/balanced-binary-tree/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-p2ph/) 一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。 1. 如果遍历完成，还没有高度差超过 1 的左右子树，则符合条件 2. 判断左右子树高度差，超过 1 则返回 false 3. 递归左右子树 4. 封装获取子树高度函数 getHeight ```javascript const isBalanced = function(root) { if (!root) return true if (Math.abs(getHeight(root.left) -...
[原题链接](https://leetcode-cn.com/problems/length-of-last-word/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-9j6v/) ## 反向遍历 过滤掉末尾空格后，反向遍历字符串，并使用 count 计数，再次遇到空格时结束。 ```js const lengthOfLastWord = function(s) { if (s.length === 0) return 0 let count = 0 for (let i = s.length - 1; i...
[原题链接](https://leetcode-cn.com/problems/daily-temperatures/solution/qian-duan-shi-tang-ti-jie-chao-hao-li-ji-ru2a/) ## 单调栈 一维数组，要寻找任一个元素的右边(左边)第一个比自己大(小)的元素的位置时，第一时间想到用单调栈解题。 1. 初始化一个都为 0 的数组，处理题目要求气温不会升高时，用 0 代替 2. 初始化一个栈，栈中准备存储索引。遍历数组，如果当前元素比栈顶大，则让元素出栈 3. 此时栈顶元素就是当前项的右边的第一个比它大的元素索引，计算出距离存到 res 中 4. 最后返回 res 即可 ```js const dailyTemperatures = (T) => { const res =...