Leetcode

题目形容给你一个字符串数组 names ，和一个由 互不雷同 的正整数组成的数组 heights 。两个数组的长度均为 n 。 对于每个下标 i，names[i] 和 heights[i] 示意第 i 集体的名字和身高。 请按身高 降序 程序返回对应的名字数组 names 。 示例 1： 输出： names = ["Mary","John","Emma"], heights = [180,165,170]输入： ["Mary","Emma","John"]解释： Mary 最高，接着是 Emma 和 John 。示例 2： 输出： names = ["Alice","Bob","Bob"], heights = [155,185,150]输入： ["Bob","Alice","Bob"]解释： 第一个 Bob 最高，而后是 Alice 和第二个 Bob 。力扣原题目地址：https://leetcode.cn/problems/...思路解法剖析题目中有两块信息，别离是对应的身高数组和姓名数组，不过最终要求的后果却是，依照身高数组的排序返回对应的姓名数组。一想到排序，咱们首先要想到js中的sort(function(a-b){})排序办法。不过平时应用这个api的时候，咱们经常是用做一维数组的排序。实际上二维数组也能够应用这个api的，为什么会提到二维数组呢？因为单个的信息蕴含两个变量：姓名和身高。所以应用二维数组最合适思路步骤创立一个二维数组，二维数组中的每一项又是一个小数组，一个个的小数组中都寄存两个值，某人的名字和身高。而后依据身高排序将排好序的二维数组遍历，取出其中的名字即可代码应用Map汇合转二维数组function sortPeople(names, heights) { // 留神heights数组没有反复项（names数组可能有反复项） // 两个对应数组，等同长度，取谁的长度都行 let n = names.length // 首先将名字身高组合成一个map汇合 let map = new Map() for (let i = 0; i < n; i++) { map.set(heights[i], names[i]) // 取谁，value就是谁 } // 而后将map汇合转换成二维数组，并调用原生js的api排序 let sort2WeiArr = [...map].sort(function (a, b) { return b[0] - a[0] // 记不清a-b还是b-a没关系，打印看下就行了 }) // 排好序的二维数组再遍历，取出名字项即可 let result = sort2WeiArr.map((item) => { return item[1] }) return result}const res = sortPeople(names, heights)console.log('排序后果', res)tips: Map汇合转二维数组：[...Map] 这样写就解构转二维数组了 ...

前言常常会有人问，作为前端，你在理论工作中用到过哪些算法，之前我答复是，树和位运算，而最近在学习网络模块，发现了和前端，起码是和网络相干的一种算法，那就是 滑动窗口； 咱们晓得在 HTTP1.1 发送申请，TCP 会将申请传输到服务端，而对于 TCP 协定，最重要的能力之一就是管制流速； 当发送方须要发送很多申请的时候，这些申请会阻塞在某一个缓存中期待 TCP 发送，这个前面还有源源不断的申请发动，那总不能一下子全堵在缓存上吧，会炸掉的，这个时候这个模型就是滑动窗口了 发送过程有三个状态： 绿色是发送并连贯胜利的浅绿色是发送，然而还没有收到 ACK 响应的，这个时候有可能会挂掉，所以这个时候发送方还得存着这个申请随时筹备重发红色是期待发送的前面那些就是被阻塞的申请了这个时候 TCP 可能缓存的申请数就是一个窗口，每当浅绿色转成深绿色，那么窗口就能够像左边滑动，而窗口还保留的状态仍然能够复用，这就是滑动窗口 的魅力了 滑动窗口最大特点是，滑动窗口过程中，保留在窗口里的数据状态间接复用，不须要再次构建，节约资源； 那么接下来咱们通过做题来相熟一下滑窗，并看看是否有更多不一样的状况吧； 注释依据滑窗窗口大小是否固定，分成了两种：固定大小的窗口 和 可变窗口大小; 前言谈及的 TCP 中的滑窗状况，其实是一个固定大小的滑窗，当然也能够先给定局部大小，而后依据流速进行扩大，那是后续的操作了； 而更多的状况是不固定大小的滑窗，这类滑窗个别都是创立过程中，一股脑子将资源耗尽去扩充窗口，达到一个阈值，而后再膨胀窗口，依据具体题目，达到一个均衡了； 这其实就如同是一个疾速试错过程，先将状况推到极致了，而后退出对应的变量来膨胀窗口，找到比拟适合的一个状况，等到合规的状况在窗口里突破了，就从新扩大； 滑窗其实在了解题意的时候，又有点一分为二的感觉，就是我能够将窗口里的状态和窗口外的状态切离开，然而他们又是此消彼长的关系，这样一直衡量,达到一个动态平衡的状态，就是某些题的后果 模板固定大小的窗口 l 初始化为 0初始化 r, 使得 r-l+1 就是窗口大小同时挪动 l 和 r判断窗口内的间断元素是否满足题目限定的条件可变窗口大小 l r 都初始化为 0r 指针挪动一步判断窗口内的间断元素是否满足条件 满足，再判断是否须要更新最优解；如果须要则更新，并尝试通过挪动 l 指针放大窗口的大小不满足，则持续双滑窗景象一般的不定滑窗都是先走 r 指针，而后达到触发条件，而后膨胀 l 指针，膨胀到不达标之后进行，而后 r 指针重新启动然而有那么一些题目，当 r 指针达标后, l 指针在一段范畴内 [l1,l2)，且可能与后续的 [r1,r2) 任何两个指针形成的滑窗都会形成合规的滑窗那么这个时候用单个指针 l 膨胀到不符合要求的 l2,那么就只产生 [l1,l2）与 r1 的条件，而原本应该合规的 lx-rx 都被干掉了(lx 在 [l1,l2] 中)，因为这个时候 l 曾经跑到 l2 处了这个时候就须要开两个指针 l1, l2 ，每次固定 r 指针的时候，咱们找出第一个符合要求的 l1, 和截止地位 l2,而后持续让 r 走，挪动过程始终保持两个滑窗 [l1.r],[l2,r]，能够保障在整个挪动过程所有的状况都思考到了这类题目都是求数量，比方说某种状况的子数组有多少个，这样就得将所有状况都弄出来，然而如果只是要求一个极值，比方说这些符合要求的状况中，最小是多少，那么就没必要用双滑窗了，因为 r 指针的挪动必定会扩充窗口，所以 l 指针只须要保留对应的极值(第一个或者最初一个)，而后求出极值即可最初滑窗是双指针的一种非凡状况，咱们在应用双指针解决问题的时候，可能不会思考前一个窗口里的状态值，只是将所有状况都思考进行，这样就会有很多计算是反复的，滑窗就是一种优化了的双指针状况。 ...

什么是动静布局动静布局，英文：Dynamic Programming，简称DP，将问题合成为互相重叠的子问题，通过重复求解子问题来解决原问题就是动静布局，如果某一问题有很多重叠子问题，应用动静布局来解是比拟无效的。 求解动静布局的外围问题是穷举，然而这类问题穷举有点特地，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动静布局问题肯定会具备「最优子结构」，能力通过子问题的最值得到原问题的最值。另外，尽管动静布局的核心思想就是穷举求最值，然而问题能够变幻无穷，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」能力正确地穷举。重叠子问题、最优子结构、状态转移方程就是动静布局三要素 动静布局和其余算法的区别动静布局和分治的区别：动静布局和分治都有最优子结构 ，然而分治的子问题不重叠动静布局和贪婪的区别：动静布局中每一个状态肯定是由上一个状态推导进去的，这一点就辨别于贪婪，贪婪没有状态推导，而是从部分间接选最优解，所以它永远是部分最优，然而全局的解不肯定是最优的。动静布局和递归的区别：递归和回溯可能存在十分多的反复计算，动静布局能够用递归加记忆化的形式缩小不必要的反复计算动静布局的解题办法递归+记忆化(自顶向下)动静布局（自底向上） 解动静布局题目的步骤依据重叠子问题定义状态寻找最优子结构推导状态转移方程确定dp初始状态确定输入值斐波那契的动静布局的解题思路 动画过大，点击查看 暴力递归//暴力递归复杂度O(2^n)var fib = function (N) { if (N == 0) return 0; if (N == 1) return 1; return fib(N - 1) + fib(N - 2);};递归 + 记忆化var fib = function (n) { const memo = {}; // 对已算出的后果进行缓存 const helper = (x) => { if (memo[x]) return memo[x]; if (x == 0) return 0; if (x == 1) return 1; memo[x] = helper(x - 1) + helper(x - 2); return memo[x]; }; return helper(n);};动静布局const fib = (n) => { if (n <= 1) return n; const dp = [0, 1]; for (let i = 2; i <= n; i++) { //自底向上计算每个状态 dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n];};滚动数组优化const fib = (n) => { if (n <= 1) return n; //滚动数组 dp[i]只和dp[i-1]、dp[i-2]相干，只保护长度为2的滚动数组，一直替换数组元素 const dp = [0, 1]; let sum = null; for (let i = 2; i <= n; i++) { sum = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = sum; } return sum;};动静布局 + 降维，（降维能缩小空间复杂度，但不利于程序的扩大）var fib = function (N) { if (N <= 1) { return N; } let prev2 = 0; let prev1 = 1; let result = 0; for (let i = 2; i <= N; i++) { result = prev1 + prev2; //间接用两个变量就行 prev2 = prev1; prev1 = result; } return result;};509. 斐波那契数（easy）斐波那契数 （通常用 F(n) 示意）造成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，前面的每一项数字都是后面两项数字的和。也就是： ...

一、二分搜索算法1、简介 二分搜寻是一种在有序数组中查找某一特定元素的搜索算法。 二分搜索算法的工夫复杂度为 O(log n)，相比拟顺序搜索的 O(n) 工夫复杂度，它要快很多。 例如，在一个长度为一百万的有序数组中，采纳顺序搜索，最坏的状况须要执行一百万次，而二分搜索算法只须要二十次！ 从上图，读者能够很容易发现，二分搜寻的要害就是通过目标值与两头值的比拟，将搜寻区间放大一半，这也是为什么有序数组是二分搜索算法的重要前提。 2、代码实现 由前文可知，二分搜寻并不是一个特地简单的算法，然而想通过代码正确地实现它，并不是一件易事。 首先要求出数组的两头下标（整数），从而获取到两头值： const mid = Math.floor((start + end) / 2) 读者可能第一工夫想到的就是上述写法，然而在一些极其的状况，start + end 可能间接超出最大的平安整数，所以更加的审慎的写法如下： const mid = Math.floor(start + (end - start) / 2) 最初就是搜寻区间如何一直地放大一半，对于很多初学者来说，常常会将其写成一个死循环，这里倡议放弃搜寻区间左闭右开的写法： while (start < end) { const mid = Math.floor(start + (end - start) / 2) if (arr[mid] < target) { start = mid + 1 } else { end = mid }}二、LeetCode 实战1、744. 寻找比指标字母大的最小字母 这道题目次要考查二分搜索算法的根本实现： ...

一、前言 《JavaScript刷LeetCode拿offer-双指针技巧》中，简略地介绍了双指针技巧相比拟单指针的长处，以及联合 Easy 难度的题目带大家进一步理解双指针的利用。 进入 Medium 难度之后，解题的关键在于如何结构双指针以及确定指针挪动的规定，解题办法能够演绎为以下两类： 滑动窗口算法（Sliding Window Algorithm）;对数组进行预处理（如：排序，前缀和等等），再利用双指针遍历;这两种办法都能够将双循环问题转化为单循环问题，从而无效地升高算法的工夫复杂度。本篇次要介绍滑动窗口算法以及相干题型的解题思路，第二类题型会放在下一篇中解说。 滑动窗口算法具体的表现形式为：左右指针始终保护一个满足条件的窗口值，右指针负责向前遍历，当窗口值不满足条件时，将左指针指向的元素移出窗口，同时向前挪动左指针。 上面，结合实际的题目来了解如何应用滑动窗口算法。 二、567. 字符串的排列给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否蕴含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。 本道题目实际上能够转化为是否能找出满足以下条件的 s2 字符串的子串： 该子串的长度和 s1 字符串的长度相等；该子串中蕴含的字符以及对应的数量和 s1 字符串雷同；那么联合滑动窗口算法，须要保护一个长度为 s1 字符串长度的窗口，并且窗口中的字符以及相应的数量与 s1 雷同。 字符数量通过 HashTable 来保护，在 JavaScript 语言中能够采纳 Map 数据结构。 三、904. 水果成篮 在一排树中，第 i 棵树产生 tree[i] 型的水果。你能够从你抉择的任何树开始，而后反复执行以下步骤：1、把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。2、挪动到以后树右侧的下一棵树。如果左边没有树，就停下来。请留神，在抉择一颗树后，你没有任何抉择：你必须执行步骤 1，而后执行步骤 2，而后返回步骤 1，而后执行步骤 2，依此类推，直至进行。你有两个篮子，每个篮子能够携带任何数量的水果，但你心愿每个篮子只携带一种类型的水果。用这个程序你能收集的水果总量是多少？ 这道题很显著合乎滑动窗口算法的特色：保护一个至少有两种水果的窗口。 当窗口中呈现第三种水果时，须要从窗口的右边顺次移除果树，保障以后窗口只含有两种水果，这里能够采纳 HashTable 记录同一类型果树最初呈现的坐标来优化工夫复杂度。 最初，在窗口挪动的过程中，计算相应的水果总量即可。 四、3. 无反复字符的最长子串给定一个字符串，请你找出其中不含有反复字符的 最长子串 的长度。 参考视频：传送门 这道题目与上一道《904. 水果成篮》的解题思路如出一撤： ...

位运算根底：程序中所有的数载计算机内存中都是以二进制存储的，位运算就是间接对整数在内存中的二进制进行操作，因为间接在内存中进行操作，不须要转成十进制，因而处理速度十分快 常见位运算 x & 1 === 0 //判断奇偶x & (x - 1) //革除最左边的1x & -x //失去最左边的1 191. 位1的个数 （easy）编写一个函数，输出是一个无符号整数（以二进制串的模式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明分量）。 提醒： 请留神，在某些语言（如 Java）中，没有无符号整数类型。在这种状况下，输出和输入都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其外部的二进制示意模式都是雷同的。在 Java 中，编译器应用二进制补码记法来示意有符号整数。因而，在下面的 示例 3 中，输出示意有符号整数 -3。 示例 1： 输出：00000000000000000000000000001011输入：3解释：输出的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。示例 2： 输出：00000000000000000000000010000000输入：1解释：输出的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。示例 3： 输出：11111111111111111111111111111101输入：31解释：输出的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。 提醒： 输出必须是长度为 32 的 二进制串 。 进阶： 如果屡次调用这个函数，你将如何优化你的算法？ 办法1：循环每个二进制位思路：间接循环二进制中的每一位，判断是否为1，统计1的个数复杂度剖析：工夫复杂度O(k)，k=32。空间复杂度为O(1)Js: var hammingWeight = function(n) { let ret = 0; for (let i = 0; i < 32; i++) { if ((n & (1 << i)) !== 0) {//让1一直左移 判断该位是否为1 ret++; } } return ret;};办法2：优化循环的过程思路：巧用二进制公式x&(x-1)示意去掉二进制中最左边的第一个1，减速循环过程复杂度剖析：工夫复杂度为O(k)，k为二进制中1的个数，最坏的状况下所有位都是1。空间复杂度是O(1)js: ...

工作太忙没有工夫刷算法题，面试的时候好心虚。这里双手奉上40道LeetCode上经典面试算法题，整顿的内容有点长，倡议先珍藏，缓缓消化，在来年顺利拿到称心的offer。 1、[LeetCode] 两数之和给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你能够假如每个输出只对应一种答案，且同样的元素不能被反复利用。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1] var twoSum = function(nums, target) { var len = nums.length; for(var i=0; i<len; i++){ for(var j=i+1; j<len;j++){ if(nums[i] + nums[j] == target){ return [i, j]; } } } return [];}; 2、[LeetCode]门路总和给定一个二叉树和一个指标和，判断该树中是否存在根节点到叶子节点的门路，这条门路上所有节点值相加等于指标和。阐明: 叶子节点是指没有子节点的节点。 var hasPathSum = function(root, sum) { if (!root) return false; var cur = sum-root.val; if (!root.left&&!root.right&&cur==0) return true; if (!root.left) return hasPathSum(root.right, cur); if (!root.right) return hasPathSum(root.left, cur); return hasPathSum(root.left, cur)||hasPathSum(root.right, cur); };3、[LeetCode]二叉树的最小深度给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短门路上的节点数量。阐明: 叶子节点是指没有子节点的节点。 ...

注释在前端中的确用到不少与树相干的的常识，比方说 DOM 树，Diff 算法，包含原型链其实都算是树，学会树，其实对于学这些常识还是有比拟大的帮忙的，当然咱们学算法还是得思考面试，而树恰好也是一个大重点 -- 起码在前端而言； 次要起因在于，树它金玉其外;败絮其中，比拟下里巴人，须要形象然而又能把图画进去不至于让你毫无脉络，简略而言就是看上去很厉害，但实际上也很接地气，俗称比拟个别；要晓得做前端的面试算法，考的不就是你有么得被动学习能力，形象能力等，然而思考到参差不齐的前端娱乐圈，考得难吧可能就全是漏网之鱼了，所以既要筛选出鱼，然而又不能难度过大，树就是那个比拟适中的，所以连忙刷起来吧敌人们； 这里原本是要遵循 3:5:2 难度来刷，预计刷个30题就差不多，然而理论中等题刷得骑虎难下，难题是欲仙欲死，容易题是味如嚼蜡，所以 XDM 担待一下。选题次要是那个男人精选的例题以及 Leetcode 中 HOT 题和字节专题，总的来说代表性还是够的，刷完应该大略或者可能应酬一下树这方面的算法了。 如果感觉有那么点帮忙，请点个赞留个言，点赞超过10个就更新下一part；好吧，即使不过也会更新，就是这么臭不要脸，大家伙加油吧，欧力给！！ 二叉树的遍历递归遍历 递归的时候前中后序都能间接解决完了递归是前中后序遍历最简略也是最容易出了解的办法，不懂的画个图就好了迭代遍历 -- 双色标记法 应用色彩标记节点状态，新节点为红色，曾经拜访的节点为灰色 -- 能够用数字或者其余任意标签标示如果遇到的节点是红色，则标记为灰色，而后将右节点，本身，左节点一次入栈 -- 中序遍历如果遇到的节点是灰色的，则将节点输入留神这里是用 stack 栈来存储的，所以是后进先出，所以如果是中序遍历，左 - 中 - 右 ，那么在插入栈的时候要反过来 右 - 中 - 左依照那个男人的批示，失常咱们就用递归做就好，就如同咱们做非排序题排序的时候，sort 一下就好了，然而一旦面试官问到用另外的迭代形式的时候，咱们再套个模板，会比记住多个迭代写法要简略，毕竟内存容量无限，而后续遍历的迭代写法的确挺坑的，能省一点内存就省一点吧 144. 二叉树的前序遍历// 144. 二叉树的前序遍历/** * @剖析 -- 递归 */var preorderTraversal = function (root) { const ret = []; const recursion = (root) => { if (!root) return; ret.push(root.val); recursion(root.left); recursion(root.right); }; recursion(root); return ret;};/** * @剖析 -- 迭代 -- 双色标记法 * 1. 应用色彩标记节点状态，新节点为红色，曾经拜访的节点为灰色 -- 能够用数字或者其余任意标签标示 * 2. 如果遇到的节点是红色，则标记为灰色，而后将右节点，本身，左节点一次入栈 -- 中序遍历 * 3. 如果遇到的节点是灰色的，则将节点输入 * 4. 留神这里是用 stack 栈来存储的，所以是后进先出，这里是前序遍历，中 - 左 - 右 ，那么在插入栈的时候要反过来 右 - 左 - 中 */var preorderTraversal = function (root) { const ret = []; const stack = []; stack.push([root, 0]); // 0 是红色未解决的，1 是灰色解决过的 while (stack.length) { const [root, color] = stack.pop(); if (root) { if (color === 0) { // 遇到白球，则插入 -- 前序 stack.push([root.right, 0]); stack.push([root.left, 0]); stack.push([root, 1]); } else { // 遇到灰球，则收网 ret.push(root.val); } } } return ret;};1.94 二叉树的中序遍历// 94. 二叉树的中序遍历/** * @剖析 * 1. 递归的时候前中后序都能间接解决完了 * 2. 递归是前中后序遍历最简略也是最容易出了解的办法，不懂的画个图就好了 */var inorderTraversal = function(root) { const ret = [] const recursion = root => { if(!root) return recursion(root.left) // 这里是中序，所以在两个递归之间，如果是前序就在后面，后序就在前面 ret.push(root.val) recursion(root.right) } recursion(root) return ret};/** * @剖析 -- 迭代 -- 双色标记法 * 1. 应用色彩标记节点状态，新节点为红色，曾经拜访的节点为灰色 -- 能够用数字或者其余任意标签标示 * 2. 如果遇到的节点是红色，则标记为灰色，而后将右节点，本身，左节点一次入栈 -- 中序遍历 * 3. 如果遇到的节点是灰色的，则将节点输入 * 4. 留神这里是用 stack 栈来存储的，所以是后进先出，所以如果是中序遍历，左 - 中 - 右 ，那么在插入栈的时候要反过来 右 - 中 - 左 */var inorderTraversal = function(root) { const ret = [] const stack = [] stack.push([root,0]) // 0 是红色未解决的，1 是灰色解决过的 while(stack.length) { const [root,color] = stack.pop() if(root){ if(color === 0){ // 遇到白球，则插入 -- 中序遍历 stack.push([root.right,0]) stack.push([root,1]) stack.push([root.left,0]) }else{ // 遇到灰球，则收网 ret.push(root.val) } } } return ret};145. 二叉树的后序遍历// 145. 二叉树的后序遍历/** * @剖析 -- 递归 */var postorderTraversal = function(root) { const ret = [] const dfs = (root) => { if(!root) return dfs(root.left) dfs(root.right) ret.push(root.val) } dfs(root) return ret};/** * @剖析 -- 迭代 -- 双色球 */var postorderTraversal = function(root) { const ret = [] const stack = [] stack.push([root,0]) while(stack.length){ const [root,color] = stack.pop() if(root) { if(color === 0){ stack.push([root,1]) stack.push([root.right,0]) stack.push([root.left,0]) }else{ ret.push(root.val) } } } return ret}刷题过程一些纳闷点自顶向下(前序遍历)和自低向上(后续遍历)这两个名词在很多讲树的题解中常常会呈现，而这与咱们遍历树求值到底关联点在哪里，缓缓刷题之后我发现，尽管 dfs 有三种模式，但在形象到具体题目的时候，其实是属于不同的办法的。 ...

注释 plus堆是动静求极值的数据结构，所以当遇到须要一直取极值的时候，就能够思考用堆了 舒适提醒，倡议每一道题都本人 new 一个堆，这样能力发现堆之美，其实就是不会再次遇到 topK 的时候只能用冒泡来做。 行文至此也该完结了，如果有 10 个关注，那就更新一下下一 part， dp 或者树吧， thx。 二叉堆的创立剖析 -- 小顶堆这里是一个小顶堆，特点就是根节点的值比子节点的值都小，通常用作经典的前 K 大次要有两个办法， 一个是回升，这里次要用作构建堆的时候，整顿堆用的一个是下沉，这里次要用于弹出堆顶元素后，置换了堆顶值之后应用的，这里用到 this.data[0]，是因为这个办法个别是构建残缺的堆之后，才会应用其余的办法不是不能够，只是为了保障灵活性，临时就先做个简易版，前面再思考，因为办法越多，其实兼容性就越差了class MinHeap { constructor(len) { this.data = []; this.data[0] = len; // 第一个节点用来寄存堆的大小 -- 某些特定环境比拟好用 } // 下浮 down(index) { const size = this.data[0]; while (index << 1 <= size) { let child = index << 1; if (child !== size && this.data[child] > this.data[child + 1]) { child += 1; //如果右节点更小，就右节点作为下一个接盘的节点 } if (this.data[index] > this.data[child]) { // 替换一下 [this.data[index], this.data[child]] = [ this.data[child], this.data[index], ]; index = child; } else { // 只有其中一次生效了，那么就没必要持续往下查找了 break; } } } // 都是从最底层开始算的 upper() { // 这里不必 this.data[0] 是因为以后构建的堆可能还没达到堆的最大值，所以不能应用 let index = this.data.length - 1; while (index >> 1 > 0) { let father = index >> 1; if (this.data[index] < this.data[father]) { // 子节点比父节点要小，则网上走 [this.data[index], this.data[father]] = [ this.data[father], this.data[index], ]; index = father; } else { break; } } } }剖析 -- 大顶堆绝对于初始版的小顶堆，这一版的大顶堆增加了两个办法， pop 和 addadd 办法能够写在应用堆的地位，然而为了让它和堆的第一个值匹配，所以写在了类办法外面，不便对 size 的增加pop 是为了取出堆顶元素，堆是为了解决动静取极值而存在的数据结构，所以必然要取出整顿的过程。class MaxHeap { constructor() { this.data = []; this.data[0] = 0; // 第一个值是以后堆的size } down(index) { const len = this.data.length; // 是下标极限 while (index << 1 < len) { let child = index << 1; if (child !== len && this.data[child + 1] > this.data[child]) { child++; } if (this.data[child] > this.data[index]) { [this.data[child], this.data[index]] = [ this.data[index], this.data[child], ]; index = child; } else { break; } } } upper() { let index = this.data[0]; // 最大下标 while (index >> 1 > 0) { const father = index >> 1; if (this.data[index] > this.data[father]) { [this.data[father], this.data[index]] = [ this.data[index], this.data[father], ]; index = father; } else { break; } } } add(value) { // 先加在最开端 this.data.push(value); this.data[0]++; // size 也加一下 this.upper(); // 整顿一下 } // 弹出堆顶元素 pop() { const last = this.data[0]; [this.data[1], this.data[last]] = [this.data[last], this.data[1]]; //替换堆顶和堆尾的值 const ret = this.data.pop(); this.data[0]--; this.down(1); // 整顿 return ret; }}参考视频：传送门 ...

并查集（union & find）：用于解决一些元素的合并和查问问题 Find：确定元素属于哪一个子集，他能够被用来确定两个元素是否属于同一个子集，退出门路压缩，复杂度近乎O(1) Union：将两个子集合并成同一个汇合 // 0,1,2,3//parent: 0,1,2,3//size: 1,1,1,1class UnionFind{ constructor(n){ //结构一个大小为n的汇合 this.count = n this.parent = new Array(n) this.size = new Array(n) // size数组记录着每棵树的大小 for (let i = 0; i < n; i++) { this.parent[i] = i; // 本人是本人的parent this.size[i] = 1; } } union(p,q){ //连通结点p和结点q, p和q都是索引 let rootP = this.find(p); let rootQ = this.find(q); if(rootP === rootQ) return // 元素数量小的接到数量多的上面，这样比拟均衡 if (this.size[rootP] > this.size[rootQ]) { this.parent[rootQ] = rootP; this.size[rootP] += this.size[rootQ]; } else { this.parent[rootP] = rootQ; this.size[rootQ] += this.size[rootP]; } this.count--; } isConnected(p, q) { //判断p,q是否连通 return this.find(p)=== this.find(q) } find(x) { //找到x结点的root while (this.parent[x] != x) { // 进行门路压缩 this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; } return x; } getCount() { //返回子集个数 return this.count; }}// 0,1,2,3//parent: 0,1,2,3//rank: 1,1,1,1//采纳rank优化class UnionFind { constructor(n) { //结构一个节点数为n的汇合 this.count = n //并查集总数 this.parent = new Array(n) this.rank = new Array(n) // rank数组记录着每棵树的分量 for (let i = 0; i < n; i++) { this.parent[i] = i; // 本人是本人的parent this.rank[i] = 1; //每个汇合上节点的数量 } } union(p, q) { //连通结点p和结点q, p和q都是索引 let rootP = this.find(p); let rootQ = this.find(q); if (rootP === rootQ) return // 深度小的接在深度大元素下 if (this.rank[rootP] > this.rank[rootQ]) { this.parent[rootQ] = rootP; } else if (this.rank[rootP] < this.rank[rootQ]) { this.parent[rootP] = rootQ; } else { this.parent[rootP] = rootQ; this.rank[rootQ]++ } this.count--; } isConnected(p, q) { //判断p,q是否连通 return this.find(p) === this.find(q) } find(x) { //找到x结点的root while (this.parent[x] != x) { // 进行门路压缩 this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; } return x; } getCount() { //返回子集个数 return this.count; }}200. 岛屿数量 (medium)给你一个由 '1'（海洋）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 ...

一、前言 个别状况下，遍历数组（或者字符串）操作，都是采纳单指针从前往后或者从后往前顺次拜访数组（或者字符串）中的元素。 而对于以下状况，只采纳单指针解决，则会徒增工夫复杂度和空间复杂度： 例如：找到两个数使得它们相加之和等于指标数，采纳单指针解决，则须要嵌套循环，使得工夫复杂度增长为 O(n^2)；再例如：翻转数组，采纳单指针解决，则须要额定内存空间，使得空间复杂度增长为 O(n)；利用双指针技巧则能够优化上述解决方案： 第一个例子：能够先对采纳数组进行排序预处理，再创立前后指针向两头遍历，遍历的工夫复杂度为 O(n)，整体工夫复杂度次要取决于排序算法，通常为 O(nlogn)；第二个列子：一个指针负责遍历，另外一个指针负责替换元素，从而使得空间复杂度为 O(1)；双指针没有简单的定义，总结起来次要解决两类问题： 将嵌套循环转化为单循环问题；通过指针记录状态，从而优化空间复杂度；上面的实战剖析会让你感触双指针的威力。 二、167. 两数之和 II - 输出有序数组给定一个已依照升序排列 的有序数组，找到两个数使得它们相加之和等于指标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。 这道题目采纳单指针的做法只能通过嵌套循环枚举所有两数之和的办法来解决，工夫复杂度为 O(n^2)。 凑巧本题中的数组曾经是有序数组，那么间接创立前后指针： 如果两数之后大于 target，尾指针向前挪动；如果两数之和小于 target，头指针向后挪动； 上述代码利用双指针技巧胜利地将工夫复杂度升高为 O(n)。 三、344. 反转字符串编写一个函数，其作用是将输出的字符串反转过去。输出字符串以字符数组 char[] 的模式给出。 本题采纳单指针的办法，须要创立一个额定的数组来保留翻转后的元素，空间复杂度为 O(n)。 利用双指针技巧，则能够在遍历的过程中同时实现替换元素的操作，工夫复杂度升高为 O(1)： 雷同类型的题目还有： 【345. 反转字符串中的元音字母】四、141. 环形链表给定一个链表，判断链表中是否有环。为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。 在链表这种数据结构中，采纳前文所说的前后指针并不一定无效（例如单向链表），这种状况下，双指针的表现形式为：快慢指针。 快慢指针指的是：设置两个前进方向雷同但速度不同的指针。 本题中，设置每次挪动一个单位的慢指针和每次挪动两个单位的快指针，那么他们必定会在环内相遇： 参考视频：传送门 雷同类型的题目还有： 【26. 删除排序数组中的反复项】五、125. 验证回文串给定一个字符串，验证它是否是回文串，只思考字母和数字字符，能够疏忽字母的大小写。阐明：本题中，咱们将空字符串定义为无效的回文串。 回文字符串问题是双指针的经典利用，同时也是面试题中的常客。 ...

递归三要素递归函数以及参数递归终止条件递归单层搜寻逻辑递归伪代码模版： function recursion(level, param1, param2, ...) { //递归终止条件 if (level > MAX_LEVEL) { // output result return; } //解决以后层 process_data(level, data, ...); //进入下一层 recursion(level + 1, p1, ...); //重置状态 reverse_state(level);}什么是分治：分治会将大问题拆解成小问题，拆解到最小问题之后，开始一直合并后果，递归是分治实现的一种模式或者是分治实现的一部分，分治包含三分局部，合成、计算、合并。分治的场景很多，例如疾速排序，归并排序。 分治伪代码模版： function divide_conquer(problem, param1, param2, ...){ if(problem === null){ // return result } //宰割问题 subproblem = split_problem(problem, data) //计算子问题 subResult1 = divide_conquer(subproblem[0], p1, ...) subResult2 = divide_conquer(subproblem[1], p1, ...) subResult3 = divide_conquer(subproblem[2], p1, ...) ... result = process_resule(subResult1, subResult2, subResult3,...)}举例计算n! n! = 1 * 2 * 3... * n ...

一、前言 本篇次要介绍双指针技巧的第二类题型：对数组进行预处理之后，再采纳双指针遍历。 在 Medium 难度的题目中，此类问题能够演绎为 K-Sum 问题： 两数之和：【881. 救生艇】；三数之和：【16. 最靠近的三数之和】、【15. 三数之和】、【923. 三数之和的多种可能】；四数之和：【18. 四数之和】；二、881. 救生艇第 i 集体的体重为 people[i]，每艘船能够承载的最大分量为 limit。每艘船最多可同时载两人，但条件是这些人的分量之和最多为 limit。返回载到每一个人所需的最小船数。(保障每个人都能被船载)。 由题意可知，保障所需的最小船数，意味着每一趟尽可能地搭载两个人，并且他们的分量最靠近最大分量，以便后续趟次可能组成两个人。 解题的要害就在于每趟尽可能地从数组中找出和值小于最大分量的最大值最小值的二元组。 那么对数组排序预处理之后，能够很容易地从左侧找到最小值，右侧找到最大值，双指针再向两头遍历，即可解题。 三、16. 最靠近的三数之和 给定一个包含 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最靠近。返回这三个数的和，假设每组输出只存在惟一答案。 奢侈解法就是通过三层循环枚举各种排列状况来找到最靠近的和值，工夫复杂度为 O(n^3)。 这里能够利用降维思维，将其转化为两数之和的问题，那么解题思路和【881. 救生艇】一模一样： 工夫复杂度被升高为 O(nlogn+n^2)。 四、15. 三数之和给定一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不反复的三元组。 有了上述题目的铺垫，再看本题，是不是会浮现以下解题范式： 降维思维，将三数之和转化为两数之和的问题；对数组进行排序，将双循环问题转化为单循环问题；对于不反复三元数组这一条件，同学们第一工夫可能会想到采纳 HashTable 来去重，然而整个双指针解题的过程中，三个数始终保持着非递加序列的个性，那么遇到反复数字间接跳过即可： ...

前言回溯，就是无脑冲，碰壁之后就回撤一步持续搞，属于一种暴力解题的思路； 实际上也是如此，当咱们在遇到一些分类探讨的问题，无奈想到比拟精妙的解决方案，咱们第一工夫思考到的就是暴力枚举所有状况，而后再做解决，而 回溯 就是这样的一个暴力法 下一个 tab 学习一下惯例的排序算法吧 注释在做回溯题 的过程中，会发现很迷茫，因为很多题如同不须要返回，在执行下一步的过程中，我就做好断定，而后将可能的失败遏制住了，这个时候，个别能持续往下走的，都属于还行的操作，咱们其实能够把这种形式叫做 剪枝 我一度陷入沉思，是不是回溯就没用了呢，是不是只有脑瓜还行，其实剪枝就好了，还回溯啥，直到想起回溯的核心思想，它其实是一种暴力解法， 也就是如果你能用其余办法，其实不必回溯,是比拟好的思路，个别状况下，回溯的复杂度会比拟高 那么到底什么时候用回溯呢？那种你没法子预设终局，或者说你的抉择不单单关联相邻层的抉择，而是会对更深层都有影响，比方说 51. N 皇后 咱们需要求的是残缺的棋盘，每一层的抉择，都会影响整个棋盘的的布局，这个时候想在下棋那一刻就将全副可能状况想进去，太难了，这时候用回溯 就是很好的抉择 而对于一些只与下层有影响，这个时候剪枝 也不失是一个好的抉择； 其实在做系列总结的时候，会尽可能用系列的办法去解答，然而一题多解也是咱们谋求的，而且咱们最初想要实现的，必定是不局限与某写法，而是只有看到了，就能 a 进去； 所以致力将大部分惯例的 tab 温习一遍，而后再缓缓填补，总结属于本人的解题计划，才是做总结的目标吧； 与大家一起致力呀 题目汇总46. 全排列剖析 不含反复数字，要求的是全排列，所以不同程序的排列都得算上，这样在枚举过程中要晓得本人已经获取过哪些值在枚举过程中缓存两个数组 arr,getIndex, arr 是枚举过程中的数组， getIndex 是走过值状态，如果以后 arr 走过对应的下标的值为1，没有走过就是 0在每一层给长期数组 arr 增加值的时候，须要保障不会反复增加，能够在每一次遇到的时候再遍历 arr，因为值是惟一的，也是能够的；在这里是用空间换工夫，用 getIndex 数组缓存对应的状态，每一次查找的复杂度是 O(1)每一次须要枚举残缺的数组，须要枚举 n 次所以工夫复杂度为 O(n2),空间复杂度 O(n)var permute = function (nums) { let ret = []; const dfs = (arr, getIndex) => { if (arr.length === nums.length) { ret.push(arr); return; } for (let i = 0; i < nums.length; i++) { const num = nums[i]; if (!!getIndex[i]) continue; // 如果存在，则代表曾经有这个值了 getIndex[i] = 1; dfs([...arr, num], getIndex); getIndex[i] = 0; } }; const getIndexArr = new Array(nums.length) dfs([], getIndexArr); return ret;};47. 全排列 II剖析 ...

并查集（union & find）：用于解决一些元素的合并和查问问题 Find：确定元素属于哪一个子集，他能够被用来确定两个元素是否属于同一个子集，退出门路压缩，复杂度近乎O(1) Union：将两个子集合并成同一个汇合 // 0,1,2,3//parent: 0,1,2,3//size: 1,1,1,1class UnionFind{ constructor(n){ //结构一个大小为n的汇合 this.count = n this.parent = new Array(n) this.size = new Array(n) // size数组记录着每棵树的大小 for (let i = 0; i < n; i++) { this.parent[i] = i; // 本人是本人的parent this.size[i] = 1; } } union(p,q){ //连通结点p和结点q, p和q都是索引 let rootP = this.find(p); let rootQ = this.find(q); if(rootP === rootQ) return // 元素数量小的接到数量多的上面，这样比拟均衡 if (this.size[rootP] > this.size[rootQ]) { this.parent[rootQ] = rootP; this.size[rootP] += this.size[rootQ]; } else { this.parent[rootP] = rootQ; this.size[rootQ] += this.size[rootP]; } this.count--; } isConnected(p, q) { //判断p,q是否连通 return this.find(p)=== this.find(q) } find(x) { //找到x结点的root while (this.parent[x] != x) { // 进行门路压缩 this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; } return x; } getCount() { //返回子集个数 return this.count; }}// 0,1,2,3//parent: 0,1,2,3//rank: 1,1,1,1//采纳rank优化class UnionFind { constructor(n) { //结构一个节点数为n的汇合 this.count = n //并查集总数 this.parent = new Array(n) this.rank = new Array(n) // rank数组记录着每棵树的分量 for (let i = 0; i < n; i++) { this.parent[i] = i; // 本人是本人的parent this.rank[i] = 1; //每个汇合上节点的数量 } } union(p, q) { //连通结点p和结点q, p和q都是索引 let rootP = this.find(p); let rootQ = this.find(q); if (rootP === rootQ) return // 深度小的接在深度大元素下 if (this.rank[rootP] > this.rank[rootQ]) { this.parent[rootQ] = rootP; } else if (this.rank[rootP] < this.rank[rootQ]) { this.parent[rootP] = rootQ; } else { this.parent[rootP] = rootQ; this.rank[rootQ]++ } this.count--; } isConnected(p, q) { //判断p,q是否连通 return this.find(p) === this.find(q) } find(x) { //找到x结点的root while (this.parent[x] != x) { // 进行门路压缩 this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; } return x; } getCount() { //返回子集个数 return this.count; }}200. 岛屿数量 (medium)给你一个由 '1'（海洋）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 ...

注释 plus堆是动静求极值的数据结构，所以当遇到须要一直取极值的时候，就能够思考用堆了 舒适提醒，倡议每一道题都本人 new 一个堆，这样能力发现堆之美，其实就是不会再次遇到 topK 的时候只能用冒泡来做。 行文至此也该完结了，如果有 10 个关注，那就更新一下下一 part， dp 或者树吧， thx。 二叉堆的创立剖析 -- 小顶堆这里是一个小顶堆，特点就是根节点的值比子节点的值都小，通常用作经典的前 K 大次要有两个办法， 一个是回升，这里次要用作构建堆的时候，整顿堆用的一个是下沉，这里次要用于弹出堆顶元素后，置换了堆顶值之后应用的，这里用到 this.data[0]，是因为这个办法个别是构建残缺的堆之后，才会应用其余的办法不是不能够，只是为了保障灵活性，临时就先做个简易版，前面再思考，因为办法越多，其实兼容性就越差了class MinHeap { constructor(len) { this.data = []; this.data[0] = len; // 第一个节点用来寄存堆的大小 -- 某些特定环境比拟好用 } // 下浮 down(index) { const size = this.data[0]; while (index << 1 <= size) { let child = index << 1; if (child !== size && this.data[child] > this.data[child + 1]) { child += 1; //如果右节点更小，就右节点作为下一个接盘的节点 } if (this.data[index] > this.data[child]) { // 替换一下 [this.data[index], this.data[child]] = [ this.data[child], this.data[index], ]; index = child; } else { // 只有其中一次生效了，那么就没必要持续往下查找了 break; } } } // 都是从最底层开始算的 upper() { // 这里不必 this.data[0] 是因为以后构建的堆可能还没达到堆的最大值，所以不能应用 let index = this.data.length - 1; while (index >> 1 > 0) { let father = index >> 1; if (this.data[index] < this.data[father]) { // 子节点比父节点要小，则网上走 [this.data[index], this.data[father]] = [ this.data[father], this.data[index], ]; index = father; } else { break; } } } }剖析 -- 大顶堆绝对于初始版的小顶堆，这一版的大顶堆增加了两个办法， pop 和 addadd 办法能够写在应用堆的地位，然而为了让它和堆的第一个值匹配，所以写在了类办法外面，不便对 size 的增加pop 是为了取出堆顶元素，堆是为了解决动静取极值而存在的数据结构，所以必然要取出整顿的过程。class MaxHeap { constructor() { this.data = []; this.data[0] = 0; // 第一个值是以后堆的size } down(index) { const len = this.data.length; // 是下标极限 while (index << 1 < len) { let child = index << 1; if (child !== len && this.data[child + 1] > this.data[child]) { child++; } if (this.data[child] > this.data[index]) { [this.data[child], this.data[index]] = [ this.data[index], this.data[child], ]; index = child; } else { break; } } } upper() { let index = this.data[0]; // 最大下标 while (index >> 1 > 0) { const father = index >> 1; if (this.data[index] > this.data[father]) { [this.data[father], this.data[index]] = [ this.data[index], this.data[father], ]; index = father; } else { break; } } } add(value) { // 先加在最开端 this.data.push(value); this.data[0]++; // size 也加一下 this.upper(); // 整顿一下 } // 弹出堆顶元素 pop() { const last = this.data[0]; [this.data[1], this.data[last]] = [this.data[last], this.data[1]]; //替换堆顶和堆尾的值 const ret = this.data.pop(); this.data[0]--; this.down(1); // 整顿 return ret; }}215. 数组中的第K个最大元素剖析 ...

前端就该用JS写算法 -- 树 -- 简略的那 30%这里优先选择了 LeetCode 热题 HOT 100 中的树题，毕竟刷题的边际收益就是冲击须要算法的面试，所以 Hot 优先级更高。 二叉树的遍历递归遍历 递归的时候前中后序都能间接解决完了递归是前中后序遍历最简略也是最容易出了解的办法，不懂的画个图就好了迭代遍历 -- 双色标记法 应用色彩标记节点状态，新节点为红色，曾经拜访的节点为灰色 -- 能够用数字或者其余任意标签标示如果遇到的节点是红色，则标记为灰色，而后将右节点，本身，左节点一次入栈 -- 中序遍历如果遇到的节点是灰色的，则将节点输入留神这里是用 stack 栈来存储的，所以是后进先出，所以如果是中序遍历，左 - 中 - 右 ，那么在插入栈的时候要反过来 右 - 中 - 左依照那个男人的批示，失常咱们就用递归做就好，就如同咱们做非排序题排序的时候，sort 一下就好了，然而一旦面试官问到用另外的迭代形式的时候，咱们再套个模板，会比记住多个迭代写法要简略，毕竟内存容量无限，而后续遍历的迭代写法的确挺坑的，能省一点内存就省一点吧 144. 二叉树的前序遍历// 144. 二叉树的前序遍历/** * @剖析 -- 递归 */var preorderTraversal = function (root) { const ret = []; const recursion = (root) => { if (!root) return; ret.push(root.val); recursion(root.left); recursion(root.right); }; recursion(root); return ret;};/** * @剖析 -- 迭代 -- 双色标记法 * 1. 应用色彩标记节点状态，新节点为红色，曾经拜访的节点为灰色 -- 能够用数字或者其余任意标签标示 * 2. 如果遇到的节点是红色，则标记为灰色，而后将右节点，本身，左节点一次入栈 -- 中序遍历 * 3. 如果遇到的节点是灰色的，则将节点输入 * 4. 留神这里是用 stack 栈来存储的，所以是后进先出，这里是前序遍历，中 - 左 - 右 ，那么在插入栈的时候要反过来 右 - 左 - 中 */var preorderTraversal = function (root) { const ret = []; const stack = []; stack.push([root, 0]); // 0 是红色未解决的，1 是灰色解决过的 while (stack.length) { const [root, color] = stack.pop(); if (root) { if (color === 0) { // 遇到白球，则插入 -- 前序 stack.push([root.right, 0]); stack.push([root.left, 0]); stack.push([root, 1]); } else { // 遇到灰球，则收网 ret.push(root.val); } } } return ret;};1.94 二叉树的中序遍历// 94. 二叉树的中序遍历/** * @剖析 * 1. 递归的时候前中后序都能间接解决完了 * 2. 递归是前中后序遍历最简略也是最容易出了解的办法，不懂的画个图就好了 */var inorderTraversal = function(root) { const ret = [] const recursion = root => { if(!root) return recursion(root.left) // 这里是中序，所以在两个递归之间，如果是前序就在后面，后序就在前面 ret.push(root.val) recursion(root.right) } recursion(root) return ret};/** * @剖析 -- 迭代 -- 双色标记法 * 1. 应用色彩标记节点状态，新节点为红色，曾经拜访的节点为灰色 -- 能够用数字或者其余任意标签标示 * 2. 如果遇到的节点是红色，则标记为灰色，而后将右节点，本身，左节点一次入栈 -- 中序遍历 * 3. 如果遇到的节点是灰色的，则将节点输入 * 4. 留神这里是用 stack 栈来存储的，所以是后进先出，所以如果是中序遍历，左 - 中 - 右 ，那么在插入栈的时候要反过来 右 - 中 - 左 */var inorderTraversal = function(root) { const ret = [] const stack = [] stack.push([root,0]) // 0 是红色未解决的，1 是灰色解决过的 while(stack.length) { const [root,color] = stack.pop() if(root){ if(color === 0){ // 遇到白球，则插入 -- 中序遍历 stack.push([root.right,0]) stack.push([root,1]) stack.push([root.left,0]) }else{ // 遇到灰球，则收网 ret.push(root.val) } } } return ret};145. 二叉树的后序遍历// 145. 二叉树的后序遍历/** * @剖析 -- 递归 */var postorderTraversal = function(root) { const ret = [] const dfs = (root) => { if(!root) return dfs(root.left) dfs(root.right) ret.push(root.val) } dfs(root) return ret};/** * @剖析 -- 迭代 -- 双色球 */var postorderTraversal = function(root) { const ret = [] const stack = [] stack.push([root,0]) while(stack.length){ const [root,color] = stack.pop() if(root) { if(color === 0){ stack.push([root,1]) stack.push([root.right,0]) stack.push([root.left,0]) }else{ ret.push(root.val) } } } return ret}参考视频：传送门 ...

前言上一 part 刚写完二分和滑窗，他们都属于非凡的双指针办法，所以这一 part 间接汇总一下除了非凡的二分和滑窗外的其余双指针写法 这里次要是快慢指针和端点指针， 解决一些一次遍历搞不掂，多个指针协商干活不累的题目，基本上感觉属于一种解题上的思路，一次不行，我就两次的样子； 所以刷完根底双指针，而后滑窗和二分后，这种思路在今后解题上应该会不定期能冒出来吧； 所以下期学习另外一种解题思路，回溯吧； 注释双指针在很多罕用的数据结构和算法中，都曾经用到，比方说链表遍历过程中，就能够用双指针找中位数，找环；在二分法中用到的也是双指针；滑动窗口，以及双滑动窗口等 所以双指针是一个解决问题的思路，当设置一个指针遍历不足以造成对照的时候，能够设置更多的参照指针来服务本人，只是个别状况两个指针足以，所以这种解决思路称为双指针 快慢指针比拟常见的双指针模式，个别是快指针走 2 步，慢指针走 1 步，达到一种对照的作用；解决了形如链表的中位数，链表有环 等问题； 还有一种是读写指针，这种也是一个指针 read 先走，而后触发某个条件之后，才会让 write 走，也就造成了快慢的成果； 左右端点指针最常见的就是二分法，都是设置 l r 指针，而后向两头合拢；所以所有的二分法的应用也是双指针的应用 还有一种就是排好序之后，依据最大值和最小值之间的运算来求值的，这个时候也须要端点指针 找反复值的时候，转换成链表找环 -- 快慢指针的变形在做快慢指针的题目的时候，咋一看题目和快慢指针没有一毛线关系，然而个别都是迭代啊，或者反复值啊什么的，反正就是须要进行雷同的运算,须要判断是否已经呈现过雷同的值, 这个时候，要不就用 hashMap 缓存一波，要不就用快慢指针，将原题转成类型链表的构造，next 指针就是对应的迭代函数，而后求是否有环(202. 高兴数), 或者求环的入口地位（287. 寻找反复数） 当然下面这种属于非凡题目的非凡做法，比方说 287. 寻找反复数 那是因为这里的下标和值刚好没法齐全重合，且有反复数，要是值也是从 [0,n-1]，那就没法子用值当下标的写法了 题目汇总题目142. 环形链表 II剖析 典型的快慢指针写法，在链表专题写过相应的题解了环形链表 II做一下这个题，是为了下一题的前置var detectCycle = function(head) { const emptyNode = new ListNode() emptyNode.next = head; if(!head) return null let slow = fast = emptyNode while(fast && fast.next){ slow = slow.next fast = fast.next.next if(slow === fast){ // 相交了，证实相交了 let next = emptyNode while(next!== slow){ next = next.next slow = slow.next } // 相交的时候，就是环入口 return slow } } return null}287. 寻找反复数剖析 -- 双指针法（快慢指针） ...

前言博主最近在刷leetcode，做到二叉树套题的时候发现很多题的解题思路都是基于二叉树的层序遍从来实现的，因而写下这篇文章，记录一下二叉树层序遍历这件"神器"在实战的使用。 [leetcode] 102.二叉树的层序遍历 二叉树的层序遍历与传统的前序、中序、后序遍历都有一些区别，他是按层级、从左到右、从上到下进行遍历的，因而当我在遍历以后层节点的时候，必定须要记录以后层所有节点的left、right，保留到队列中，进行下一轮遍历，直到节点没有left、right，则代表曾经遍历到了最初一层了。 因而须要借助一个辅助数据结构——队列，队列先进后出，合乎层序遍历的程序性，其实此题就是队列 + 广度优先遍历 的一道联合题。 间接看代码吧： /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number[][]} */var levelOrder = function(root) { const res = [], queue = []; queue.push(root); if(root === null) return res; while(queue.length !== 0) { let level = []; const length = queue.length for(var i = 0; i < length; i++) { var node = queue.shift(); level.push(node.val); node.left && queue.push(node.left); node.right && queue.push(node.right); } res.push(level); } return res;};接下来咱们逐行剖析代码。 ...

1. 字典简介与汇合相似，字典也是一种存储惟一值的数据结构，但它是以键值对的模式来存储。应用 ES6 Map1.1 字典的罕用操作const m = new Map();// 增m.set('a', 'aa');m.set('b', 'bb');// 删m.delete('b');m.clear();// 改m.set('a', 'aaa')// 查m.get('a');2. LeetCode： 349. 两个数组的交加 2.1 解题思路求nums1 和 nums2 多都有的值用字典建设一个映射关系，记录nums1里有的值遍历nums2,找出nums1 里也有的值2.2 解题步骤新建一个字典，遍历nums1,填充字典遍历nums2, 遇到字典里的值就选出，并从字典中删除。/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */var intersection = function (nums1, nums2) { // 汇合Set 实现形式 // return [...new Set(nums1)].filter(item => nums2.includes(item)) const map = new Map(); nums1.forEach(n => { map.set(n, true) }) const res = []; nums2.forEach(n => { if (map.get(n)) { res.push(n); map.delete(n); } }) return res};3. LeetCode：20. 无效的括号 ...

什么是贪婪算法贪婪法，又称贪婪算法，贪心算法，在对问题求解时，总是做出在以后看来最好的抉择，冀望通过每个阶段的部分最优抉择达到全局最优，但后果不肯定最优 实用场景：简略的说，问题可能分解成子问题来解决，子问题的最优解能递推到最终问题的最优解，就能用贪婪算法的到最初的最优解，这种子问题最优解称为最优子结构 贪婪算法与动静布局的不同点在于它对每个子问题的解决方案都做出以后的最优抉择，不能回退，而动静布局会保留之前的运算后果，并依据之前的后果进行抉择，有回退的性能，贪婪是动静布局的理想化的状况。 122. 交易股票的最佳时机 II（medium）给你一个整数数组 prices ，其中 prices[i] 示意某支股票第 i 天的价格。 在每一天，你能够决定是否购买和/或发售股票。你在任何时候 最多 只能持有 一股 股票。你也能够先购买，而后在 同一天 发售。 返回 你能取得的 最大 利润 。 示例 1： 输出：prices = [7,1,5,3,6,4]输入：7解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能取得利润 = 5 - 1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能取得利润 = 6 - 3 = 3 。 总利润为 4 + 3 = 7 。示例 2： ...

前言回溯，就是无脑冲，碰壁之后就回撤一步持续搞，属于一种暴力解题的思路； 实际上也是如此，当咱们在遇到一些分类探讨的问题，无奈想到比拟精妙的解决方案，咱们第一工夫思考到的就是暴力枚举所有状况，而后再做解决，而 回溯 就是这样的一个暴力法 下一个 tab 学习一下惯例的排序算法吧 注释在做回溯题 的过程中，会发现很迷茫，因为很多题如同不须要返回，在执行下一步的过程中，我就做好断定，而后将可能的失败遏制住了，这个时候，个别能持续往下走的，都属于还行的操作，咱们其实能够把这种形式叫做 剪枝 我一度陷入沉思，是不是回溯就没用了呢，是不是只有脑瓜还行，其实剪枝就好了，还回溯啥，直到想起回溯的核心思想，它其实是一种暴力解法， 也就是如果你能用其余办法，其实不必回溯,是比拟好的思路，个别状况下，回溯的复杂度会比拟高 那么到底什么时候用回溯呢？那种你没法子预设终局，或者说你的抉择不单单关联相邻层的抉择，而是会对更深层都有影响，比方说 51. N 皇后 咱们需要求的是残缺的棋盘，每一层的抉择，都会影响整个棋盘的的布局，这个时候想在下棋那一刻就将全副可能状况想进去，太难了，这时候用回溯 就是很好的抉择 而对于一些只与下层有影响，这个时候剪枝 也不失是一个好的抉择； 其实在做系列总结的时候，会尽可能用系列的办法去解答，然而一题多解也是咱们谋求的，而且咱们最初想要实现的，必定是不局限与某写法，而是只有看到了，就能 a 进去； 所以致力将大部分惯例的 tab 温习一遍，而后再缓缓填补，总结属于本人的解题计划，才是做总结的目标吧； 与大家一起致力呀 题目汇总46. 全排列剖析 不含反复数字，要求的是全排列，所以不同程序的排列都得算上，这样在枚举过程中要晓得本人已经获取过哪些值在枚举过程中缓存两个数组 arr,getIndex, arr 是枚举过程中的数组， getIndex 是走过值状态，如果以后 arr 走过对应的下标的值为1，没有走过就是 0在每一层给长期数组 arr 增加值的时候，须要保障不会反复增加，能够在每一次遇到的时候再遍历 arr，因为值是惟一的，也是能够的；在这里是用空间换工夫，用 getIndex 数组缓存对应的状态，每一次查找的复杂度是 O(1)每一次须要枚举残缺的数组，须要枚举 n 次所以工夫复杂度为 O(n2),空间复杂度 O(n)var permute = function (nums) { let ret = []; const dfs = (arr, getIndex) => { if (arr.length === nums.length) { ret.push(arr); return; } for (let i = 0; i < nums.length; i++) { const num = nums[i]; if (!!getIndex[i]) continue; // 如果存在，则代表曾经有这个值了 getIndex[i] = 1; dfs([...arr, num], getIndex); getIndex[i] = 0; } }; const getIndexArr = new Array(nums.length) dfs([], getIndexArr); return ret;};47. 全排列 II剖析 ...

什么是动静布局动静布局，英文：Dynamic Programming，简称DP，将问题合成为互相重叠的子问题，通过重复求解子问题来解决原问题就是动静布局，如果某一问题有很多重叠子问题，应用动静布局来解是比拟无效的。 求解动静布局的外围问题是穷举，然而这类问题穷举有点特地，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动静布局问题肯定会具备「最优子结构」，能力通过子问题的最值得到原问题的最值。另外，尽管动静布局的核心思想就是穷举求最值，然而问题能够变幻无穷，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」能力正确地穷举。重叠子问题、最优子结构、状态转移方程就是动静布局三要素 动静布局和其余算法的区别动静布局和分治的区别：动静布局和分治都有最优子结构 ，然而分治的子问题不重叠动静布局和贪婪的区别：动静布局中每一个状态肯定是由上一个状态推导进去的，这一点就辨别于贪婪，贪婪没有状态推导，而是从部分间接选最优解，所以它永远是部分最优，然而全局的解不肯定是最优的。动静布局和递归的区别：递归和回溯可能存在十分多的反复计算，动静布局能够用递归加记忆化的形式缩小不必要的反复计算动静布局的解题办法递归+记忆化(自顶向下)动静布局（自底向上）[外链图片转存中...(img-2XygXnrR-1668751529822)] 解动静布局题目的步骤依据重叠子问题定义状态寻找最优子结构推导状态转移方程确定dp初始状态确定输入值斐波那契的动静布局的解题思路[外链图片转存中...(img-994raFxo-1668751529824)] 动画过大，点击查看 暴力递归//暴力递归复杂度O(2^n)var fib = function (N) { if (N == 0) return 0; if (N == 1) return 1; return fib(N - 1) + fib(N - 2);};递归 + 记忆化var fib = function (n) { const memo = {}; // 对已算出的后果进行缓存 const helper = (x) => { if (memo[x]) return memo[x]; if (x == 0) return 0; if (x == 1) return 1; memo[x] = helper(x - 1) + helper(x - 2); return memo[x]; }; return helper(n);};动静布局const fib = (n) => { if (n <= 1) return n; const dp = [0, 1]; for (let i = 2; i <= n; i++) { //自底向上计算每个状态 dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n];};滚动数组优化const fib = (n) => { if (n <= 1) return n; //滚动数组 dp[i]只和dp[i-1]、dp[i-2]相干，只保护长度为2的滚动数组，一直替换数组元素 const dp = [0, 1]; let sum = null; for (let i = 2; i <= n; i++) { sum = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = sum; } return sum;};动静布局 + 降维，（降维能缩小空间复杂度，但不利于程序的扩大）var fib = function (N) { if (N <= 1) { return N; } let prev2 = 0; let prev1 = 1; let result = 0; for (let i = 2; i <= N; i++) { result = prev1 + prev2; //间接用两个变量就行 prev2 = prev1; prev1 = result; } return result;};509. 斐波那契数（easy）斐波那契数 （通常用 F(n) 示意）造成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，前面的每一项数字都是后面两项数字的和。也就是： ...

注释 plus堆是动静求极值的数据结构，所以当遇到须要一直取极值的时候，就能够思考用堆了 舒适提醒，倡议每一道题都本人 new 一个堆，这样能力发现堆之美，其实就是不会再次遇到 topK 的时候只能用冒泡来做。 行文至此也该完结了，如果有 10 个关注，那就更新一下下一 part， dp 或者树吧， thx。 二叉堆的创立剖析 -- 小顶堆这里是一个小顶堆，特点就是根节点的值比子节点的值都小，通常用作经典的前 K 大次要有两个办法， 一个是回升，这里次要用作构建堆的时候，整顿堆用的一个是下沉，这里次要用于弹出堆顶元素后，置换了堆顶值之后应用的，这里用到 this.data[0]，是因为这个办法个别是构建残缺的堆之后，才会应用其余的办法不是不能够，只是为了保障灵活性，临时就先做个简易版，前面再思考，因为办法越多，其实兼容性就越差了class MinHeap { constructor(len) { this.data = []; this.data[0] = len; // 第一个节点用来寄存堆的大小 -- 某些特定环境比拟好用 } // 下浮 down(index) { const size = this.data[0]; while (index << 1 <= size) { let child = index << 1; if (child !== size && this.data[child] > this.data[child + 1]) { child += 1; //如果右节点更小，就右节点作为下一个接盘的节点 } if (this.data[index] > this.data[child]) { // 替换一下 [this.data[index], this.data[child]] = [ this.data[child], this.data[index], ]; index = child; } else { // 只有其中一次生效了，那么就没必要持续往下查找了 break; } } } // 都是从最底层开始算的 upper() { // 这里不必 this.data[0] 是因为以后构建的堆可能还没达到堆的最大值，所以不能应用 let index = this.data.length - 1; while (index >> 1 > 0) { let father = index >> 1; if (this.data[index] < this.data[father]) { // 子节点比父节点要小，则网上走 [this.data[index], this.data[father]] = [ this.data[father], this.data[index], ]; index = father; } else { break; } } } }剖析 -- 大顶堆绝对于初始版的小顶堆，这一版的大顶堆增加了两个办法， pop 和 addadd 办法能够写在应用堆的地位，然而为了让它和堆的第一个值匹配，所以写在了类办法外面，不便对 size 的增加pop 是为了取出堆顶元素，堆是为了解决动静取极值而存在的数据结构，所以必然要取出整顿的过程。class MaxHeap { constructor() { this.data = []; this.data[0] = 0; // 第一个值是以后堆的size } down(index) { const len = this.data.length; // 是下标极限 while (index << 1 < len) { let child = index << 1; if (child !== len && this.data[child + 1] > this.data[child]) { child++; } if (this.data[child] > this.data[index]) { [this.data[child], this.data[index]] = [ this.data[index], this.data[child], ]; index = child; } else { break; } } } upper() { let index = this.data[0]; // 最大下标 while (index >> 1 > 0) { const father = index >> 1; if (this.data[index] > this.data[father]) { [this.data[father], this.data[index]] = [ this.data[index], this.data[father], ]; index = father; } else { break; } } } add(value) { // 先加在最开端 this.data.push(value); this.data[0]++; // size 也加一下 this.upper(); // 整顿一下 } // 弹出堆顶元素 pop() { const last = this.data[0]; [this.data[1], this.data[last]] = [this.data[last], this.data[1]]; //替换堆顶和堆尾的值 const ret = this.data.pop(); this.data[0]--; this.down(1); // 整顿 return ret; }}215. 数组中的第K个最大元素剖析 ...

前言明天没啥前言，分治很难，次要难在如何拆分后比拟好治理合并，这比二分这些只有拆了就完结要难上一个 level，所以这里属于出入 分治 这种想法的思维，后续会尽可能的锤炼这样的做法；做一道分治，如果能用其余办法代替的时候，个别分治不算是最优解，起码很伤脑子； 注释概念分治即分而治之，所以要分成两局部 分：将一个规模为 N 的问题合成为若干个规模较小的子问题治：依据子问题的解求原问题关键点肯定是先分再治治肯定是利用分的后果进行的，也就是说治依赖于分实用场景如果问题能够被合成为若干个规模较小的雷同问题这些被合成的问题的后果能够进行合并这些被合成的问题是互相独立的，不蕴含重叠的子问题分支和 dp 有很深分割，且与二分法也有关联，实质上，二分就是始终只有分没有治的分治，因为二分的后果只须要找到那个较小的雷同问题的解，不须要再合并起来；技巧思考子问题的求解边界，应用函数来定义问题思考如何将子问题的解进行合并 -- 假如子问题曾经计算好了，如何合并起来思考编码思路 -- 个别应用递归分治和二分，dp的异同二分只对问题进行分，分完间接舍弃；而分治不仅须要对问题进行合成，还须要对多个问题进行治理分治和 dp 都波及到问题的问题，并且都须要保障子问题的不重不漏。 dp 是通过递推和抉择进行转译，从非凡推广到一半分治也可能波及到抉择；dp 解决的问题往往随同重叠子问题，而分治则不是小结如果一个问题被文杰为若干个不重叠的独立子问题，并且子问题能够推到出原问题，咱们就能够用分治来解决；题目53. 最大子序和剖析 -- 分治法 先分 -- 使用递归的办法将数组区间的左右节点 l,r 一直二分进来，直到 l === r 为止，这个时候须要思考怎么治理了再治 -- 这里最终要求的是最大的间断子序列，咱们先思考两个值合并，最大的状况是三种, Math.max(L,R,L+R), 然而当再多一点值的时候，咱们就须要扭转一下 Math.max(LMAX,RMAX,L_Rmax+R_Lmax) 这里的 LMAX, RMAX 是指合并两个区间的最大值，L_Rmax 是指在 L 区间蕴含 right 起点为最大区间；所以治的过程中，每个区间须要有4个变量，别离是 totalSum 区间总和，leftSum 蕴含 left 节点的最大间断子列和, rightSum 蕴含 right 节点的最大间断子列和, maxSum 区间的最大值初始化的时候，也就是单个节点的时候，4个变量都是惟一值 nums[l]开始合并治理， totalSum 间接将两个节点的 totalSum 合并即可；leftSum 总是和 left 区间相干 -- Math.max(left.maxSum,left.totalSum+right.leftSum), 要不间接区左区间的最大值，要不全取左区间 + 右区间的 leftSum同理 rightSum 也总是和 right 区间相干 -- Math.max(right.maxSum,right.totalSum+left.rightSum)maxSum 分三种状况 -- Math.max(left.maxSum,right.maxSum,left.rightSum+right.leftSum)所以先递后归，工夫复杂度为 O(n)var maxSubArray = function (nums) { const recursion = (l,r) => { if(l === r) { return { totalSum: nums[l], leftSum: nums[l], rightSum: nums[l], maxSum: nums[l] } } const mid = ((r-l)>>2)+l const left = recursion(l,mid) const right = recursion(mid+1,r) return { totalSum:left.totalSum+right.totalSum, // 区间内值的总和 leftSum:Math.max(left.leftSum,left.totalSum+right.leftSum), // 左边界开始的最大间断子列和 rightSum: Math.max(right.rightSum,right.totalSum+left.rightSum), // 区间哟偶边界完结的最大间断子列和 maxSum:Math.max(left.maxSum,right.maxSum,left.rightSum+right.leftSum) } } return recursion(0,nums.length-1).maxSum}剖析 -- 贪婪 ...

什么是动静布局动静布局，英文：Dynamic Programming，简称DP，将问题合成为互相重叠的子问题，通过重复求解子问题来解决原问题就是动静布局，如果某一问题有很多重叠子问题，应用动静布局来解是比拟无效的。 求解动静布局的外围问题是穷举，然而这类问题穷举有点特地，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动静布局问题肯定会具备「最优子结构」，能力通过子问题的最值得到原问题的最值。另外，尽管动静布局的核心思想就是穷举求最值，然而问题能够变幻无穷，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」能力正确地穷举。重叠子问题、最优子结构、状态转移方程就是动静布局三要素 动静布局和其余算法的区别动静布局和分治的区别：动静布局和分治都有最优子结构 ，然而分治的子问题不重叠动静布局和贪婪的区别：动静布局中每一个状态肯定是由上一个状态推导进去的，这一点就辨别于贪婪，贪婪没有状态推导，而是从部分间接选最优解，所以它永远是部分最优，然而全局的解不肯定是最优的。动静布局和递归的区别：递归和回溯可能存在十分多的反复计算，动静布局能够用递归加记忆化的形式缩小不必要的反复计算动静布局的解题办法递归+记忆化(自顶向下)动静布局（自底向上） 解动静布局题目的步骤依据重叠子问题定义状态寻找最优子结构推导状态转移方程确定dp初始状态确定输入值斐波那契的动静布局的解题思路 动画过大，点击查看 暴力递归//暴力递归复杂度O(2^n)var fib = function (N) { if (N == 0) return 0; if (N == 1) return 1; return fib(N - 1) + fib(N - 2);};递归 + 记忆化var fib = function (n) { const memo = {}; // 对已算出的后果进行缓存 const helper = (x) => { if (memo[x]) return memo[x]; if (x == 0) return 0; if (x == 1) return 1; memo[x] = helper(x - 1) + helper(x - 2); return memo[x]; }; return helper(n);};动静布局const fib = (n) => { if (n <= 1) return n; const dp = [0, 1]; for (let i = 2; i <= n; i++) { //自底向上计算每个状态 dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n];};滚动数组优化const fib = (n) => { if (n <= 1) return n; //滚动数组 dp[i]只和dp[i-1]、dp[i-2]相干，只保护长度为2的滚动数组，一直替换数组元素 const dp = [0, 1]; let sum = null; for (let i = 2; i <= n; i++) { sum = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = sum; } return sum;};动静布局 + 降维，（降维能缩小空间复杂度，但不利于程序的扩大）var fib = function (N) { if (N <= 1) { return N; } let prev2 = 0; let prev1 = 1; let result = 0; for (let i = 2; i <= N; i++) { result = prev1 + prev2; //间接用两个变量就行 prev2 = prev1; prev1 = result; } return result;};509. 斐波那契数（easy）斐波那契数 （通常用 F(n) 示意）造成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，前面的每一项数字都是后面两项数字的和。也就是： ...

一、前言 个别状况下，遍历数组（或者字符串）操作，都是采纳单指针从前往后或者从后往前顺次拜访数组（或者字符串）中的元素。 而对于以下状况，只采纳单指针解决，则会徒增工夫复杂度和空间复杂度： 例如：找到两个数使得它们相加之和等于指标数，采纳单指针解决，则须要嵌套循环，使得工夫复杂度增长为 O(n^2)；再例如：翻转数组，采纳单指针解决，则须要额定内存空间，使得空间复杂度增长为 O(n)；利用双指针技巧则能够优化上述解决方案： 第一个例子：能够先对采纳数组进行排序预处理，再创立前后指针向两头遍历，遍历的工夫复杂度为 O(n)，整体工夫复杂度次要取决于排序算法，通常为 O(nlogn)；第二个列子：一个指针负责遍历，另外一个指针负责替换元素，从而使得空间复杂度为 O(1)；双指针没有简单的定义，总结起来次要解决两类问题： 将嵌套循环转化为单循环问题；通过指针记录状态，从而优化空间复杂度；上面的实战剖析会让你感触双指针的威力。 二、167. 两数之和 II - 输出有序数组给定一个已依照升序排列 的有序数组，找到两个数使得它们相加之和等于指标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。 这道题目采纳单指针的做法只能通过嵌套循环枚举所有两数之和的办法来解决，工夫复杂度为 O(n^2)。 凑巧本题中的数组曾经是有序数组，那么间接创立前后指针： 如果两数之后大于 target，尾指针向前挪动；如果两数之和小于 target，头指针向后挪动； 上述代码利用双指针技巧胜利地将工夫复杂度升高为 O(n)。 三、344. 反转字符串编写一个函数，其作用是将输出的字符串反转过去。输出字符串以字符数组 char[] 的模式给出。 本题采纳单指针的办法，须要创立一个额定的数组来保留翻转后的元素，空间复杂度为 O(n)。 利用双指针技巧，则能够在遍历的过程中同时实现替换元素的操作，工夫复杂度升高为 O(1)： 雷同类型的题目还有： 【345. 反转字符串中的元音字母】四、141. 环形链表给定一个链表，判断链表中是否有环。为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。 在链表这种数据结构中，采纳前文所说的前后指针并不一定无效（例如单向链表），这种状况下，双指针的表现形式为：快慢指针。 快慢指针指的是：设置两个前进方向雷同但速度不同的指针。 本题中，设置每次挪动一个单位的慢指针和每次挪动两个单位的快指针，那么他们必定会在环内相遇： 参考视频：传送门 雷同类型的题目还有： 【26. 删除排序数组中的反复项】五、125. 验证回文串给定一个字符串，验证它是否是回文串，只思考字母和数字字符，能够疏忽字母的大小写。阐明：本题中，咱们将空字符串定义为无效的回文串。 回文字符串问题是双指针的经典利用，同时也是面试题中的常客。 ...

前言上一 part 刚写完二分和滑窗，他们都属于非凡的双指针办法，所以这一 part 间接汇总一下除了非凡的二分和滑窗外的其余双指针写法 这里次要是快慢指针和端点指针， 解决一些一次遍历搞不掂，多个指针协商干活不累的题目，基本上感觉属于一种解题上的思路，一次不行，我就两次的样子； 所以刷完根底双指针，而后滑窗和二分后，这种思路在今后解题上应该会不定期能冒出来吧； 所以下期学习另外一种解题思路，回溯吧； 注释双指针在很多罕用的数据结构和算法中，都曾经用到，比方说链表遍历过程中，就能够用双指针找中位数，找环；在二分法中用到的也是双指针；滑动窗口，以及双滑动窗口等 所以双指针是一个解决问题的思路，当设置一个指针遍历不足以造成对照的时候，能够设置更多的参照指针来服务本人，只是个别状况两个指针足以，所以这种解决思路称为双指针 快慢指针比拟常见的双指针模式，个别是快指针走 2 步，慢指针走 1 步，达到一种对照的作用；解决了形如链表的中位数，链表有环 等问题； 还有一种是读写指针，这种也是一个指针 read 先走，而后触发某个条件之后，才会让 write 走，也就造成了快慢的成果； 左右端点指针最常见的就是二分法，都是设置 l r 指针，而后向两头合拢；所以所有的二分法的应用也是双指针的应用 还有一种就是排好序之后，依据最大值和最小值之间的运算来求值的，这个时候也须要端点指针 找反复值的时候，转换成链表找环 -- 快慢指针的变形在做快慢指针的题目的时候，咋一看题目和快慢指针没有一毛线关系，然而个别都是迭代啊，或者反复值啊什么的，反正就是须要进行雷同的运算,须要判断是否已经呈现过雷同的值, 这个时候，要不就用 hashMap 缓存一波，要不就用快慢指针，将原题转成类型链表的构造，next 指针就是对应的迭代函数，而后求是否有环(202. 高兴数), 或者求环的入口地位（287. 寻找反复数） 当然下面这种属于非凡题目的非凡做法，比方说 287. 寻找反复数 那是因为这里的下标和值刚好没法齐全重合，且有反复数，要是值也是从 [0,n-1]，那就没法子用值当下标的写法了 题目汇总题目142. 环形链表 II剖析 典型的快慢指针写法，在链表专题写过相应的题解了环形链表 II做一下这个题，是为了下一题的前置var detectCycle = function(head) { const emptyNode = new ListNode() emptyNode.next = head; if(!head) return null let slow = fast = emptyNode while(fast && fast.next){ slow = slow.next fast = fast.next.next if(slow === fast){ // 相交了，证实相交了 let next = emptyNode while(next!== slow){ next = next.next slow = slow.next } // 相交的时候，就是环入口 return slow } } return null}287. 寻找反复数剖析 -- 双指针法（快慢指针） ...

前言常常会有人问，作为前端，你在理论工作中用到过哪些算法，而我答复个别是，树和位运算； 想想 webpack 上的那些依赖的版本类型，想想 react 源码中的那些 flag 的定义和运算，我感觉还是很有必要去学习一下位运算到底能解决一些什么问题 注释其实位运算最典型的就运算符号就是，| & ^ 三个，然而使用到具体题目上就很灵便了，根本这个系列也只是温习一下，晓得一下如何用二进制的位来存储获取值，而用二进制位这样的数据结构时，位运算就是关联应用的算法了； 其余的，我也不晓得啊，就是感觉位运算好酷，有一些非凡的题目，间接用位运算就能几行解决，所以学学能够装个逼，因而这个系列临时比拟少，就两套经典题而已，当前在补充吧； PS: 其实整顿题目至此，曾经有 6 组了，最后是为了温习写过的代码，然而越写越感觉本人懂的少，开始疲乏的，然而坚持下去应该会有播种的吧，加油 题解136. 只呈现一次的数字只呈现一次的数字 -- 所有题目都是线性工夫复杂度，空间复杂度都是常数级复杂度剖析剖析 -- 1个单值，其余是两个 已知 a ^ a = 0, 0 ^ a = a ,所以将 nums 中所有值进行异或解决，呈现两次的都会被打消，而最初的后果就是惟一一次呈现的那个值工夫复杂度 O(N)，空间复杂度O(1)var singleNumber = function(nums) { return nums.reduce((prev,cur) => prev ^ cur,0) // 0 和任何值异或都等于任何值，所以以 0 为初始值};137. 只呈现一次的数字 II剖析 -- 1个单值 x ，其余是 3 个 y1,y2... 将 nums 数组与 [0,31] 的位进行 & 比拟，找出在这个位上存在的值的数量 count；如果 count 整除 3， 证实这个位上只存在 yi；如果不整除，证实单值 x 在这个位上，那么后果要加上这个位留神，因为 num 的取值范畴是 [-pow(2,31),pow(2,31)-1], 所以第 31 位 是能够取到的，所以遍历的时候要遍历到第 31位,取到正负值；工夫复杂度 O(31∗N)，空间复杂度O(1)/** * @剖析 --- 一个值呈现 1 次，其余值呈现 3次 -- * 1. 将所有值相加，转成二进制，而后雷同的值在同一个位上必定也是一样的，而后对每一个位进行除 3 取余，失去的值就是惟一一个呈现 1 次的值了 */var singleNumber = function (nums) { let ret = 0; for (let i = 0; i < 32; i++) { const temp = 1 << i; let count = 0; nums.forEach((num) => { if (num & temp) count++; }); // 在 i 这个位上，有 count 这么多个值 if (count % 3) ret |= temp; } return ret;};260. 只呈现一次的数字 III只呈现一次的数字 -- 所有题目都是线性工夫复杂度，空间复杂度都是常数级复杂度剖析如果题目看错是只有一个值呈现一次，其余都呈现两次，那么间接异或就能够得出后果；当初是有两个值只呈现一次，所以异或和失去的就是这两个值的异或和，所以须要将原数组拆解成两份 ...

什么是动静布局动静布局，英文：Dynamic Programming，简称DP，将问题合成为互相重叠的子问题，通过重复求解子问题来解决原问题就是动静布局，如果某一问题有很多重叠子问题，应用动静布局来解是比拟无效的。 求解动静布局的外围问题是穷举，然而这类问题穷举有点特地，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动静布局问题肯定会具备「最优子结构」，能力通过子问题的最值得到原问题的最值。另外，尽管动静布局的核心思想就是穷举求最值，然而问题能够变幻无穷，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」能力正确地穷举。重叠子问题、最优子结构、状态转移方程就是动静布局三要素 动静布局和其余算法的区别动静布局和分治的区别：动静布局和分治都有最优子结构 ，然而分治的子问题不重叠动静布局和贪婪的区别：动静布局中每一个状态肯定是由上一个状态推导进去的，这一点就辨别于贪婪，贪婪没有状态推导，而是从部分间接选最优解，所以它永远是部分最优，然而全局的解不肯定是最优的。动静布局和递归的区别：递归和回溯可能存在十分多的反复计算，动静布局能够用递归加记忆化的形式缩小不必要的反复计算动静布局的解题办法递归+记忆化(自顶向下)动静布局（自底向上） 解动静布局题目的步骤依据重叠子问题定义状态寻找最优子结构推导状态转移方程确定dp初始状态确定输入值斐波那契的动静布局的解题思路 动画过大，点击查看 暴力递归//暴力递归复杂度O(2^n)var fib = function (N) { if (N == 0) return 0; if (N == 1) return 1; return fib(N - 1) + fib(N - 2);};递归 + 记忆化var fib = function (n) { const memo = {}; // 对已算出的后果进行缓存 const helper = (x) => { if (memo[x]) return memo[x]; if (x == 0) return 0; if (x == 1) return 1; memo[x] = helper(x - 1) + helper(x - 2); return memo[x]; }; return helper(n);};动静布局const fib = (n) => { if (n <= 1) return n; const dp = [0, 1]; for (let i = 2; i <= n; i++) { //自底向上计算每个状态 dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n];};滚动数组优化const fib = (n) => { if (n <= 1) return n; //滚动数组 dp[i]只和dp[i-1]、dp[i-2]相干，只保护长度为2的滚动数组，一直替换数组元素 const dp = [0, 1]; let sum = null; for (let i = 2; i <= n; i++) { sum = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = sum; } return sum;};动静布局 + 降维，（降维能缩小空间复杂度，但不利于程序的扩大）var fib = function (N) { if (N <= 1) { return N; } let prev2 = 0; let prev1 = 1; let result = 0; for (let i = 2; i <= N; i++) { result = prev1 + prev2; //间接用两个变量就行 prev2 = prev1; prev1 = result; } return result;};322. 零钱兑换 (medium)视频解说：传送门 ...

前言回溯，就是无脑冲，碰壁之后就回撤一步持续搞，属于一种暴力解题的思路； 实际上也是如此，当咱们在遇到一些分类探讨的问题，无奈想到比拟精妙的解决方案，咱们第一工夫思考到的就是暴力枚举所有状况，而后再做解决，而 回溯 就是这样的一个暴力法 下一个 tab 学习一下惯例的排序算法吧 注释在做回溯题 的过程中，会发现很迷茫，因为很多题如同不须要返回，在执行下一步的过程中，我就做好断定，而后将可能的失败遏制住了，这个时候，个别能持续往下走的，都属于还行的操作，咱们其实能够把这种形式叫做 剪枝 我一度陷入沉思，是不是回溯就没用了呢，是不是只有脑瓜还行，其实剪枝就好了，还回溯啥，直到想起回溯的核心思想，它其实是一种暴力解法， 也就是如果你能用其余办法，其实不必回溯,是比拟好的思路，个别状况下，回溯的复杂度会比拟高 那么到底什么时候用回溯呢？那种你没法子预设终局，或者说你的抉择不单单关联相邻层的抉择，而是会对更深层都有影响，比方说 51. N 皇后 咱们需要求的是残缺的棋盘，每一层的抉择，都会影响整个棋盘的的布局，这个时候想在下棋那一刻就将全副可能状况想进去，太难了，这时候用回溯 就是很好的抉择 而对于一些只与下层有影响，这个时候剪枝 也不失是一个好的抉择； 其实在做系列总结的时候，会尽可能用系列的办法去解答，然而一题多解也是咱们谋求的，而且咱们最初想要实现的，必定是不局限与某写法，而是只有看到了，就能 a 进去； 所以致力将大部分惯例的 tab 温习一遍，而后再缓缓填补，总结属于本人的解题计划，才是做总结的目标吧； 与大家一起致力呀 题目汇总46. 全排列剖析 不含反复数字，要求的是全排列，所以不同程序的排列都得算上，这样在枚举过程中要晓得本人已经获取过哪些值在枚举过程中缓存两个数组 arr,getIndex, arr 是枚举过程中的数组， getIndex 是走过值状态，如果以后 arr 走过对应的下标的值为1，没有走过就是 0在每一层给长期数组 arr 增加值的时候，须要保障不会反复增加，能够在每一次遇到的时候再遍历 arr，因为值是惟一的，也是能够的；在这里是用空间换工夫，用 getIndex 数组缓存对应的状态，每一次查找的复杂度是 O(1)每一次须要枚举残缺的数组，须要枚举 n 次所以工夫复杂度为 O(n2),空间复杂度 O(n)参考视频：传送门 var permute = function (nums) { let ret = []; const dfs = (arr, getIndex) => { if (arr.length === nums.length) { ret.push(arr); return; } for (let i = 0; i < nums.length; i++) { const num = nums[i]; if (!!getIndex[i]) continue; // 如果存在，则代表曾经有这个值了 getIndex[i] = 1; dfs([...arr, num], getIndex); getIndex[i] = 0; } }; const getIndexArr = new Array(nums.length) dfs([], getIndexArr); return ret;};47. 全排列 II剖析 ...

前言上一 part 刚写完二分和滑窗，他们都属于非凡的双指针办法，所以这一 part 间接汇总一下除了非凡的二分和滑窗外的其余双指针写法 这里次要是快慢指针和端点指针， 解决一些一次遍历搞不掂，多个指针协商干活不累的题目，基本上感觉属于一种解题上的思路，一次不行，我就两次的样子； 所以刷完根底双指针，而后滑窗和二分后，这种思路在今后解题上应该会不定期能冒出来吧； 所以下期学习另外一种解题思路，回溯吧； 注释双指针在很多罕用的数据结构和算法中，都曾经用到，比方说链表遍历过程中，就能够用双指针找中位数，找环；在二分法中用到的也是双指针；滑动窗口，以及双滑动窗口等 所以双指针是一个解决问题的思路，当设置一个指针遍历不足以造成对照的时候，能够设置更多的参照指针来服务本人，只是个别状况两个指针足以，所以这种解决思路称为双指针 快慢指针比拟常见的双指针模式，个别是快指针走 2 步，慢指针走 1 步，达到一种对照的作用；解决了形如链表的中位数，链表有环 等问题； 还有一种是读写指针，这种也是一个指针 read 先走，而后触发某个条件之后，才会让 write 走，也就造成了快慢的成果； 左右端点指针最常见的就是二分法，都是设置 l r 指针，而后向两头合拢；所以所有的二分法的应用也是双指针的应用 还有一种就是排好序之后，依据最大值和最小值之间的运算来求值的，这个时候也须要端点指针 找反复值的时候，转换成链表找环 -- 快慢指针的变形在做快慢指针的题目的时候，咋一看题目和快慢指针没有一毛线关系，然而个别都是迭代啊，或者反复值啊什么的，反正就是须要进行雷同的运算,须要判断是否已经呈现过雷同的值, 这个时候，要不就用 hashMap 缓存一波，要不就用快慢指针，将原题转成类型链表的构造，next 指针就是对应的迭代函数，而后求是否有环(202. 高兴数), 或者求环的入口地位（287. 寻找反复数） 当然下面这种属于非凡题目的非凡做法，比方说 287. 寻找反复数 那是因为这里的下标和值刚好没法齐全重合，且有反复数，要是值也是从 [0,n-1]，那就没法子用值当下标的写法了 题目汇总快慢指针环形链表 II寻找反复数删除有序数组中的反复项 II高兴数左右端点指针最靠近的三数之和乘积小于K的子数组有序数组的平方爱吃香蕉的珂珂救生艇二分法（这里只有链接，具体能够去看二分的题）模板1 二分查找x 的平方根猜数字大小排列硬币搜寻旋转排序数组 模板2第一个谬误的版本寻找峰值寻找旋转排序数组中的最小值寻找旋转排序数组中的最小值 II 模板3在排序数组中查找元素的第一个和最初一个地位找到 K 个最靠近的元素 其余Pow(x, n)无效的齐全平方数寻找比指标字母大的最小字母两个数组的交加两个数组的交加 II两数之和 II - 输出有序数组寻找反复数4.寻找两个正序数组的中位数宰割数组的最大值滑动窗口（也是属于双指针，感觉匹配快慢指针一点）找到字符串中所有字母异位词无反复字符的最长子串最小笼罩子串长度最小的子数组904.水果成篮和雷同的二元子数组K 个不同整数的子数组最长湍流子数组最大间断1的个数 III替换子串失去均衡字符串统计「柔美子数组」将 x 减到 0 的最小操作数参考视频：传送门 题目142. 环形链表 II剖析 典型的快慢指针写法，在链表专题写过相应的题解了环形链表 II做一下这个题，是为了下一题的前置var detectCycle = function(head) { const emptyNode = new ListNode() emptyNode.next = head; if(!head) return null let slow = fast = emptyNode while(fast && fast.next){ slow = slow.next fast = fast.next.next if(slow === fast){ // 相交了，证实相交了 let next = emptyNode while(next!== slow){ next = next.next slow = slow.next } // 相交的时候，就是环入口 return slow } } return null}287. 寻找反复数剖析 -- 双指针法（快慢指针） ...

前言常常会有人问，作为前端，你在理论工作中用到过哪些算法，之前我答复是，树和位运算，而最近在学习网络模块，发现了和前端，起码是和网络相干的一种算法，那就是 滑动窗口； 咱们晓得在 HTTP1.1 发送申请，TCP 会将申请传输到服务端，而对于 TCP 协定，最重要的能力之一就是管制流速； 当发送方须要发送很多申请的时候，这些申请会阻塞在某一个缓存中期待 TCP 发送，这个前面还有源源不断的申请发动，那总不能一下子全堵在缓存上吧，会炸掉的，这个时候这个模型就是滑动窗口了 发送过程有三个状态： 绿色是发送并连贯胜利的浅绿色是发送，然而还没有收到 ACK 响应的，这个时候有可能会挂掉，所以这个时候发送方还得存着这个申请随时筹备重发红色是期待发送的前面那些就是被阻塞的申请了这个时候 TCP 可能缓存的申请数就是一个窗口，每当浅绿色转成深绿色，那么窗口就能够像左边滑动，而窗口还保留的状态仍然能够复用，这就是滑动窗口 的魅力了 滑动窗口最大特点是，滑动窗口过程中，保留在窗口里的数据状态间接复用，不须要再次构建，节约资源； 那么接下来咱们通过做题来相熟一下滑窗，并看看是否有更多不一样的状况吧； 注释依据滑窗窗口大小是否固定，分成了两种：固定大小的窗口 和 可变窗口大小; 前言谈及的 TCP 中的滑窗状况，其实是一个固定大小的滑窗，当然也能够先给定局部大小，而后依据流速进行扩大，那是后续的操作了； 而更多的状况是不固定大小的滑窗，这类滑窗个别都是创立过程中，一股脑子将资源耗尽去扩充窗口，达到一个阈值，而后再膨胀窗口，依据具体题目，达到一个均衡了； 这其实就如同是一个疾速试错过程，先将状况推到极致了，而后退出对应的变量来膨胀窗口，找到比拟适合的一个状况，等到合规的状况在窗口里突破了，就从新扩大； 滑窗其实在了解题意的时候，又有点一分为二的感觉，就是我能够将窗口里的状态和窗口外的状态切离开，然而他们又是此消彼长的关系，这样一直衡量,达到一个动态平衡的状态，就是某些题的后果 模板固定大小的窗口 l 初始化为 0初始化 r, 使得 r-l+1 就是窗口大小同时挪动 l 和 r判断窗口内的间断元素是否满足题目限定的条件可变窗口大小 l r 都初始化为 0r 指针挪动一步判断窗口内的间断元素是否满足条件 满足，再判断是否须要更新最优解；如果须要则更新，并尝试通过挪动 l 指针放大窗口的大小不满足，则持续参考视频：传送门 双滑窗景象一般的不定滑窗都是先走 r 指针，而后达到触发条件，而后膨胀 l 指针，膨胀到不达标之后进行，而后 r 指针重新启动然而有那么一些题目，当 r 指针达标后, l 指针在一段范畴内 [l1,l2)，且可能与后续的 [r1,r2) 任何两个指针形成的滑窗都会形成合规的滑窗那么这个时候用单个指针 l 膨胀到不符合要求的 l2,那么就只产生 [l1,l2）与 r1 的条件，而原本应该合规的 lx-rx 都被干掉了(lx 在 [l1,l2] 中)，因为这个时候 l 曾经跑到 l2 处了这个时候就须要开两个指针 l1, l2 ，每次固定 r 指针的时候，咱们找出第一个符合要求的 l1, 和截止地位 l2,而后持续让 r 走，挪动过程始终保持两个滑窗 [l1.r],[l2,r]，能够保障在整个挪动过程所有的状况都思考到了这类题目都是求数量，比方说某种状况的子数组有多少个，这样就得将所有状况都弄出来，然而如果只是要求一个极值，比方说这些符合要求的状况中，最小是多少，那么就没必要用双滑窗了，因为 r 指针的挪动必定会扩充窗口，所以 l 指针只须要保留对应的极值(第一个或者最初一个)，而后求出极值即可最初滑窗是双指针的一种非凡状况，咱们在应用双指针解决问题的时候，可能不会思考前一个窗口里的状态值，只是将所有状况都思考进行，这样就会有很多计算是反复的，滑窗就是一种优化了的双指针状况。 ...

前言并查集是合并汇合的形式，对于一些关联性的汇合，合并查问的形式能够使得题目分类解决，是一种题型的解决方案，这里最要害是构思好汇合之间的关联关系； 在这一 part 中，仅仅只是对局部题做了理解学习，远远没有达到能够手撕的水平，然而面试过程中遇到的并不算特地多，所以属于一个理解补充的 part，大家能够学习学习，还是挺有意思的； 下一 part 做分治法 注释这是一篇水文，国庆回家也就保持每天做一丢丢题目，而后放弃一下手感，而并查集的确比拟好的锤炼一下脑子，脑子不够转不过去，所以能够尝试学习并做一下，他的根本模板不会很简单，根本如下： class UnionFind { constructor(n){ // 缓存两个数组，父节点数组和以后节点的子节点数量数组 // 1. 初始化的父节点数组都是指向本人以后的下标的； -- 其中下标是惟一值 this.parents = new Array(n).fill(1).map((_,index) => index) // 2. 初始化的子节点数量数组都是只有一个；-- 其中下标是惟一值 this.sizes = new Array(n).fill(1) // } // 寻找 x 的根节点 find(x){ if(this.parents[x] === x) return x return this.find(this.parents[x]) } // 合并两个并查集 connect(x,y){ const px = this.find(x) const py = this.find(y) if(px === py) return // 如果他们是一个汇合，则间接返回 if(this.sizes[px]>this.sizes[py]){ // px 挂的节点更多，所以将 py 也挂过来 this.parents[py] =px this.sizes[px]++ }else{ this.parents[px] =py this.sizes[py]++ } }}当然，具体问题上，可能能够简化或者强化 connect 办法，来解决具体的问题，这就须要同学本人去学习探讨了； ...

前言学习算法的时候，总会有一些让人生畏的名词，比如动静布局，贪婪算法 等，听着就很难；而这一 part 就是为了攻破之前始终没有零碎学习的 贪婪算法； 有一说一，做了这些贪婪题，其实并没感觉发现了什么套路新大陆等，因为贪婪有的时候很奇妙，而且想到就是想到了，没想到可能就不必贪婪去做了，所以这属于做完只是刷了存在感的 part； 惟一的播种就是加重了对贪婪的恐怖，明确它也就是一种 部分贪婪导致全局贪婪失去最优解 的一种思路办法，所以当前遇到了，也就能平心静气的去学习应用它了； 下一 part 去做一下比拟难的并查集 注释455. 散发饼干剖析 -- 贪婪 用最大的饼干满足胃口最大的小孩，这样就能部分最优求出全局最优，能够满足最多的小孩因为 g,s 都须要取最大，所以须要排序最初用两个端套的遍历找出最优解工夫复杂度 O(n+m)var findContentChildren = function (g, s) { g.sort((a,b) => a-b) s.sort((a,b) => a-b) let ret = 0 let sl = s.length-1; let gl = g.length-1 while(gl>=0){ // 人没了，饼干能够还存在 if(s[sl]>=g[gl] && sl>=0){ // 最大的饼干是否满足最大胃口的孩子 ret++ sl-- } gl-- } return ret}376. 摆动序列剖析 -- 贪婪 间断数字之间差值是正负交替的，叫做摆动序列；边缘状况，如果只有1个值，或者两个不相等的值，也是摆动序列如果呈现 0， 则间接不是摆动序列了如果部分符合要求，依照条件部分删除不符合要求的值，就是贪婪的做法工夫复杂度 O(n)参考视频：传送门var wiggleMaxLength = function(nums) { if(nums.length<2) return nums.length let ret = 1 // 从 1 开始是因为要求的是整个摆动序列的长度，所以先初始化1，而后遇到极值递增即可 let preDiff = 0 // 初始化第一个差值；设置为0，则无论真正第一个差值是多少，失去的都是 0 let curDiff = 0 for(let i = 1;i<nums.length;i++){ curDiff = nums[i]- nums[i-1] // 差值必须是正负数，如果是 0 则跳过 if(curDiff === 0) continue if(preDiff * curDiff <= 0){ ret++ preDiff = curDiff } } return ret};53. 最大子序和剖析 -- 贪婪 ...

一、前言 二分搜索算法自身并不是特地简单，外围点次要集中在： 有序数组：指的是一个递增或者递加的区间（非凡状况如：【852. 山脉数组的峰顶索引】）；两头数：用来确定搜寻指标落在左半区间还是右半区间；进入 Medium 难度之后，这两个条件个别不会间接给出，须要解题者依据题目自行结构。 二、LeetCode 实战1、378. 有序矩阵中第K小的元素 由程度和垂直方向为递增数组的条件，能够失去以后二维空间中的左上角为最小值，右下角为最大值，所以有序数组即为最小值到最大值的整数递增序列。 题目要求计算出第 k 小的元素，那么从有序数组中筛选进去的两头数并不能间接与 k 进行比拟，须要在二维空间中找出以后两头数是第几小的数字，再与 k 进行比拟： 如果以后两头数比第 k 小的元素要大，那么第 k 小元素必然在左半区间；否则必然落在右半区间；通过以后二维数组程度和垂直方向枯燥递增的个性，能够从左下角开始搜寻以后两头数为第几小的数字。 相似解题思路的还有： 【74. 搜寻二维矩阵】2、875. 爱吃香蕉的珂珂 这道题要求咱们找出一个最慢吃香蕉的速度，使得在 H 小时能够吃完 N 堆香蕉。 珂珂最慢吃香蕉的速度是每个小时吃1根，最快的速度是每小时吃掉 max(N)，有序数组即为 1 到 max(N) 的整数递增序列。 从有序数组中找出一个速度之后，还须要计算以后速度下吃完所有香蕉所需的工夫和 H 相比拟： 如果以后速度下吃完所有香蕉的工夫大于 H，那么所须要搜寻的速度 K 必然落在右半区间；反之，K 落在左半区间；参考视频：传送门 3、658. 找到 K 个最靠近的元素 这道题要求咱们找到一个起始下标 index，使得 [index, index + k) 中的数字最靠近 x 。 该题并没有暗藏有序数组这一条件，所以这道题目的难点在于如何通过两头下标来判断 index 落在哪个区间： 首先思考数组边界的问题，如果 mid + k > arr.length - 1，那么 index 必然在落在左半区间；接下来利用最靠近 x 和优先选择最小元素（也就是优先选择右边的元素）这两个条件：如果间隔 x 右边的差值小于间隔 x 左边的差值，那么 index 必然落在左半区间； ...

一、二分搜索算法1、简介 二分搜寻是一种在有序数组中查找某一特定元素的搜索算法。 二分搜索算法的工夫复杂度为 O(log n)，相比拟顺序搜索的 O(n) 工夫复杂度，它要快很多。 例如，在一个长度为一百万的有序数组中，采纳顺序搜索，最坏的状况须要执行一百万次，而二分搜索算法只须要二十次！ 从上图，读者能够很容易发现，二分搜寻的要害就是通过目标值与两头值的比拟，将搜寻区间放大一半，这也是为什么有序数组是二分搜索算法的重要前提。 2、代码实现 由前文可知，二分搜寻并不是一个特地简单的算法，然而想通过代码正确地实现它，并不是一件易事。 首先要求出数组的两头下标（整数），从而获取到两头值： const mid = Math.floor((start + end) / 2) 读者可能第一工夫想到的就是上述写法，然而在一些极其的状况，start + end 可能间接超出最大的平安整数，所以更加的审慎的写法如下： const mid = Math.floor(start + (end - start) / 2) 最初就是搜寻区间如何一直地放大一半，对于很多初学者来说，常常会将其写成一个死循环，这里倡议放弃搜寻区间左闭右开的写法： while (start < end) { const mid = Math.floor(start + (end - start) / 2) if (arr[mid] < target) { start = mid + 1 } else { end = mid }}二、LeetCode 实战1、744. 寻找比指标字母大的最小字母 这道题目次要考查二分搜索算法的根本实现： ...

一、前言 本篇次要介绍双指针技巧的第二类题型：对数组进行预处理之后，再采纳双指针遍历。 在 Medium 难度的题目中，此类问题能够演绎为 K-Sum 问题： 两数之和：【881. 救生艇】；三数之和：【16. 最靠近的三数之和】、【15. 三数之和】、【923. 三数之和的多种可能】；四数之和：【18. 四数之和】；二、881. 救生艇第 i 集体的体重为 people[i]，每艘船能够承载的最大分量为 limit。每艘船最多可同时载两人，但条件是这些人的分量之和最多为 limit。返回载到每一个人所需的最小船数。(保障每个人都能被船载)。 由题意可知，保障所需的最小船数，意味着每一趟尽可能地搭载两个人，并且他们的分量最靠近最大分量，以便后续趟次可能组成两个人。 解题的要害就在于每趟尽可能地从数组中找出和值小于最大分量的最大值最小值的二元组。 那么对数组排序预处理之后，能够很容易地从左侧找到最小值，右侧找到最大值，双指针再向两头遍历，即可解题。 三、16. 最靠近的三数之和 给定一个包含 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最靠近。返回这三个数的和，假设每组输出只存在惟一答案。 奢侈解法就是通过三层循环枚举各种排列状况来找到最靠近的和值，工夫复杂度为 O(n^3)。 这里能够利用降维思维，将其转化为两数之和的问题，那么解题思路和【881. 救生艇】一模一样： 工夫复杂度被升高为 O(nlogn+n^2)。参考视频：传送门 四、15. 三数之和给定一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不反复的三元组。 有了上述题目的铺垫，再看本题，是不是会浮现以下解题范式： 降维思维，将三数之和转化为两数之和的问题；对数组进行排序，将双循环问题转化为单循环问题；对于不反复三元数组这一条件，同学们第一工夫可能会想到采纳 HashTable 来去重，然而整个双指针解题的过程中，三个数始终保持着非递加序列的个性，那么遇到反复数字间接跳过即可： ...

一、前言 《JavaScript刷LeetCode拿offer-双指针技巧》中，简略地介绍了双指针技巧相比拟单指针的长处，以及联合 Easy 难度的题目带大家进一步理解双指针的利用。 进入 Medium 难度之后，解题的关键在于如何结构双指针以及确定指针挪动的规定，解题办法能够演绎为以下两类： 滑动窗口算法（Sliding Window Algorithm）;对数组进行预处理（如：排序，前缀和等等），再利用双指针遍历;这两种办法都能够将双循环问题转化为单循环问题，从而无效地升高算法的工夫复杂度。本篇次要介绍滑动窗口算法以及相干题型的解题思路，第二类题型会放在下一篇中解说。 滑动窗口算法具体的表现形式为：左右指针始终保护一个满足条件的窗口值，右指针负责向前遍历，当窗口值不满足条件时，将左指针指向的元素移出窗口，同时向前挪动左指针。 上面，结合实际的题目来了解如何应用滑动窗口算法。 二、567. 字符串的排列给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否蕴含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。 本道题目实际上能够转化为是否能找出满足以下条件的 s2 字符串的子串： 该子串的长度和 s1 字符串的长度相等；该子串中蕴含的字符以及对应的数量和 s1 字符串雷同；那么联合滑动窗口算法，须要保护一个长度为 s1 字符串长度的窗口，并且窗口中的字符以及相应的数量与 s1 雷同。 字符数量通过 HashTable 来保护，在 JavaScript 语言中能够采纳 Map 数据结构。 三、904. 水果成篮 在一排树中，第 i 棵树产生 tree[i] 型的水果。你能够从你抉择的任何树开始，而后反复执行以下步骤：1、把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。2、挪动到以后树右侧的下一棵树。如果左边没有树，就停下来。请留神，在抉择一颗树后，你没有任何抉择：你必须执行步骤 1，而后执行步骤 2，而后返回步骤 1，而后执行步骤 2，依此类推，直至进行。你有两个篮子，每个篮子能够携带任何数量的水果，但你心愿每个篮子只携带一种类型的水果。用这个程序你能收集的水果总量是多少？ 这道题很显著合乎滑动窗口算法的特色：保护一个至少有两种水果的窗口。 当窗口中呈现第三种水果时，须要从窗口的右边顺次移除果树，保障以后窗口只含有两种水果，这里能够采纳 HashTable 记录同一类型果树最初呈现的坐标来优化工夫复杂度。 最初，在窗口挪动的过程中，计算相应的水果总量即可。参考视频：传送门 四、3. 无反复字符的最长子串给定一个字符串，请你找出其中不含有反复字符的 最长子串 的长度。 这道题目与上一道《904. 水果成篮》的解题思路如出一撤： 保护一个不含反复字符的窗口；当窗口不满足条件时，从窗口右侧顺次移除字符，确保窗口再次满足条件，同样能够采纳 HashTable 记录雷同字符最初呈现的下标来优化工夫复杂度；五、713. 乘积小于K的子数组给定一个正整数数组 nums。找出该数组内乘积小于 k 的间断的子数组的个数。 本题须要保护一个乘积小于 k 的窗口，与上述题目相比，本题不须要太多技巧去计算无效的窗口值，它的难点在于满足乘积的数组的长度正好是以后不重复子数组的数量。 ...

一、前言 个别状况下，遍历数组（或者字符串）操作，都是采纳单指针从前往后或者从后往前顺次拜访数组（或者字符串）中的元素。 而对于以下状况，只采纳单指针解决，则会徒增工夫复杂度和空间复杂度： 例如：找到两个数使得它们相加之和等于指标数，采纳单指针解决，则须要嵌套循环，使得工夫复杂度增长为 O(n^2)；再例如：翻转数组，采纳单指针解决，则须要额定内存空间，使得空间复杂度增长为 O(n)；利用双指针技巧则能够优化上述解决方案： 第一个例子：能够先对采纳数组进行排序预处理，再创立前后指针向两头遍历，遍历的工夫复杂度为 O(n)，整体工夫复杂度次要取决于排序算法，通常为 O(nlogn)；第二个列子：一个指针负责遍历，另外一个指针负责替换元素，从而使得空间复杂度为 O(1)；双指针没有简单的定义，总结起来次要解决两类问题： 将嵌套循环转化为单循环问题；通过指针记录状态，从而优化空间复杂度；上面的实战剖析会让你感触双指针的威力。 二、167. 两数之和 II - 输出有序数组给定一个已依照升序排列 的有序数组，找到两个数使得它们相加之和等于指标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。 这道题目采纳单指针的做法只能通过嵌套循环枚举所有两数之和的办法来解决，工夫复杂度为 O(n^2)。 凑巧本题中的数组曾经是有序数组，那么间接创立前后指针： 如果两数之后大于 target，尾指针向前挪动；如果两数之和小于 target，头指针向后挪动； 上述代码利用双指针技巧胜利地将工夫复杂度升高为 O(n)。 三、344. 反转字符串编写一个函数，其作用是将输出的字符串反转过去。输出字符串以字符数组 char[] 的模式给出。 本题采纳单指针的办法，须要创立一个额定的数组来保留翻转后的元素，空间复杂度为 O(n)。 利用双指针技巧，则能够在遍历的过程中同时实现替换元素的操作，工夫复杂度升高为 O(1)： 雷同类型的题目还有： 【345. 反转字符串中的元音字母】四、141. 环形链表给定一个链表，判断链表中是否有环。为了示意给定链表中的环，咱们应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。参考视频：传送门 在链表这种数据结构中，采纳前文所说的前后指针并不一定无效（例如单向链表），这种状况下，双指针的表现形式为：快慢指针。 快慢指针指的是：设置两个前进方向雷同但速度不同的指针。 本题中，设置每次挪动一个单位的慢指针和每次挪动两个单位的快指针，那么他们必定会在环内相遇： 雷同类型的题目还有： 【26. 删除排序数组中的反复项】五、125. 验证回文串给定一个字符串，验证它是否是回文串，只思考字母和数字字符，能够疏忽字母的大小写。阐明：本题中，咱们将空字符串定义为无效的回文串。 回文字符串问题是双指针的经典利用，同时也是面试题中的常客。 六、27. 移除元素 ...

一、前言 上一篇中介绍了如何采纳 DFS 和 BFS 的搜寻思维去实现二叉树的前序遍历、中序遍历、后序遍历以及分层遍历。 这一节次要介绍 Medium 难度中比拟常见的一种题型：依据各种遍历结构二叉树。 二、1008. 先序遍历结构二叉树返回与给定先序遍历 preorder 相匹配的二叉搜寻树（binary search tree）的根结点 本道题目要求结构一棵 BST，使得它的前序遍历序列与给定的 preorder 匹配。 首先，对二叉树进行前序遍历，能够失去如下序列： 根节点 --> 左子树 --> 右子树 显然，依据前序序列，能够确定第一个元素就是根节点，那么接下来的问题就是如何找到左右子树的宰割点？ 回顾一下 BST 的个性： 左子树的元素都比根元素小；右子树的元素都比根元素大；BST 中不存在反复的元素；联合上述性质：通过根节点与序列中元素的大小比拟能够失去左右子树的宰割点。 三、105. 从前序与中序遍历序列结构二叉树依据一棵树的前序遍历与中序遍历结构二叉树。留神: 你能够假如树中没有反复的元素。 本道题目要求结构一棵一般的二叉树，而非 BST。 前序遍历：根节点 --> 左子树 --> 右子树 中序遍历: 左子树 --> 根节点 --> 右子树 从上述两个遍历序列中，大家应该曾经发现宰割左右子树的条件就藏在中序遍历中。 依据前序遍历失去根元素，再遍历中序遍历序列失去根元素的下标，从而宰割左右子树。如果二叉树中存在反复元素，那么这种计划是行不通的，这也是此类型题目一个重要的条件。 参考视频：传送门 四、106. 从中序与后序遍历序列结构二叉树 依据一棵树的中序遍历与后序遍历结构二叉树。留神:你能够假如树中没有反复的元素。 本题的解题思路与上一道题的解题思路一模一样，所以正好借用本道题目介绍一下工夫复杂度的优化。 上一题解题代码的耗时操作次要在于频繁地应用 shift、indexOf 和 slice。 对于 indexOf 操作，能够采纳 HashTable 代替，这是经典的空间换工夫的优化形式。 ...

一、前言 Medium 难度次要考查联合二叉树性质的 CRUD 操作，而这所有的根底都离不开遍历二叉树。 二叉树是图的子集，因此同样实用以下两种搜寻思维： DFS（深度优先搜寻）：沿着根节点递归上来，遇到叶子节点则向上回溯；BFS (广度优先搜寻)：依照二叉树的档次拜访，通常采纳队列保留每个档次的节点。因为二叉树自身的定义就是递归的，所以采纳递归解决起来，代码更容易了解。然而递归的效率绝对比较慢，次要起因在于：一个函数被调用的工夫和空间老本开销很大，递归太多很可能导致调用栈溢出的问题。上一篇中也提到能够采纳尾递归的书写形式，让 JavaScript 引擎去将递归优化成迭代，从而解决性能上的问题。 然而在一些状况下，尾递归并没有那么好写，所以本文会同时给出递归和迭代的解决方案。 接下来，通过具体的题目解析，带大家理解 DFS 和 BFS 搜寻思维在二叉树中的利用。 二、102. 二叉树的档次遍历给定一个二叉树，返回其按档次遍历的节点值。（即逐层地，从左到右拜访所有节点）。1、BFS 这道题目要求按档次遍历节点，很合乎 BFS 搜寻思维的定义，所以代码也很好了解。 这里须要利用队列（queue）来保留每一层须要拜访的节点，须要特地留神队列的个性是先进先出，而本题要求每一层从左到右遍历，所以须要先将左子树放入队列。 2、DFS 采纳 DFS 搜寻思维，须要留神在递归的过程中记录以后节点的档次信息： 参考视频：传送门 三、145. 二叉树的后序遍历 给定一个二叉树，返回它的 后序 遍历。 二叉树中最常见的就是依照根节点拜访秩序定义的三种遍历形式： 先序遍历：首先拜访根，再先序遍历遍历左子树，最初先序遍历右子树；中序遍历：首先中序遍历左子树，再拜访根，最初中序遍历右子树；后序遍历：首先后序遍历左子树，再后序遍历右子树，最初拜访根；以本道题的后序遍历为例，尝试递归和迭代两种不同的办法： 1、递归实现 DFS 从定义中，大家应该可能设想到递归的代码如何书写： 2、迭代实现 DFS 本道题目采纳迭代实现 DFS 不太容易了解，次要因为迭代不能像递归那样向上回溯，所以迭代向下遍历的过程中，无奈保障根节点最初拜访。 再回顾一下后序遍历最终失去的序列： 左子树 --> 右子树 --> 根 如果必须先拜访根节点，那么是不是能够失去这样的序列： 根 --> 右子树 --> 左子树 最初，再将该序列反转，是不是就是本题所要求解的后序遍历！ 这里咱们利用栈后进先出的个性，将右子树最初推动栈，使得右子树先进行深度搜寻： ...

一、前言 本难度的题目次要考查二叉树的基本概念和操作。 1、基本概念 树是计算机科学中常常用到的一种非线性数据结构，以分层的模式存储数据。二叉树是一种非凡的树结构，每个节点最多有两个子树，通常子树被称作“左子树”和“右子树”。 以上述图片为例，介绍二叉树相干的几个术语： 节点的度：节点领有子树的数量，图中节点 7 的度为 2；叶子节点：度为 0 的节点，图中节点 2 就是一个叶子节点；节点的档次：根节点的层定义为 1，根的孩子为第二层节点，顺次类推；树的深度：树中的最大节点层，图中树的深度为 3；在 JavaScript 中，能够创立 TreeNode 对象来形容树的节点： function TreeNode(val) { this.val = val; this.left = this.right = null;} 另外二叉树也有不同的体现状态，最常见的就是二叉查找树（Binary Search Tree）,它具备以下性质： 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；任意节点的左、右子树也别离为二叉查找树；没有键值相等的节点。二叉查找树相比拟其余数据结构的劣势在于查找、插入的工夫复杂度较低，为 O(logn)，并且对它进行中序遍历操作之后，能够失去一个有序序列，这使得它成为出题的常客。 2、基本操作 二叉树常常考查的问题次要基于以下操作： 计算二叉树的深度；先序遍历：首先拜访根，再先序遍历遍历左子树，最初先序遍历右子树；中序遍历：首先中序遍历左子树，再拜访根，最初中序遍历右子树；后序遍历：首先后序遍历左子树，再后序遍历右子树，最初拜访根；档次遍历：依照节点的档次拜访；二叉树非常适合采纳递归思维解决，尽管递归十分消耗内存，然而它写出的代码可读性十分强，另外能够通过尾递归的书写形式，让 JavaScript 引擎将其优化为迭代的形式，从而大幅度地优化工夫和空间的复杂度。 二、104. 二叉树的最大深度给定一个二叉树，找出其最大深度。 这是一道计算二叉树深度的题目，利用递归思维：一直计算子树的深度，即可失去整个二叉树的深度。 雷同类型的题目： 【111. 二叉树的最小深度】；三、144. 二叉树的前序遍历给定一个二叉树，返回它的 前序 遍历。 采纳递归实现二叉树的前序遍历的代码，可读性十分强： 参考视频：传送门 同样的实现中序遍历以及后序遍历，是不是小菜一碟! 四、783. 二叉搜寻树结点最小间隔给定一个二叉搜寻树的根结点 root, 返回树中任意两节点的差的最小值。 解题思路：二叉搜寻树的中序遍历序列为递增序列； 雷同类型的题目： 【530. 二叉搜寻树的最小相对差】；【897. 递增程序查找树】；【653. 两数之和 IV - 输出 BST】；五、563. 二叉树的坡度给定一个二叉树，计算整个树的坡度。一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。整个树的坡度就是其所有节点的坡度之和。 解题思路：在后序遍历的过程中，先计算左子树和值以及右子树和值，再计算以后节点的坡度，最初更新以后子树的和值。 ...

一、链表 链表（Linked List）是一种常见的根底数据结构，也是线性表的一种。 一个线性表是 n 个具备雷同个性的数据元素的无限序列，线性表的存储构造分为两类：程序表（数组）和链表。 链表相比拟程序表，它并不会依照线性的顺序存储数据，而是在每个节点里存储到下一个节点的指针，在 JavaScript 中，咱们能够这样形容链表中的节点： 二、链表 vs 数组 存储形式的不同： 数组在应用前须要先申请占用内存的大小，并且是间断的内存区域，不适宜 动静存储，正是因为间断内存存储，使得 数组随机拜访的工夫复杂度为 O(1)。链表则克服了数组须要事后晓得数据大小的毛病，能够充沛地利用内存空间，实现动态内存治理，然而因为每个节点减少了指针域，空间开销比拟大。操作工夫复杂度的不同： 数据类型读取工夫复杂度写入工夫复杂度链表O(n)O(1)数组O(1)O(n) 后面从存储形式的剖析中，能够晓得数组具备随机拜访的能力，然而拜访链表中的元素则须要遍历链表，因而工夫复杂度为 O(n)。 链表中写入操作只须要将以后节点的前驱和后继节点的指针断开即可，所以工夫复杂度为 O(1)。 然而因为数组是间断内存的个性，写入操作并没有那么简略，以删除数组首位元素为例，数组须要执行以下两步操作： 删除首位元素。O(1)从第二位元素开始，顺次向前挪动一位。O(n)所以对于任意地位的写入，链表尽管须要先执行 O(n) 的遍从来定位元素，然而它的整体效率依然比数组高。 三、Easy 典型题型剖析1、【1290. 二进制链表转整数】给你一个单链表的援用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制示意模式。请你返回该链表所示意数字的 十进制值 。 这道题目次要考查链表遍历的基本操作：迭代链表节点的 next 指针。 参考视频：传送门 2、【876. 链表的两头结点】给定一个带有头结点 head 的非空单链表，返回链表的两头结点。如果有两个两头结点，则返回第二个两头结点。 这道题目比拟切实的解题思路是：第一次遍历求出链表长度，从而计算出两头地位，第二次遍历依据两头地位找出两头节点。 上面给出的解法，是常常用到的双指针技巧中的快慢指针，奇妙地求解出两头节点： 3、【83. 删除排序链表中的反复元素】给定一个排序链表，删除所有反复的元素，使得每个元素只呈现一次。 因为本道题目中的链表是一个排序链表，所以只考查了链表中删除节点的操作：扭转指标节点的前驱节点的 next 指针，即可删除指标节点。 4、【206. 反转链表】反转一个单链表。 第一种解法：先遍历链表获取翻转后的链表节点值的数组，再遍历链表替换节点的值。 第二种解法，利用链表的个性，简化为一次遍历实现翻转操作。 以下面的链表为例，翻转流程如下： 解题代码如下： 5、【141. 环形链表】给定一个链表，判断链表中是否有环。 第一种解法：遍历链表，利用 HashMap 记录节点对象，如果呈现反复的节点则有环。 ...

工作太忙没有工夫刷算法题，面试的时候好心虚。这里双手奉上40道LeetCode上经典面试算法题，整顿的内容有点长，倡议先珍藏，缓缓消化，在来年顺利拿到称心的offer。 1、[LeetCode] 两数之和给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你能够假如每个输出只对应一种答案，且同样的元素不能被反复利用。示例:给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1] var twoSum = function(nums, target) { var len = nums.length; for(var i=0; i<len; i++){ for(var j=i+1; j<len;j++){ if(nums[i] + nums[j] == target){ return [i, j]; } } } return [];}; 2、[LeetCode]门路总和给定一个二叉树和一个指标和，判断该树中是否存在根节点到叶子节点的门路，这条门路上所有节点值相加等于指标和。阐明: 叶子节点是指没有子节点的节点。 var hasPathSum = function(root, sum) { if (!root) return false; var cur = sum-root.val; if (!root.left&&!root.right&&cur==0) return true; if (!root.left) return hasPathSum(root.right, cur); if (!root.right) return hasPathSum(root.left, cur); return hasPathSum(root.left, cur)||hasPathSum(root.right, cur); };3、[LeetCode]二叉树的最小深度给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短门路上的节点数量。阐明: 叶子节点是指没有子节点的节点。 ...

前言博主最近在刷leetcode，做到二叉树套题的时候发现很多题的解题思路都是基于二叉树的层序遍从来实现的，因而写下这篇文章，记录一下二叉树层序遍历这件"神器"在实战的使用。 [leetcode] 102.二叉树的层序遍历 二叉树的层序遍历与传统的前序、中序、后序遍历都有一些区别，他是按层级、从左到右、从上到下进行遍历的，因而当我在遍历以后层节点的时候，必定须要记录以后层所有节点的left、right，保留到队列中，进行下一轮遍历，直到节点没有left、right，则代表曾经遍历到了最初一层了。 因而须要借助一个辅助数据结构——队列，队列先进后出，合乎层序遍历的程序性，其实此题就是队列 + 广度优先遍历 的一道联合题。 间接看代码吧： /** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number[][]} */var levelOrder = function(root) { const res = [], queue = []; queue.push(root); if(root === null) return res; while(queue.length !== 0) { let level = []; const length = queue.length for(var i = 0; i < length; i++) { var node = queue.shift(); level.push(node.val); node.left && queue.push(node.left); node.right && queue.push(node.right); } res.push(level); } return res;};接下来咱们逐行剖析代码。 ...

什么是动静布局动静布局，英文：Dynamic Programming，简称DP，将问题合成为互相重叠的子问题，通过重复求解子问题来解决原问题就是动静布局，如果某一问题有很多重叠子问题，应用动静布局来解是比拟无效的。 求解动静布局的外围问题是穷举，然而这类问题穷举有点特地，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动静布局问题肯定会具备「最优子结构」，能力通过子问题的最值得到原问题的最值。另外，尽管动静布局的核心思想就是穷举求最值，然而问题能够变幻无穷，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」能力正确地穷举。重叠子问题、最优子结构、状态转移方程就是动静布局三要素 动静布局和其余算法的区别动静布局和分治的区别：动静布局和分治都有最优子结构 ，然而分治的子问题不重叠动静布局和贪婪的区别：动静布局中每一个状态肯定是由上一个状态推导进去的，这一点就辨别于贪婪，贪婪没有状态推导，而是从部分间接选最优解，所以它永远是部分最优，然而全局的解不肯定是最优的。动静布局和递归的区别：递归和回溯可能存在十分多的反复计算，动静布局能够用递归加记忆化的形式缩小不必要的反复计算动静布局的解题办法递归+记忆化(自顶向下)动静布局（自底向上） 解动静布局题目的步骤依据重叠子问题定义状态寻找最优子结构推导状态转移方程确定dp初始状态确定输入值斐波那契的动静布局的解题思路 动画过大，点击查看 暴力递归//暴力递归复杂度O(2^n)var fib = function (N) { if (N == 0) return 0; if (N == 1) return 1; return fib(N - 1) + fib(N - 2);};递归 + 记忆化var fib = function (n) { const memo = {}; // 对已算出的后果进行缓存 const helper = (x) => { if (memo[x]) return memo[x]; if (x == 0) return 0; if (x == 1) return 1; memo[x] = helper(x - 1) + helper(x - 2); return memo[x]; }; return helper(n);};动静布局const fib = (n) => { if (n <= 1) return n; const dp = [0, 1]; for (let i = 2; i <= n; i++) { //自底向上计算每个状态 dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n];};滚动数组优化const fib = (n) => { if (n <= 1) return n; //滚动数组 dp[i]只和dp[i-1]、dp[i-2]相干，只保护长度为2的滚动数组，一直替换数组元素 const dp = [0, 1]; let sum = null; for (let i = 2; i <= n; i++) { sum = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = sum; } return sum;};动静布局 + 降维，（降维能缩小空间复杂度，但不利于程序的扩大）var fib = function (N) { if (N <= 1) { return N; } let prev2 = 0; let prev1 = 1; let result = 0; for (let i = 2; i <= N; i++) { result = prev1 + prev2; //间接用两个变量就行 prev2 = prev1; prev1 = result; } return result;};509. 斐波那契数（easy）视频解说：传送门 ...

前言某个男人 动静布局,而我作为一个致力称为厨师界最会写算法的前端，总得刷上一部分题，有那么一点发现吧，当初咱们就来聊聊，菜鸡如我，发现了什么。 注释汇总这周学习的当初，我脑壳疼的慌，啥货色都想不到，然而为了不破本人每周都总结一下下的指标，只能水几句了； dp 如同是所有高级菜鸟的一个瓶颈，反正每次说到算法难在哪里，第一个想到的就是 dp， 去吹牛皮说面试他人装逼，就说顺手甩几道 dp 去难为面试者的老哥层出不穷，所以 dp 有一种失望之巅的赶脚，只有翻过它，就能进阶了； 其实学习算法到面试遇到的算法，用到 dp 的时候其实没有，树，链表这些反而是超火的热题，所以 dp 对于前端以面试为目标的算法学习，属于一种积攒吧，就是经典题型学一学，遇到了原题搞一搞，遇到难题间接 pass ，就是高考数学倒数两题的感觉，所以呢，所以把最经典的温习一遍，而后。。我就一菜鸡，我也不晓得, 反正后续应该会持续编吧，会学更深的 dp，毕竟这个货色是真的有意思，有趣味的能够到这里学习一下大神的总结 以上，切实吹不上来了，下线，睡觉；下周做，位运算吧；加油呀 题目汇总股票买卖交易股票的最佳时机交易股票的最佳时机 II交易股票的最佳时机 III交易股票的最佳时机 IV最佳交易股票机会含冷冻期交易股票的最佳时机含手续费打家劫舍打家劫舍打家劫舍 II打家劫舍 III记忆化递归杨辉三角爬楼梯面试题 08.06. 汉诺塔问题其余零钱兑换零钱兑换 II -- 凑计划最长回文子串题目121. 交易股票的最佳时机剖析：参考视频：传送门 交易 1 次， 不须要距离, 不收手续费dp_0 示意没有持有的状态的最大利润，dp_1 示意持有状态下的最小老本2.5. 因为只进行一次交易，所以 dp_1要尽可能大的取，确保买入的老本最小，而 dp_0 也要放弃最高，保障卖出最大状态转移方程 dp_0 = Math.max(dp_0,dp_1+nums[i]), dp_1 = Math.max(dp_1,-nums[i])base case dp_0 =0 dp_1 = -nums[i]var maxProfit = function(prices) { let dp_0 = 0,dp_1 = prices[0] for(let i = 0;i<prices.length;i++){ dp_0 = Math.max(dp_0,dp_1+prices[i]) dp_1 = Math.max(dp_1,-prices[i]) // 因为只会交易一次，这里 } return dp_0}122. 交易股票的最佳时机 II剖析 ...

简介文中所有题目均为精心筛选过的超高频题目，所以大家能够珍藏起来 适用人群针对有肯定数据结构根底(理解链表, 二叉树, 二叉堆, 递归)的基本概念,并对工夫空间复杂度有根本认知的。 食用指南将文中列出的每道题至多手写3遍 面试前能够依照本文整理出来的题目间接过一遍 阐明文章更新频率: 除休息日外,每天在题目下方更新一道题的题解 有LeetCode原题的将贴上原地址，不在文章内做题目形容 Tc: Time complexity (工夫复杂度) Sc: Space complexity (空间复杂度) 题目类型数组篇1.twoSum [要求Tc: O(n) Sc:O(n)] (字节跳动)LeetCode第1题 依照题目要求,咱们第一工夫想到的会是两层循环暴力解法： 解法1：Time = O(n²), Space = O(1) 思路:遍历每个元素nums[j]，并查找是否存在一个值与 target - nums[j] 相等的指标元素。 function twoSum(nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { return [i,j]; } } } return [];}解法2:Time = O(n), Space = O(n)： ...

1. 栈是什么？ 一种先进后出的数据结构；JavaScript没有栈的构造；能够用array实现栈的性能 入栈 push(x);出栈 pop(); const stack = [];// 入栈 stack.push(1);stack.push(2);// 出栈const item1 = stack.pop();const item2 = stack.pop();2. 什么场景下用栈所有后进先出的构造。2.1 十进制转换为二进制：最初余数要顺叙输入才是正确二进制； 后进去的余数反而要排到后面把余数顺次入栈，而后出栈，就能够实现余数顺叙输入。2.2 判断括号是否非法：左括号进栈，右括号出栈，栈空则非法； 越靠后的左括号，对应的右括号越靠前左括号入栈，右括号出栈，最初栈空了就是非法的2.3 函数调用栈：最初调用的函数，最先执行完； 最初调用的函数，最先执行完JS解释器应用栈来管制函数调用的程序3. leetcode: 20. 无效的括号valid-parentheses 3.1 解题思路对于没有闭合的左括号而言，越靠后的左括号，对应的右括号越靠前 输出： "{[]}"输入：true3.2 解题步骤新建一个栈扫描字符串，遇左括号入栈，遇到和栈顶括号类型匹配的右括号就出栈，类型不匹配间接断定为不非法参考视频：传送门/** * @param {string} s * @return {boolean} */var isValid = function (s) { if (s.length % 2 === 1) { return false } const stack = []; for (let i = 0; i < s.length; i += 1) { const c = s[i]; if (c === '(' || c === '{' || c === '[') { stack.push(c) } else { const t = stack[stack.length - 1]; if ( (t === '(' && c === ')') || (t === '{' && c === '}') || (t === '[' && c === ']') ) { stack.pop(); } else { return false; } } } return stack.length === 0;};4. 前端与栈：JS中的函数调用栈4.1 后进先出 const func1 = () => { func2(); }; const func2 = () => { func3(); }; const func3 = () => {}; func1(); ...

什么是树一种分层数据的形象模型。前端工作中常见的树包含：DOM树，级联抉择，树形控件JS中没有树，能够用Object和Array构建树树的罕用操作：深度/广度优先遍历，先中后序遍历深度优先遍历拜访根节点对根节点的children挨个进行深度优先遍历代码展现： const tree = { val: 'a', children: [ { val: 'b', children: [ { val: 'd', children: [] }, { val: 'e', children: [] } ] }, { val: 'c', children: [ { val: 'f', children: [] }, { val: 'g', children: [] } ] } ],};const dfs = (root) => { console.log(root.val); root.children.forEach(dfs);}dfs(tree);输入程序：a -> b -> d -> e -> c -> f -> g 广度优先遍历新建一个队列，把根节点入队把队头出队并拜访把队头的children别离入队反复二，三步，直到队列为空代码展现： const bfs = (root) => { const q = [root]; while (q.length) { const n = q.shift(); console.log(n.val); n.children.forEach((child) => { q.push(child); }) }}bfs(tree); 输入程序：a -> b -> c -> d -> e -> f -> g ...

序章咱们把字符串、数组、正则、排序、递归归为简略算法。接下来系列里，将系列文章里将为大家逐个介绍。 字符串翻转字符串中的单词给定一个字符串，你须要反转字符串中每个单词的字符程序，同时仍保留空格和单词的初始程序。示例 1:输出: "Let's take LeetCode contest"输入: "s'teL ekat edoCteeL tsetnoc"留神：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额定的空格。起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/reverse-words-in-a-string-iii解题思路：要保障单词和空格的初始程序；a)保障单词的先后顺序不能扭转；b)保障单词的反转。 步骤一：先把句子分隔开，宰割开后塞入数组里，数组的先后顺序就是单词的先后顺序。 步骤二：而后把数组的每个单词进行反转。 /** * @param {string} s * @return {string} */var reverseWords = function(s) { let arr = s.split(' ') let result = arr.map(item=>{ return item.split('').reverse().join('') }) return result.join(' ')};代码不够简洁，做上面解决。 var reverseWords = function(s) { return s.split(' ').map(item => item.split('').reverse().join('') ).join(' ')};也能够把空格换成正则去解决，\s示意空格的意思。这里留神把握split的2种用法。 var reverseWords = function(s) { return s.split(/\s/g).map(item => item.split('').reverse().join('') ).join(' ')};还能够这么写。正则/[\w']+/g就是辨认单词的意思，中括号示意可选项，w是字符的意思，[\w']示意可选字符和', 不止一个元素，前面有个+号。 留神：这不是一个比拟好的解法，如果单词中蕴含逗号，圆括号等，正则尾部会匹配到，输入的答案就会不现实。 var reverseWords = function(s) { return s.match(/[\w']+/g).map(item => item.split('').reverse().join('') ).join(' ')}; ...

简略总结一些用 JavaScript 刷力扣的根本调试技巧。最近又刷了点题，总结了些数据结构和算法，心愿能对各为 JSer 刷题提供帮忙。 此篇文章次要想给大家一些开箱即用的 JavaScipt 版本的代码模板，波及到较简单的知识点，原理局部可能会省略，有需要的话前面有工夫能够给局部知识点独自写一篇具体的解说。 BigInt家喻户晓，JavaScript 只能准确表白 Number.MIN_SAFE_INTEGER(-2^53+1) ~ Number.MAX_SAFE_INTEGER(2^53-1) 的值。 而在一些题目中，经常会有较大的数字计算，这时就会产生误差。举个栗子：在控制台输出上面的两个表达式会失去雷同的后果： >> 123456789*123456789 // 15241578750190520>> 123456789*123456789+1 // 15241578750190520而如果应用 BigInt 则能够准确求值： >> BigInt(123456789)*BigInt(123456789) // 15241578750190521n>> BigInt(123456789)*BigInt(123456789)+BigInt(1) // 15241578750190522n能够通过在一个整数字面量前面加 n 的形式定义一个 BigInt ，如：10n，或者调用函数 BigInt()。下面的表达式也能够写成： >> 123456789n*123456789n // 15241578750190521n>> 123456789n*123456789n+1n // 15241578750190522nBigInt 只能与 BigInt 做运算，如果和 Number 进行计算须要先通过 BigInt() 做类型转换。 BigInt 反对运算符，+、*、-、**、% 。除 >>>（无符号右移）之外的位操作也能够反对。因为 BigInt 都是有符号的， >>>（无符号右移）不能用于 BigInt。BigInt 不反对单目 (+) 运算符。 BigInt 也反对 / 运算符，然而会被向上取整。 const rounded = 5n / 2n; // 2n, not 2.5n取模运算在数据较大时，个别没有方法间接去进行计算，通常都会给一个大质数（例如，1000000007），求对质数取模后的后果。 ...

一、题目粗心给定一个蕴含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范畴内（包含 1 和 n），可知至多存在一个反复的整数。 假如 nums 只有 一个反复的整数 ，返回 这个反复的数 。 你设计的解决方案必须 不批改 数组 nums 且只用常量级 O(1) 的额定空间。 示例 1： 输出：nums = [1,3,4,2,2] 输入：2 示例 2： 输出：nums = [3,1,3,4,2] 输入：3 提醒： 1 <= n <= 105nums.length == n + 11 <= nums[i] <= nnums 中 只有一个整数 呈现 两次或屡次 ，其余整数均只呈现 一次进阶： 如何证实 nums 中至多存在一个反复的数字?你能够设计一个线性级工夫复杂度 O(n) 的解决方案吗？起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路这道题给咱们n+1个数，所有的数都在[1, n]区域内，首先让证实必定会有一个反复数，题目要求不能扭转原数组，即不能给原数组排序，又不能用多余空间，那么hash的就不必思考了，又要求工夫小于O(n^2)，只能思考用二分搜寻法了，在区间[1, n]中搜寻，首先求出中点mid，而后遍历整个数组，统计所有小于等于mid的数的个数，如果个数小于等于mid，则阐明反复值在[mid+1, n]之间，反之，反复值在[1, mid-1]之间，而后顺次类推，直到搜寻实现，此时的low就是咱们要求的反复值。 三、解题办法3.1 Java实现public class Solution { public int findDuplicate(int[] nums) { int left = 1; int right = nums.length; while (left < right) { int mid = left + (right - left) / 2; int cnt = 0; for (int num : nums) { cnt += (num <= mid) ? 1 : 0; } if (cnt <= mid) { left = mid + 1; } else { right = mid; } } return right; }}四、总结小记2022/10/25 旦行坏事，莫问前程

各类题的解决方案话不多说，零碎整顿下解题的一些算法和解决方案 二叉树二叉树大多应用递归的形式左右两个元素向下递归。比方： 计算二叉树最大深度 var maxDepth = function (root) { if (root == null) return 0 return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))};将二叉树以二维数组模式体现 var levelOrder = function(root) { let ans = [] helper(root, ans, 0) return ans};function helper(node, ans, i){ if (node == null) return if (i == ans.length) ans.push([]) ans[i].push(node.val) helper(node.left, ans, i + 1) helper(node.right, ans, i + 1)}都是通过递归形式逐层向上来查找二叉树数据。 可能性问题这类题个别是通知你一组数据，而后求出可能性、最小值或最大值。比方： 给定几种面额的硬币和一个总额，应用起码的硬币凑成这个总额。 var coinChange = function (coins, amount) { let max = amount + 1 let dp = new Array(amount + 1) dp.fill(max) dp[0] = 0 for (let i = 1; i < max; i++) { for (let j = 0; j < coins.length; j++) { if (coins[j] <= i) { dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1) } } } return dp[amount] > amount ? -1 : dp[amount]};应用了动静布局（DP），将从 0 到指标额度所需的最小硬币数都列出来。 ...

尽管很多人都感觉前端算法弱，但其实 JavaScript 也能够刷题啊！最近两个月断断续续刷完了 leetcode 前 200 的 middle + hard ，总结了一些刷题罕用的模板代码。 罕用函数包含打印函数和一些数学函数。 const _max = Math.max.bind(Math);const _min = Math.min.bind(Math);const _pow = Math.pow.bind(Math);const _floor = Math.floor.bind(Math);const _round = Math.round.bind(Math);const _ceil = Math.ceil.bind(Math);const log = console.log.bind(console);//const log = _ => {}log 在提交的代码中当然是用不到的，不过在调试时非常有用。然而当代码外面加了很多 log 的时候，提交时还须要一个个正文掉就相当麻烦了，只有将log赋值为空函数就能够了。 举一个简略的例子，上面的代码是能够间接提交的。 // 计算 1+2+...+n// const log = console.log.bind(console);const log = _ => {}function sumOneToN(n) { let sum = 0; for (let i = 1; i <= n; i++) { sum += i; log(`i=${i}: sum=${sum}`); } return sum;}sumOneToN(10);位运算的一些小技巧判断一个整数 x 的奇偶性：x & 1 = 1 (奇数) ， x & 1 = 0 (偶数) ...

一、题目粗心编写一个函数，输出是一个无符号整数（以二进制串的模式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明分量）。 提醒： 请留神，在某些语言（如 Java）中，没有无符号整数类型。在这种状况下，输出和输入都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其外部的二进制示意模式都是雷同的。在 Java 中，编译器应用二进制补码记法来示意有符号整数。因而，在下面的 示例 3 中，输出示意有符号整数 -3。 示例 1： 输出：00000000000000000000000000001011 输入：3 解释：输出的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。 示例 2： 输出：00000000000000000000000010000000 输入：1 解释：输出的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。 示例 3： 输出：11111111111111111111111111111101 输入：31 解释：输出的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。 提醒： 输出必须是长度为 32 的 二进制串 。进阶： 如果屡次调用这个函数，你将如何优化你的算法？起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路思路1:n & 1如果为1，ans=ans+1,而后再n向右移一位，直到n=0，返回ans。留神：因为是Java实现所以要用for 思路2:先判断如果n!=0，ans++，令n = n&(n-1)，循环直到n=0，返回ans。参考他人的思路，没看懂 三、解题办法3.1 Java实现 - 思路1public class Solution2 { // you need to treat n as an unsigned value public int hammingWeight(int n) { int ans = 0; for (int i = 0; i < 32; i++) { ans += n & 1; n >>= 1; } return ans; }}3.2 Java实现 - 思路2public class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int ans = 0; while (n != 0) { ans++; n = n & (n - 1); } return ans; }}四、总结小记2011/10/24 有些货色想不明确，就埋藏心底，发酵一会

一、题目粗心给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请 你返回所有和为 0 且不反复的三元组。 留神：答案中不能够蕴含反复的三元组。 示例 1： 输出：nums = [-1,0,1,2,-1,-4] 输入：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 ...

零 题目：算法（leetcode，附思维导图 + 全副解法）300题之（151）反转字符串中的单词一 题目形容 二 解法总览（思维导图） 三 全副解法1 计划11)代码： // 计划1 “本人。API的链式调用法”。// 思路：// 1）调用 trim() ：去除收尾的空格。// 2）调用 replace(/\s+/g, ' ') ：将n个空格变成1个。// 3）调用 split(' ') ：按空格将字符串切割成数组。// 4）调用 reverse() ：翻转数组。// 5）调用 .join(' ') ：按空格将数组拼接成字符串。var reverseWords = function(s) { // 1）调用 trim() ：去除收尾的空格。 // 2）调用 replace(/\s+/g, ' ') ：将n个空格变成1个。 // 3）调用 split(' ') ：按空格将字符串切割成数组。 // 4）调用 reverse() ：翻转数组。 // 5）调用 .join(' ') ：按空格将数组拼接成字符串。 return s.trim().replace(/\s+/g, ' ').split(' ').reverse().join(' ');}2 计划21)代码： // 计划2 “本人。模拟法”。// 思路：// 1）状态初始化：l = s.length; tempStr = '', resList = [] 。// 2）遍历字符串s，将每个单词塞入数组 resList 。// 3）翻转 resList ，并按空字符拼接成字符串。var reverseWords = function(s) { // 1）状态初始化：l = s.length; tempStr = '', resList = [] 。 const l = s.length; let tempStr = '', resList = []; // 2）遍历字符串s，将每个单词塞入数组 resList 。 for (let i = 0; i < l; i++) { const tempVal = s[i]; if (tempVal === ' ') { if (tempStr.length) { resList.push(tempStr); tempStr = ''; } } else { tempStr += tempVal; } } // 边界：可能有残余的单词！！ if (tempStr.length) { resList.push(tempStr); } // 3）翻转 resList ，并按空字符拼接成字符串。 return resList.reverse().join(' ');}四 资源分享 & 更多1 历史文章 - 总览 ...

一、题目粗心给定一个二叉搜寻树的根节点 root 和一个值 key，删除二叉搜寻树中的 key 对应的节点，并保障二叉搜寻树的性质不变。返回二叉搜寻树（有可能被更新）的根节点的援用。 一般来说，删除节点可分为两个步骤： 首先找到须要删除的节点；如果找到了，删除它。示例 1: 输出：root = [5,3,6,2,4,null,7], key = 3 输入：[5,4,6,2,null,null,7] 解释：给定须要删除的节点值是 3，所以咱们首先找到 3 这个节点，而后删除它。 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 另一个正确答案是 [5,2,6,null,4,null,7]。 示例 2: 输出: root = [5,3,6,2,4,null,7], key = 0 输入: [5,3,6,2,4,null,7] 解释: 二叉树不蕴含值为 0 的节点 示例 3: 输出: root = [], key = 0 输入: [] 提醒: 节点数的范畴 [0, 104].-105 <= Node.val <= 105节点值惟一root 是非法的二叉搜寻树-105 <= key <= 105起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路这道题让咱们删除二叉搜寻树中的一个节点，难点在于删除完节点并补上那个节点的地位后还应该是一棵二叉搜寻树。被删除掉的节点地位，不肯定是由其左右节点补上， 7 / \ 4 8 / \ 2 6 \ / 3 5下面这棵树，如果要删除节点4，那么应该将节点5补到4的地位，这样能力保障还是BST，后果是上面这棵树 ...

一、题目粗心实现RandomizedSet 类： RandomizedSet() 初始化 RandomizedSet 对象bool insert(int val) 当元素 val 不存在时，向汇合中插入该项，并返回 true ；否则，返回 false 。bool remove(int val) 当元素 val 存在时，从汇合中移除该项，并返回 true ；否则，返回 false 。int getRandom() 随机返回现有汇合中的一项（测试用例保障调用此办法时汇合中至多存在一个元素）。每个元素应该有 雷同的概率 被返回。你必须实现类的所有函数，并满足每个函数的 均匀 工夫复杂度为 O(1) 。 示例： 输出 ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] 输入 [null, true, false, true, 2, true, false, 2] 解释 RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // 向汇合中插入 1 。返回 true 示意 1 被胜利地插入。 ...

1.题目形容：给出一棵二叉树，返回其节点值的后序遍历。 2.样例输出：二叉树 = {1,2,3}输入：[2,3,1] 3.解题思路：首先咱们须要理解什么是二叉树的后序遍历：依照拜访左子树——右子树——根节点的形式遍历这棵树，而在拜访左子树或者右子树的时候，咱们依照同样的形式遍历，直到遍历完整棵树。因而整个遍历过程人造具备递归的性质，咱们能够间接用递归函数来模仿这一过程。 定义 postorder(root) 示意以后遍历到 root 节点的答案。依照定义，咱们只有递归调用postorder(root->left) 来遍历 root 节点的左子树，而后递归调用 postorder(root->right) 来遍历 root 节点的右子树，最初将 root 节点的值退出答案即可，递归终止的条件为碰到空节点。class Solution {public: void postorder(TreeNode *root, vector<int> &res) { if (root == nullptr) { return; } postorder(root->left, res); postorder(root->right, res); res.push_back(root->val); } vector<int> postorderTraversal(TreeNode *root) { vector<int> res; postorder(root, res); return res; }};4.代码示例：

1.题目形容：给出一棵二叉树,返回其中序遍历。输出：二叉树 = {1,2,3}输入：[2,1,3] 2.解题思路：递归法首先咱们须要理解什么是二叉树的中序遍历：依照拜访左子树——根节点——右子树的形式遍历这棵树，而在拜访左子树或者右子树的时候咱们依照同样的形式遍历，直到遍历完整棵树。因而整个遍历过程人造具备递归的性质，咱们能够间接用递归函数来模仿这一过程。 3.代码示例：class Solution {public: void inorder(TreeNode* root, vector<int>& res) { if (!root) { return; } inorder(root->left, res); res.push_back(root->val); inorder(root->right, res); } vector<int> inorderTraversal(TreeNode* root) { vector<int> res; inorder(root, res); return res; }};

1.题目形容：翻转一个链表 2.样例输出输出：链表 = 1->2->3->null输入：3->2->1->null 3.题目思路剖析：在这里其实就是使用一个遍历的思维，意思就是先在最开始的时候，定义一个空的区域，定义为指针prev，而后将链表的最前端视为curr，最前端元素的后继元素标为指针*next。在遍历的时候，将curr指向的元素，也就是当初的元素的后继元素指向后面的元素，而后将curr后移，将prev指向当初的元素，next指向前面元素的后继元素，而后再将*curr指向的元素的后继元素指向后面那一个，再持续递推上来。最初返回prev，因为这时候prev刚刚好遍历齐全部的链表。 4.代码示例：class Solution {public: ListNode* reverse(ListNode *head) { ListNode* prev = nullptr; ListNode* curr = head; while (curr) { ListNode* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; }};

1.问题形容：给出一棵二叉树，返回其节点值的前序遍历。提醒：前序排列的定义：根节点——左子树——右子树的形式遍历这棵树 2.解题思路：在这道题目当中最好了解的就是应用递归的算法，首先咱们须要理解什么是二叉树的前序遍历：依照拜访根节点——左子树——右子树的形式遍历这棵树，而在拜访左子树或者右子树的时候，咱们依照同样的形式遍历，直到遍历完整棵树。因而整个遍历过程人造具备递归的性质，咱们能够间接用递归函数来模仿这一过程。 定义 preorder(root) 示意以后遍历到 root 节点的答案。依照定义，咱们只有首先将 root 节点的值退出答案，而后递归调用 preorder(root.left) 来遍历 root 节点的左子树，最初递归调用 preorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。 3.解题代码class Solution {public: void preorder(TreeNode *root, vector<int> &res) { if (root == nullptr) { return; } res.push_back(root->val); preorder(root->left, res); preorder(root->right, res); } vector<int> preorderTraversal(TreeNode *root) { vector<int> res; preorder(root, res); return res; }};

一、题目粗心请你设计并实现一个满足 LRU (最近起码应用) 缓存 束缚的数据结构。实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字 key 曾经存在，则变更其数据值value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未应用的关键字。函数 get 和 put 必须以 O(1) 的均匀工夫复杂度运行。 示例： 输出 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] ...

问题形容：一个有名的按摩师会收到源源不断的预约申请，每个预约都能够抉择接或不接。在每次预约服务之间要有休息时间，因而她不能承受相邻的预约。给定一个预约申请序列，替按摩师找到最优的预约汇合（总预约工夫最长），返回总的分钟数。 测试输出：输出： [1,2,3,1]输入： 4解释： 抉择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。输出： [2,7,9,3,1]输入： 12解释： 抉择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。输出： [2,1,4,5,3,1,1,3]输入： 12解释： 抉择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。解题思路：设dp[i] 为第 i 天完结后按摩师从第一天到第 i 天承受的预约总时长； 首先咱们来剖析一下原问题，假如第有i天，那么第i天预约的总时长与前一天和大前天都无关，当前一天按摩了，那么第i天的总时长就等于前一天的总时长，也就是dp[i]=dp[i-1]，因为不能相邻两天都进行按摩，要留一点点劳动的工夫，如前一天没有按摩，那么这个时候第i天的总时长就等于大前天的时长加上明天的时长。也就是dp[i]=dp[i-2]+num[i] (在这里num[i]示意输出的预约工夫数组) 因为题目要咱们求出最优解，那么这个时候就能够取上述两种状况当中的最大值，也就是dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]) 解题代码：class Solution {public: int massage(vector<int>& nums) { int n = nums.size(); if(n==0) return 0; if(n==1) return nums[0]; int dp[n]; dp[0] = nums[0]; dp[1] = max(nums[0],nums[1]); for(int i = 2;i<n;i++){ dp[i] = max(dp[i-1],dp[i-2]+nums[i]); } return dp[n-1]; }};

一、题目粗心给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。 如果存在则返回 true，不存在返回 false。 示例 1： 输出：nums = [1,2,3,1], k = 3, t = 0 输入：true 示例 2： 输出：nums = [1,0,1,1], k = 1, t = 2 输入：true 示例 3： 输出：nums = [1,5,9,1,5,9], k = 2, t = 3 输入：false 提醒： 0 <= nums.length <= 2 * 104-231 <= nums[i] <= 231 - 10 <= k <= 1040 <= t <= 231 - 1起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 ...

一、题目粗心给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。 示例 1： 输出：nums = [1,2,3,1], k = 3 输入：true 示例 2： 输出：nums = [1,0,1,1], k = 1 输入：true 示例 3： 输出：nums = [1,2,3,1,2,3], k = 2 输入：false 提醒： 1 <= nums.length <= 105-109 <= nums[i] <= 1090 <= k <= 105起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路原本要刷210.存在反复元素III的，发现上一题就是II，于是就先刷这题了。这道题限度了数组中只许有一组反复的数字，而且其坐标差不能超过k。用map来解决，定义一个map，来记录每个数字和其坐标的映射，而后遍历这个数组，判断map中是否存在以后数的坐标，如果存在判断已存在的坐标对应的数与以后数的差是否超过k。 三、解题办法3.1 Java实现public class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i]) && (i - map.get(nums[i]) <= k)) { return true; } else { map.put(nums[i], i); } } return false; }}四、总结小记2022/10/12 刷了好多题，都遗记了怎么办。。。总结啊

一、题目粗心存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的惟一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。模式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具备以下属性： 不存在自环（graph[u] 不蕴含 u）。不存在平行边（graph[u] 不蕴含反复值）。如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的门路。二分图 定义：如果能将一个图的节点汇合宰割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 汇合，一个来自 B 汇合，就将这个图称为 二分图 。 如果图是二分图，返回 true ；否则，返回 false 。 示例 1： 输出：graph = [[1,2,3],[0,2],[0,1,3],[0,2]] 输入：false 解释：不能将节点宰割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。 示例 2： 输出：graph = [[1,3],[0,2],[1,3],[0,2]] ...

一、题目粗心给定一个二叉树, 找到该树中两个指定节点的最近公共先人。 百度百科中最近公共先人的定义为：“对于有根树 T 的两个节点 p、q，最近公共先人示意为一个节点 x，满足 x 是 p、q 的先人且 x 的深度尽可能大（一个节点也能够是它本人的先人）。” 示例 1： 输出：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输入：3 解释：节点 5 和节点 1 的最近公共先人是节点 3 。 示例 2： 输出：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输入：5 解释：节点 5 和节点 4 的最近公共先人是节点 5 。因为依据定义最近公共先人节点能够为节点自身。 示例 3： 输出：root = [1,2], p = 1, q = 2 输入：1 提醒： 树中节点数目在范畴 [2, 105] 内。-109 <= Node.val <= 109所有 Node.val 互不雷同 。p != qp 和 q 均存在于给定的二叉树中。起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 ...

D141 66. Plus One题目链接66. Plus One 题目剖析以数组模式给定一个整数，并以数组模式返回给它加1后的后果。 例如： Input [9]Output [10]Expected [1,0]Input [1,9,9]Expected [2,0,0]解题思路一开始我的想法是把数组拼接，而后+1，再拆成数组。但疏忽了它给定的整数可能会超过32位/64位的状况。遂放弃。 因为高位在前，低位在后，我采纳的是把数组反转过去的计划。当然，也能够先计算数组长度，再用for循环从后往前也是能够的。 在for循环中，咱们先给以后位数加1，看其是否溢出，即是否须要进位。 若加了1之后小于10，即不须要进位，那么前面的所有位数都不必进位。间接中断循环。否则把以后数字置零并持续循环。这里也能够+1取余来”兼容“不止加1的状况。 这里有两种状况： 在不减少位数的状况下实现进位，也就说+1之后不会扭转位数。进位后位数会减少，也就是说数字全是9，+1之后最初须要再加个数字1。例如，[9], [9,9](99), [9,9,9](999)。本来是n位的，+1之后变成了n+1位。依照下面给定的算法，会呈现最初是0的状况。这个时候须要手动补足数字1。 最初再把数组翻转回去即可。 最终代码<?phpclass Solution { /** * @param Integer[] $digits * @return Integer[] */ function plusOne($digits) { $revArr = array_reverse($digits); foreach($revArr as $index => $num){ if(++$revArr[$index] < 10){ break; } $revArr[$index] = 0; } if($revArr[$index]===0){ $revArr[] = 1; } return array_reverse($revArr); }}若感觉本文章对你有用，欢送用爱发电赞助。

一、题目粗心给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。 示例 1： 输出：root = [1,null,2,3] 输入：[3,2,1] 示例 2： 输出：root = [] 输入：[] 示例 3： 输出：root = [1] 输入：[1] 提醒： 树中节点的数目在范畴 [0, 100] 内-100 <= Node.val <= 100起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路二叉树的问题，用递归就很简略。剖析一下用非递归办法的思路：跟前序、中序、层序一样都要用到栈，后序的程序是左 右 根，所以当一个节点值被取出来时，它的左右子节点要么不存在，要么曾经被拜访过了。先将根结点压入栈，而后定义一个辅助结点 head，while 循环的条件是栈不为空，在循环中，首先将栈顶结点t取出来，如果栈顶结点没有左右子结点，或者其左子结点是 head，或者其右子结点是 head 的状况下。将栈顶结点值退出后果 res 中，并将栈顶元素移出栈，而后将 head 指向栈顶元素；否则的话就看如果右子结点不为空，将其退出栈，再看左子结点不为空的话，就退出栈，留神这里先右后左的程序是因为栈的后入先出的特点，能够使得左子结点先被解决。 三、解题办法3.1 Java实现public class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); traverse(list, root); return list; } public void traverse(List<Integer> list, TreeNode root) { if (root == null) { return; } traverse(list, root.left); traverse(list, root.right); list.add(root.val); }}四、总结小记2022/10/9 上k8s是不是卷呀

一、题目粗心给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。 示例 1： 输出：root = [1,null,2,3] 输入：[1,3,2] 示例 2： 输出：root = [] 输入：[] 示例 3： 输出：root = [1] 输入：[1] 提醒： 树中节点数目在范畴 [0, 100] 内-100 <= Node.val <= 100起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路二叉树的中序遍历程序为左 根 右，能够用递归和非递归来解。递归解法非常间接，对左了节点调用递归函数，根节点拜访值，右子节点再调用递归函数。 非递归有两种办法，一种应用栈：从根节点开始，先将根节点压入栈，而后再将其所有左节点压入栈，而后取出栈顶节点，保留节点值，再将以后指针移到其右子节点上，若存在右子节点，则在下次循环时又可将其所有左子节点压入栈中，这样就保障了拜访程序为左 根 右。 三、解题办法3.1 Java实现 - 递归实现public class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); traverse(list, root); return list; } public void traverse(List<Integer> list, TreeNode root) { if (root == null) { return; } traverse(list, root.left); list.add(root.val); traverse(list, root.right); }}四、总结小记2022/10/8 节后活有点多呀

一、题目粗心给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你结构并返回这颗 二叉树 。 示例 1: 输出：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输入：[3,9,20,null,null,15,7] 示例 2: 输出：inorder = [-1], postorder = [-1] 输入：[-1] 提醒: 1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000inorder 和 postorder 都由 不同 的值组成postorder 中每一个值都在 inorder 中inorder 保障是树的中序遍历postorder 保障是树的后序遍历起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路要求从中序和后序遍历的后果来从新建原二叉树，中序遍历程序是左 根 右，后序遍历程序是左 右 根，对于这种树的重建个别采纳递归来做，因为后序的程序的最初一个必定是根，所以原二叉树的根节点能够晓得，题目中给了一个很要害的条件就是树中没有雷同元素，有了这个条件就能够在中序遍历中也定位出根节点的地位，并依据根节点的地位将中序遍历拆分为春熙路右两局部，别离对其递归调用原函数。 三、解题办法3.1 Java实现public class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1); } TreeNode helper(int[] in, int inL, int inR, int[] post, int postL, int postR) { if (inL > inR || postL > postR) { return null; } TreeNode node = new TreeNode(post[postR]); int i = 0; for (i = inL; i < in.length; i++) { if (in[i] == node.val) { break; } } node.left = helper(in, inL, i - 1, post, postL, postL + i - inL - 1); node.right = helper(in, i + 1, inR, post, postL + i - inL, postR - 1); return node; }}四、总结小记2022/10/7 今天又是新的一天

一、题目粗心给你一个二叉搜寻树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。 差值是一个负数，其数值等于两值之差的绝对值。 示例 1： 输出：root = [4,2,6,1,3] 输入：1 示例 2： 输出：root = [1,0,48,null,null,12,49] 输入：1 提醒： 树中节点的数目范畴是 [2, 104]0 <= Node.val <= 105起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路这道题给咱们一棵二叉搜寻树，让咱们求任意个节点值之间的最小相对差。因为BST的左<根<右的性质可知，如果依照中序遍历会失去一个有序数组，那么最小相对差必定在置信的两个节点值之之间产生。所以咱们的做法就是对BST进行中序遍历，而后以后节点值和之前节点值求相对差并更新后果res。须要留神的是在解决第一个节点值时，没有前节点所以不能求相对差。咱们用变量pre来示意前节点，将其初始化为-1（节点值不为正数），咱们就晓得pre是否存在。 三、解题办法3.1 Java实现public class Solution { public int getMinimumDifference(TreeNode root) { int[] res = {Integer.MAX_VALUE}; int[] pre = {-1}; inorder(root, pre, res); return res[0]; } void inorder(TreeNode root, int[] pre, int[] res) { if (root == null) { return; } inorder(root.left, pre, res); if (pre[0] != -1) { res[0] = Math.min(res[0], root.val - pre[0]); } pre[0] = root.val; inorder(root.right, pre, res); }}四、总结小记2022/10/5 有时候生存不肯定比工作轻松

LeetCode网站 不必多说了，刷题必备 牛客网站 不仅能够刷题，还能够看面经 Codewars网站 有一些和业务很像的题，有一部分题的背景也很乏味，英语 Hackerrank网站 外企用的多，能够通过链接分享的模式来面试测试，想相熟环境的话能够试试，英语 Codility网站 外企用的多，能够通过链接分享的模式来面试测试，想相熟环境的话能够试试，英语 Project Euler网站 英语，数学类的题很多 LintCode网站 国内的LeetCode、也有不同与LeetCode的问题 BEF网站 前端特化网站，还有CSS、React.js等等问题，不过目前还没有Vue.js AtCoder网站 日本竞技编程网站，有英文 Timus Online Judge（ACM）网站 毛子做的ACM刷题网站

一、题目粗心给定一个二叉搜寻树, 找到该树中两个指定节点的最近公共先人。 百度百科中最近公共先人的定义为：“对于有根树 T 的两个结点 p、q，最近公共先人示意为一个结点 x，满足 x 是 p、q 的先人且 x 的深度尽可能大（一个节点也能够是它本人的先人）。” 例如，给定如下二叉搜寻树: root = [6,2,8,0,4,7,9,null,null,3,5] 示例 1: 输出: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输入: 6 解释: 节点 2 和节点 8 的最近公共先人是 6。 示例 2: 输出: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输入: 2 解释: 节点 2 和节点 4 的最近公共先人是 2, 因为依据定义最近公共先人节点能够为节点自身。 阐明: 所有节点的值都是惟一的。p、q 为不同节点且均存在于给定的二叉搜寻树中。起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路求二叉树的最小独特父节点，能够用递归来求解，同志二叉搜寻树的特点是左<根<右，所以根节点的值始终都是两头值，大于左子树的所有节点值，小于右子树的所有节点值，咱们能够做如下判断，如果根节点的值大于p和q之间的较大值，阐明q和q都在左子树中，那么此时咱们就进入根节点的左子节点持续uxjv，如果根节点小于p和q之间的较小值，阐明p和q都在右子树中，那么此时咱们就进入根节点的右子节点持续递归，如果都不是，则阐明以后根节点就是是近朱者赤;近墨者黑独特父节点，间接返回即可。 三、解题办法3.1 Java实现public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null) { return root; } if (root.val > Math.max(p.val, q.val)) { return lowestCommonAncestor(root.left, p, q); } else if (root.val < Math.min(p.val, q.val)) { return lowestCommonAncestor(root.right, q, q); } else { return root; } }}四、总结小记2202/10/4 假期疫情瞬息万变

一、题目粗心给出二叉 搜寻 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 揭示一下，二叉搜寻树满足下列约束条件： 节点的左子树仅蕴含键 小于 节点键的节点。节点的右子树仅蕴含键 大于 节点键的节点。左右子树也必须是二叉搜寻树。留神：本题和 1038雷同 示例 1： 输出：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输入：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8] 示例 2： 输出：root = [0,null,1] 输入：[1,null,1] 示例 3： 输出：root = [1,0,2] 输入：[3,3,2] 示例 4： 输出：root = [3,2,4,1] 输入：[7,9,4,10] 提醒： 树中的节点数介于 0 和 104 之间。每个节点的值介于 -104 和 104 之间。树中的所有值 互不雷同 。给定的树为二叉搜寻树。起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路这道题让咱们将二叉搜寻树转为累加树，通过题目汇总的例子能够晓得，是把每个节点值加上所有比它大的节点值总和作为新的节点值。仔细观察题目中的例子能够发现，2变成20，而20是所有节点之各，因为2是最小节点值，要加上其余所有节点值，所以必定就是所有节点值之和。5变成18，是通过20减去2得来的，而13还是13，则由20减7得来的，而7是2和5之和。能够将中序遍历左根右的程序逆过去，变成右根左的程序，这样能够反向计算累加和sum，同时更新节点值。 三、解题办法3.1 Java实现四、总结小记2022/10/1 又是忙䘵的一天

一、题目粗心给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最右边 节点的值。 假如二叉树中至多有一个节点。 示例 1: 输出: root = [2,1,3] 输入: 1 示例 2: 输出: [1,2,3,4,null,5,6,null,null,7] 输入: 7 提醒: 二叉树的节点个数的范畴是 [1,104]-231 <= Node.val <= 231 - 1起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路求二叉树的最左下树节点的值，也就是最初一行左数第一个值，能够用先序遍从来做，保护一个最大尝试和该尝试的节点值，因为先序遍历遍历的程序是根左右，所以每一行最右边的节点必定最先先遍历到，因为是新一行，那么以后尝试必定比之前的最大深度大，所以能够更新最大深度为以后深度，节点值res为以后节点值，这样在遍历到该行其余节点时就不会更新res了 三、解题办法3.1 Java实现public class Solution { public int findBottomLeftValue(TreeNode root) { int maxDepth = 1; int[] res = new int[]{root.val}; helper(root, 1, maxDepth, res); return res[0]; } void helper(TreeNode node, int depth, int maxDpeth, int[] res) { if (node == null) { return; } if (depth > maxDpeth) { maxDpeth = depth; res[0] = node.val; } helper(node.left, depth + 1, maxDpeth, res); helper(node.right, depth + 1, maxDpeth, res); }}四、总结小记2022/9/30 明天有点焦急

一、题目粗心给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。 示例 1： 输出：root = [4,2,7,1,3,6,9] 输入：[4,7,2,9,6,3,1] 示例 2： 输出：root = [2,1,3] 输入：[2,3,1] 示例 3： 输出：root = [] 输入：[] 提醒： 树中节点数目范畴在 [0, 100] 内-100 <= Node.val <= 100起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路翻转二叉树是树的基本操作之一，能够应用递归和非递归两种办法。递归办法：替换以后左右节点，并间接调用递归即可。非递归办法：跟二叉树的层序遍历一样，须要用queue画辅助，先把根节点排入队列中，而后从队列中取出来，替换其左右节点，如果存在则别离将左右节点再排入队列中，以此类推直到队列中没有节点了 三、解题办法3.1 Java实现-递归public class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return root; } TreeNode tmp = root.left; root.left = invertTree(root.right); root.right = invertTree(tmp); return root; }}3.2 Java实现-非递归public class Solution2 { public TreeNode invertTree(TreeNode root) { if (root == null) { return root; } Deque<TreeNode> q = new ArrayDeque<>(); q.push(root); while (!q.isEmpty()) { TreeNode node = q.pop(); TreeNode tmp = node.left; node.left = node.right; node.right = tmp; if (node.left != null) { q.push(node.left); } if (node.right != null) { q.push(node.right); } } return root; }}四、总结小记2022/9/29 在你成为领导者之前，胜利的全副就是自我的成长；当你成了领导者，胜利的全副就变成帮忙别人成长。---通用电气CEO 杰克 · 韦尔奇《商业的实质》

题目给定一个字符串 s ，请你找出其中不含有反复字符的 最长子串 的长度。示例 1: 输出: s = "abcabcbb"输入: 3 解释: 因为无反复字符的最长子串是 "abc"，所以其长度为 3。示例 2: 输出: s = "bbbbb"输入: 1解释: 因为无反复字符的最长子串是 "b"，所以其长度为 1。示例 3: 输出: s = "pwwkew"输入: 3解释: 因为无反复字符的最长子串是 "wke"，所以其长度为 3。请留神，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 提醒： 0 <= s.length <= 5 * 104s 由英文字母、数字、符号和空格组成链接：3. 无反复字符的最长子串 思路通过头尾指针来标出以后"无反复字符"一旦呈现反复，则挪动头指针。通过"尾指针地位-头指针地位"失去"无反复字符"长度。如下图 代码public int lengthOfLongestSubstring(String s) { if(s == null || s.length() == 0) { return 0; } int n = s.length(); int ret = 0; // 反复字符串呈现的地位 int point; // 以后"无反复字符"的起始地位 int begin = 0; for (int i = 0; i < n; ++i) { // 获取反复字符呈现的地位 point = s.indexOf(s.charAt(i), begin); // 如果大于1，则阐明以后"无反复字符"里没有反复 point = point >= i ? -1 : point; if (point >= 0) { ret = Math.max(ret, i - begin); // "无反复字符"的其实地位往右挪动一位 begin = point + 1; } } return Math.max(ret, n - begin);}运行后果： ...

一、题目粗心给你两棵二叉树 root 和 subRoot 。测验 root 中是否蕴含和 subRoot 具备雷同构造和节点值的子树。如果存在，返回 true ；否则，返回 false 。 二叉树 tree 的一棵子树包含 tree 的某个节点和这个节点的所有后辈节点。tree 也能够看做它本身的一棵子树。 示例 1： 输出：root = [3,4,5,1,2], subRoot = [4,1,2] 输入：true 示例 2： 输出：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] 输入：false 提醒： root 树上的节点数量范畴是 [1, 2000]subRoot 树上的节点数量范畴是 [1, 1000]-104 <= root.val <= 104-104 <= subRoot.val <= 104起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路思路1:子树必须是从叶节点开始的，两头局部的不能算是子树，转换一下思路，从root的某个节点开始，就跟subRoot的所有构造都一样，那么问题就转换成了判断两棵树是否雷同 思路2:对root和subRoot两棵树别离进行序列化，各生成一个字符串，如果subRoot的字符串是root的子串的话，阐明subRoot是s的子树，须要留神的是，在序列化的时候要非凡解决一下，就是在每个节点后面都加上一个字符，比方,,那么12序列化后就是,12,#2序列化后就是,2,# 三、解题办法3.1 Java实现public class Solution { public boolean isSubtree(TreeNode root, TreeNode subRoot) { // root至多有1个节点 // subRoot至多有1个节点 if (root == null) { return false; } boolean isSame = isSameTreeNode(root, subRoot); if (isSame) { return true; } return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot); } boolean isSameTreeNode(TreeNode node1, TreeNode node2) { if (node1 == null && node2 == null) { return true; } if (node1 == null && node2 != null) { return false; } if (node1 != null && node2 == null) { return false; } if (node1.val != node2.val) { return false; } return isSameTreeNode(node1.left, node2.left) && isSameTreeNode(node1.right, node2.right); }}四、总结小记2022/9/28 尽管很简略，然而看到通过的那一刻还是很开心的

一、题目粗心给你两棵二叉树： root1 和 root2 。 设想一下，当你将其中一棵笼罩到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你须要将这两棵树合并成一棵新二叉树。合并的规定是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将间接作为新二叉树的节点。 返回合并后的二叉树。 留神: 合并过程必须从两个树的根节点开始。 示例 1： 输出：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7] 输入：[3,4,5,5,4,null,7] 示例 2： 输出：root1 = [1], root2 = [1,2] 输入：[2,2] 提醒： 两棵树中的节点数目在范畴 [0, 2000] 内-104 <= Node.val <= 104 起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路间接用递归调用给定函数，先判断如果root1为空返回root2，如果root2为空返回root1，都存在的状况下建设新节点node，而后对root1和root2的左子节点调用递归并赋给node的左子节点，再对root1和root2的右子节点调用递归并赋给node的右子节点，返回node即可。 三、解题办法3.1 Java实现class Solution { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 == null) { return root2; } if (root2 == null) { return root1; } TreeNode node = new TreeNode(root1.val + root2.val); node.left = mergeTrees(root1.left, root2.left); node.right = mergeTrees(root1.right, root2.right); return node; }}四、总结小记2022/9/27 愿每个人都能：出奔半生，归来仍是少年

一、题目粗心Trie（发音相似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的利用情景，例如主动补完和拼写查看。 请你实现 Trie 类： Trie() 初始化前缀树对象。void insert(String word) 向前缀树中插入字符串 word 。boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前曾经插入）；否则，返回 false 。boolean startsWith(String prefix) 如果之前曾经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。示例： 输出["Trie", "insert", "search", "search", "startsWith", "insert", "search"][[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]输入[null, null, true, false, true, null, true]解释Trie trie = new Trie();trie.insert("apple");trie.search("apple"); // 返回 Truetrie.search("app"); // 返回 Falsetrie.startsWith("app"); // 返回 Truetrie.insert("app");trie.search("app"); // 返回 True提醒： 1 <= word.length, prefix.length <= 2000word 和 prefix 仅由小写英文字母组成insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 ...

最小滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最小长度。while j < len(nums): 判断[i, j]是否满足条件 while 满足条件： 不断更新后果(留神在while内更新！) i += 1 （最大水平的压缩i，使得滑窗尽可能的小） j += 1//209. 长度最小的子数组 int minSubArrayLen(int target, vector<int>& nums) { int left = 0, right = 0; int res = INT_MAX; int sum = 0; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; // 留神这里应用while，每次更新 i（起始地位），并一直比拟子序列是否符合条件 while (sum >= target) { int subLength = (i - left + 1); // 取子序列的长度 res = res < subLength ? res : subLength; if (res == 1 && sum == target) { return res; } sum -= nums[left++]; // 这里体现出滑动窗口的精华之处，一直变更i（子序列的起始地位） } } // 如果result没有被赋值的话，就返回0，阐明没有符合条件的子序列 return res == INT32_MAX ? 0 : res; }最大滑窗模板：给定数组 nums，定义滑窗的左右边界 i, j，求满足某个条件的滑窗的最大长度。while j < len(nums): 判断[i, j]是否满足条件 while 不满足条件： i += 1 （最激进的压缩i，一旦满足条件了就退出压缩i的过程，使得滑窗尽可能的大） 不断更新后果（留神在while外更新！） j += 1//904. 水果成篮 int totalFruit(vector<int>& fruits) { //滑动窗口法 int left = 0; //滑动窗口左边界 int sub_len = 0; //子序列长度 int fruit_counter = 0; //篮子中的水果品种数 int len = fruits.size(); unordered_map<int, int> basket; //创立篮子 for (int j = 0; j < len; j++) { if (basket[fruits[j]] == 0) //以后水果数量在篮子中数量为零 { fruit_counter++; } basket[fruits[j]]++; while (fruit_counter > 2)//如果篮子中的水果数目超过两种，则须要挪动左边界 { basket[fruits[left]]--; //若对应水果key的value变为0，阐明篮子里曾经没有这种水果了，水果品种要对应变动（留神basket[fruits[left]] == 0即右边的水果数量为0） if (basket[fruits[left]] == 0) { fruit_counter--; } left++; } sub_len = max(sub_len, j - left + 1); } return sub_len; }最大滑窗是在迭代右移右边界的过程中更新后果，而最小滑窗是在迭代右移左边界的过程中更新后果 ...

一、题目粗心给你二叉搜寻树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜寻树，使得所有节点的值在[low, high]中。修剪树 不应该 扭转保留在树中的元素的绝对构造 (即，如果没有被移除，原有的父代子代关系都该当保留)。 能够证实，存在 惟一的答案 。 所以后果该当返回修剪好的二叉搜寻树的新的根节点。留神，根节点可能会依据给定的边界产生扭转。 示例 1： 输出：root = [1,0,2], low = 1, high = 2 输入：[1,null,2] 示例 2： 输出：root = [3,0,4,null,2,null,null,1], low = 1, high = 3 输入：[3,2,null,1] 提醒： 树中节点数在范畴 [1, 104] 内0 <= Node.val <= 104树中每个节点的值都是 惟一 的题目数据保障输出是一棵无效的二叉搜寻树0 <= low <= high <= 104起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路什么是二叉查找树？ 二叉查找树（Binary Search Tree，BST）是一种非凡的二叉树：对于每个父节点，其左子树中所有节点的值小于等于父节点的值，其右子树中所有节点的值大于等于父节点的值。 利用二叉查找树的大小关系，咱们能够很容易地利用递归进行树的解决。 三、解题办法3.1 Java实现class Solution { public TreeNode trimBST(TreeNode root, int low, int high) { if (root == null) { return root; } if (root.val > high) { return trimBST(root.left, low, high); } if (root.val < low) { return trimBST(root.right, low, high); } root.left = trimBST(root.left, low, high); root.right = trimBST(root.right, low, high); return root; }}四、总结小记2022/9/24 孩子静悄悄，必然在做妖；老人也是

解题思路：依照图示思路模仿过程进行 螺旋矩阵 vector<vector<int>> generateMatrix(int n) {// 创立二维矩阵vector<vector<int>> matrix(n);for (int i = 0; i < matrix.size(); i++) matrix[i].resize(n);// 上下左右int u = 0;int d = n - 1;int l = 0;int r = n - 1;int num = 1;while (true) { // 上 for (int i = l; i <= r; i++) matrix[u][i] = num++; if (u++ >= d) break; // 右 for (int i = u; i <= d; i++) matrix[i][r] = num++; if (r-- <= l) break; // 下 for (int i = r; i >= l; i--) matrix[d][i] = num++; if (d-- <= u) break; // 左 for (int i = d; i >= u; i--) matrix[i][l] = num++; if (l++ >= r) break;}return matrix;}59.螺旋矩阵II ...

一、题目粗心给你二叉树的根节点 root ，返回它节点值的 前序 遍历。 示例 1： 输出：root = [1,null,2,3] 输入：[1,2,3] 示例 2： 输出：root = [] 输入：[] 示例 3： 输出：root = [1] 输入：[1] 示例 4： 输出：root = [1,2] 输入：[1,2] 示例 5： 输出：root = [1,null,2] 输入：[1,2] 提醒： 树中节点数目在范畴 [0, 100] 内-100 <= Node.val <= 100进阶：递归算法很简略，你能够通过迭代算法实现吗？ 起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路二叉树的遍历，常见的有先序遍历、中序遍历、后序遍历和层序遍历，它们用uxjv实现起来都非常简单； 思考应用非递归来实现，用到时stack来辅助转自，因为先序遍历的程序为 根左右，算法为： 1、把根节点push到栈中 2、循环查看栈是否为空，若不空，取出栈顶元素并保留其值，而后看其右节点是否存在，若存在则push到栈中，再看其左节点，若存在，则push到栈中 三、解题办法3.1 Java实现-递归class Solution { public List<Integer> preorderTraversal(TreeNode root) { // 先序遍历：中左右 List<Integer> ans = new ArrayList<>(); preorder(root, ans); return ans; } void preorder(TreeNode node, List<Integer> ans) { if (node == null) { return; } ans.add(node.val); preorder(node.left, ans); preorder(node.right, ans); }}3.2 Java实现-迭代public class Solution2 { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); if (root == null) { return ans; } // 应用栈来辅助实现，Java中用双端队列来代替栈 Deque<TreeNode> stack = new ArrayDeque<>(); stack.addFirst(root); while (!stack.isEmpty()) { TreeNode tmp = stack.pop(); ans.add(tmp.val); if (tmp.right != null) { stack.addFirst(tmp.right); } if (tmp.left != null) { stack.addFirst(tmp.left); } } return ans; }}四、总结小记2022/9/23 遇到“上传下达”的状况，激情顿无，毫无意义

一、题目粗心给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请结构二叉树并返回其根节点。 示例 1: 输出: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]输入: [3,9,20,null,null,15,7]示例 2: 输出: preorder = [-1], inorder = [-1]输入: [-1]提醒: 1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder 和 inorder 均 无反复 元素inorder 均呈现在 preorderpreorder 保障 为二叉树的前序遍历序列inorder 保障 为二叉树的中序遍历序列起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路本题要求用先序和中序遍从来建设二叉树，因为先序的程序的第一个必定是根，所以原二叉树的根节点能够晓得，题目中给了一个很要害的条件就是树中没有雷同元素，有了这个条件就能够在中序遍历中也定位出根邛的地位，并以根节点的地位将中序遍历拆分为左右两个局部，别离对其递归调用原函数。 三、解题办法3.1 Java实现class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length == 0) { return null; } Map<Integer, Integer> hash = new HashMap<>(); for (int i = 0; i < preorder.length; i++) { hash.put(inorder[i], i); } return buildTreeHelper(hash, preorder, 0, preorder.length - 1, 0); } TreeNode buildTreeHelper(Map<Integer, Integer> hash, int[] preorder, int s0, int e0, int s1) { if (s0 > e0) { return null; } int mid = preorder[s1]; int index = hash.get(mid); int leftLen = index - s0 - 1; TreeNode node = new TreeNode(mid); node.left = buildTreeHelper(hash, preorder, s0, index - 1, s1 + 1); node.right = buildTreeHelper(hash, preorder, index + 1, e0, s1 + 2 + leftLen); return node; }}四、总结小记2022/9/22 到了上有老下有小的中年人，有些责任必须去承当，有些问题必须去面对

一、题目粗心给定一个非空二叉树的根节点 root , 以数组的模式返回每一层节点的平均值。与理论答案相差 10-5 以内的答案能够被承受。 示例 1： 输出：root = [3,9,20,null,null,15,7]输入：[3.00000,14.50000,11.00000]解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。因而返回 [3, 14.5, 11] 。示例 2: 输出：root = [3,9,20,15,7]输入：[3.00000,14.50000,11.00000]提醒： 树中节点数量在 [1, 104] 范畴内-231 <= Node.val <= 231 - 1起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路求一个二叉树每层的平均值，利用广度优先搜寻，咱们能够很不便地求取每层的平均值。间接应用queue，间接将每层的值累计加起来除以该层的节点个数，存入后果ans中即可。 三、解题办法3.1 Java实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<Double> averageOfLevels(TreeNode root) { List<Double> ans = new ArrayList<>(); if (root == null) { return ans; } Queue<TreeNode> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()) { int count = q.size(); double sum = 0; for (int i = 0; i < count; i++) { TreeNode node = q.peek(); q.poll(); sum += node.val; if (node.left != null) { q.add(node.left); } if (node.right != null) { q.add(node.right); } } ans.add(sum / count); } return ans; }}四、总结小记2022/9/15 notion是pld的榜样，什么是PLG，product-led groupth。

一、题目粗心给出二叉树的根节点 root，树上每个节点都有一个不同的值。 如果节点值在 to_delete 中呈现，咱们就把该节点从树上删去，最初失去一个森林（一些不相交的树形成的汇合）。 返回森林中的每棵树。你能够按任意程序组织答案。 示例 1： 输出：root = [1,2,3,4,5,6,7], to_delete = [3,5]输入：[[1,2,null,4],[6],[7]]示例 2： 输出：root = [1,2,4,null,3], to_delete = [3]输入：[[1,2,4]]提醒： 树中的节点数最大为 1000。每个节点都有一个介于 1 到 1000 之间的值，且各不相同。to_delete.length <= 1000to_delete 蕴含一些从 1 到 1000、各不相同的值。起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路给一棵二叉树，每个节点值均不同，删除一些节点，因为删除非叶子节点会使原来的二叉树断开，从而会造成从棵二叉树，造成一片森林，返回森林中所有二叉树的根节点。 二叉树的题首先想到用递归，递归办法传递4个参数，以后节点；是否是根节点（如果是根节点、且存在左右子树才会造成新树）；再传递一个hashset用来存储要删除的节点，达到常数据级搜寻；还有一个保留后果的list。 在递归函数中，如果节点为空返回null，定义亦是deleted来保留以后节点值是否在hashset中，若是根节点且不须要被删除，则将节点退出返回后果list中。而后将左子节点赋值为对左子节点调用递归函数的返回值，右子节点赋值为对右子节点调用递归函数的返回值。最初判断以后节点是否被删除了，如果是的话返回空，否则返回以后指针。这样的话每棵树的根节点都在递归过程中存入后果list中了。 三、解题办法3.1 Java实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public List<TreeNode> delNodes(TreeNode root, int[] to_delete) { List<TreeNode> ans = new ArrayList<>(); Set<Integer> set = new HashSet<>(); for (int tmp : to_delete) { set.add(tmp); } helper(root, true, set, ans); return ans; } TreeNode helper(TreeNode node, boolean isRoot, Set<Integer> set, List<TreeNode> ans) { if (node == null) { return null; } boolean deleted = set.contains(node.val); if (isRoot && !deleted) { ans.add(node); } node.left = helper(node.left, deleted, set, ans); node.right = helper(node.right, deleted, set, ans); return deleted ? null : node; }}四、总结小记2022/9/14 工作接踵而至

一、题目粗心给定一个二叉树，判断它是否是高度均衡的二叉树。 本题中，一棵高度均衡二叉树定义为： 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。 示例 1： 输出：root = [3,9,20,null,null,15,7]输入：true示例 2： 输出：root = [1,2,2,3,3,null,null,4,4]输入：false示例 3： 输出：root = []输入：true提醒： 树中的节点数在范畴 [0, 5000] 内-104 <= Node.val <= 104起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路思路：定义一个求各个节点深度的函数，而后中每个节点的两个子树来比拟深度差，针对每个点都会被计算深度时拜访一次进行优化，如果发现子树不均衡，则不计算具体的深度，而是间接返回-1，优化后的谅赤：对于每一个节点，通过checkDepth办法递归取得左右子树的深度，如果子树是均衡的，则返回实在的深度，若不均衡，间接返回-1。 三、解题办法3.1 Java实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public boolean isBalanced(TreeNode root) { return checkDepth(root) != -1; } int checkDepth(TreeNode root) { if (root == null) { return 0; } int left = checkDepth(root.left); if (left == -1) { return -1; } int right = checkDepth(root.right); if (right == -1) { return -1; } if (Math.abs(left - right) > 1) { return -1; } return Math.max(left, right) + 1; }}四、总结小记2022/9/13 当中层切记不要只是上传下达

明天的每日一题 Best Time to Buy and Sell Stock IVYou are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k. Find the maximum profit you can achieve. You may complete at most k transactions. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). Input: k = 2, prices = [2,4,1]Output: 2Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.状态转移咱们保护两个数组 buy 和 sell 别离记录以后持有和卖出时的收益buy[i] 代表在第i天买入后手里的钱sell[i] 代表在第i天卖出后手里的钱因为有k手交易的限度，将动静布局数组转化为矩阵,第二个维度代表交易的次数，这里交易的定义是残缺的一次买入后又卖出记为一次，由此可得状态转移方程 ...

一、题目粗心给定一棵二叉树，你须要计算它的直径长度。一棵二叉树的直径长度是任意两个结点门路长度中的最大值。这条门路可能穿过也可能不穿过根结点。 示例 :给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是门路 [4,2,1,3] 或者 [5,2,1,3]。 留神：两结点之间的门路长度是以它们之间边的数目示意。 起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路求二叉树的直径，其实就是求根节点左右两个子树的深度之和。咱们只有对每个节点求出其左右子树深度之和，这个值作为一个候选值。 三、解题办法3.1 Java实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { /** * 用来优化递归 */ Map<TreeNode, Integer> map = new HashMap<>(); public int diameterOfBinaryTree(TreeNode root) { int[] diameter = new int[1]; maxDepth(root, diameter); return diameter[0]; } /** * 求二叉树的最大深度，而二叉树的直径为 左二叉树深度 + 右二叉树深度 */ int maxDepth(TreeNode root, int[] diameter) { if (root == null) { return 0; } if (map.containsKey(root)) { return map.get(root); } int l = maxDepth(root.left, diameter); int r = maxDepth(root.right, diameter); diameter[0] = Math.max(l + r, diameter[0]); return Math.max(l, r) + 1; }}四、总结小记2022/9/9 马上中秋节啦

一、题目粗心给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 门路 的数目。 门路 不须要从根节点开始，也不须要在叶子节点完结，然而门路方向必须是向下的（只能从父节点到子节点）。 示例 1： 输出：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8输入：3解释：和等于 8 的门路有 3 条，如图所示。示例 2： 输出：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22输入：3提醒: 二叉树的节点个数的范畴是 [0,1000]-109 <= Node.val <= 109-1000 <= targetSum <= 1000起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路双层递归实现，留神分状况思考：1、如果选取该节点退出门路，则之后必须持续退出间断节点，或进行退出节点；2、如果不选取该节点退出门路，则对其左右节点进行重新考虑。因而一个不便的办法是咱们创立一个辅函数，专门用来计算间断退出节点的门路。 三、解题办法3.1 Java实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public int pathSum(TreeNode root, int targetSum) { if (root == null) { return 0; } return pathSumStartWithRoot(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum); } /** * 留神，这里入参类型为long，否则通不过上面这个用例 * 这里root.val太大，递归调用多了targetNum-root.val就会溢出整数型的最小值，把参数换成long即可 * [1000000000,1000000000,null,294967296,null,1000000000,null,1000000000,null,1000000000] * 0 */ int pathSumStartWithRoot(TreeNode root, long targetSum) { if (root == null) { return 0; } int count = root.val == targetSum ? 1 : 0; count += pathSumStartWithRoot(root.left, targetSum - root.val); count += pathSumStartWithRoot(root.right, targetSum - root.val); return count; }}四、总结小记2022/9/8 求人不如求己

一、题目粗心给你一个二叉树的根节点 root ， 查看它是否轴对称。 示例 1： 输出：root = [1,2,2,3,4,4,3]输入：true示例 2： 输出：root = [1,2,2,null,3,null,3]输入：false提醒： 树中节点数目在范畴 [1, 1000] 内-100 <= Node.val <= 100进阶：你能够使用递归和迭代两种办法解决这个问题吗？ 起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路判断一个树是否对称等价于判断左右子树是否对称。分四步:(1)如果两个子树都为空指针，则它们相等或对称(2) 如果两个子树只有一个为空指针，则它们不相等或不对称(3)如果两个子树根节点的值不相等， 则它们不相等或不对称(4)依据相等或对称要求，进行递归解决。 三、解题办法3.1 Java实现public class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } return isMirror(root.left, root.right); } public boolean isMirror(TreeNode left, TreeNode right) { // (1)如果两个子树都为空指针，则它们相等或对称 if (left == null && right == null) { return true; } // (2) 如果两个子树只有一个为空指针，则它们不相等或不对称 if (left == null && right != null) { return false; } if (left != null && right == null) { return false; } // (3)如果两个子树根节点的值不相等， 则它们不相等或不对称 if (left != null && right != null && left.val != right.val) { return false; } // (4)依据相等或对称要求，进行递归解决。 return isMirror(left.left, right.right) && isMirror(left.right, right.left); }}四、总结小记2022/9/7 做治理给待遇肯定要由远及近

一、题目粗心给你二叉树的根结点 root ，请你将它开展为一个单链表： 开展后的单链表应该同样应用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。开展后的单链表应该与二叉树 先序遍历 程序雷同。 示例 1： 输出：root = [1,2,5,3,4,null,6]输入：[1,null,2,null,3,null,4,null,5,null,6]示例 2： 输出：root = []输入：[]示例 3： 输出：root = [0]输入：[0]提醒： 树中结点数在范畴 [0, 2000] 内-100 <= Node.val <= 100进阶：你能够应用原地算法（O(1) 额定空间）开展这棵树吗？ 起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路思路：非迭代版实现，从根节点开始登程，先检测其左子节点是否存在，如存在则将根节点和其右节点断开，将左子节点及其前面所有构造一起连贯到右子节点的地位，把原右子节点连到原左子节点为最初面的右子节点之后。 三、解题办法3.1 Java实现/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public void flatten(TreeNode root) { // 上面再来看非迭代版本的实现，这个办法是从根节点开始登程，先检测其左子结点是否存在，如存在则将根节点和其右子节点断开， // 将左子结点及其前面所有构造一起连到原右子节点的地位，把原右子节点连到元左子结点最初面的右子节点之后。代码如下： TreeNode cur = root; while (cur != null) { if (cur.left != null) { TreeNode p = cur.left; while (p.right != null) { p = p.right; } p.right = cur.right; cur.right = cur.left; cur.left = null; } cur = cur.right; } }}四、总结小记2022/9/6 按起了葫芦起了瓢；都不违心写文档，全凭集体教训来推动

一、题目粗心给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长门路上的节点数。 阐明: 叶子节点是指没有子节点的节点。 示例：给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7返回它的最大深度 3 。 起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路思路：求二叉树的最大深度问题用深度优先搜寻 Depth First Search，递归的完满利用。 思路二：也能够用层序遍历二叉树，而后计数总层数，即为二叉树的最大深度，须要留神的是while循环中的for循环的写法，肯定要将q.size()放在初始化里，而不能放在普快进行的条件中，因为q的大小是随时变动的，所以放在进行条件中会出错。 三、解题办法3.1 Java实现-递归/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }}3.2 Java实现-层序遍历public class Solution2 { public int maxDepth(TreeNode root) { if (root == null) { return 0; } int ans = 0; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { ans++; for (int i = q.size(); i > 0; i--) { TreeNode t = q.poll(); if (t.left != null) { q.offer(t.left); } if (t.right != null) { q.offer(t.right); } } } return ans; }}四、总结小记2022/9/5 做开发没有需要设计那就是无穷劫难的开始

一、题目粗心给定一个已排序的链表的头 head ， 删除所有反复的元素，使每个元素只呈现一次 。返回 已排序的链表 。 示例 1： 输出：head = [1,1,2]输入：[1,2]示例 2： 输出：head = [1,1,2,3,3]输入：[1,2,3]提醒： 链表中节点数目在范畴 [0, 300] 内-100 <= Node.val <= 100题目数据保障链表曾经按升序 排列起源：力扣（LeetCode）链接：https://leetcode.cn/problems/...著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。 二、解题思路思路：如果下一个元素和以后元素的值相等，这个元素的下个元素就等于下个元素的下个元素，持续循环。 三、解题办法3.1 Java实现class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode cur = head; while (cur != null && cur.next != null) { if (cur.val == cur.next.val) { cur.next = cur.next.next; } else { cur = cur.next; } } return head; }}四、总结小记2022/9/4 据理解，5公里内通勤是“幸福通勤”的最大阈值