Leetcode

/* 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。*/ 前置常识： lc0876 链表的两头节点 (用快慢指针找到链表的两头节点) Lc0234这题的的思路是1、用快慢指针找到原链表后半局部(找到后半段链表的头指针)。2、将前半段链表反转。3、比拟反转后的前半段链表和后半段链表。 其中1、2 两步骤能够同时进行。 先看代码 这题有两个须要留神的点1、奇数长度的链表和偶数长度的链表解决形式不同。2、反转链表的操作自身。 上面看图解。奇数长度的链表 slow须要往前走一步 而偶数长度的链表，快慢指针的while循环之后slow指针曾经达到了预期的地位 再看反转链表的过程，这是刚接触链表的选手比拟难了解的中央 重点在while循环中红框的代码局部 完结。 同步更新到本人的语雀https://www.yuque.com/dirackeeko/tfpe21/ny24nl7sleaocz5b

Easy题，一开始的思路是间接算斜率，然而除法应用了浮点数来计算斜率，这可能导致精度问题。只管这种状况在大多数理论利用中并不常见，但如果输出的坐标值十分大或十分小，那么就可能遇到精度问题。此外，因为浮点数的不精确性，即便两个斜率实际上是相等的，比拟也可能会返回false。另外这种办法还不能很好的解决水平线的问题，算进去inf,-inf须要做额定的判断 impl Solution { pub fn check_straight_line(coordinates: Vec<Vec<i32>>) -> bool { if coordinates.len() <= 2 { return true } let gradient = (coordinates[1][1] as f32 - coordinates[0][1] as f32) / (coordinates[1][0] as f32 - coordinates[0][0] as f32); for coordinate in coordinates.iter().skip(2){ let x = coordinate[0] as f32; let y = coordinate[1] as f32; println!("{}, {}", x, y); println!("gradient: {}", gradient); println!("gradient here: {}", (y - coordinates[0][1] as f32) / (x - coordinates[0][0] as f32)); if (y - coordinates[0][1] as f32) / (x - coordinates[0][0] as f32) != gradient { return false } } true }}随后想到用乘法来防止找个问题。穿插乘法的斜率的核心思想基于这样一个事实：在二维立体上，两个点之间的斜率是一个常数。具体来说，对于点 (x1, y1) 和 (x2, y2)，斜率 m 能够示意为： ...

华为OD对立考试A卷+B卷 新题库阐明2023年5月份，华为官网曾经将的 2022/0223Q(1/2/3/4)对立批改为OD对立考试（A卷）和OD对立考试（B卷）。你收到的链接下面会标注A卷还是B卷。请留神：依据反馈，目前大部分收到的都是B卷。然而仍有概率抽到A卷。A卷对应2023的新题库（2022Q4 20223Q1） B卷对应20022局部考题以及新出的题目 专栏：2023华为OD机试(A卷+B卷)（C++JavaJSPy）专栏：2023华为OD机试(A卷)（C++ Java JS Py）专栏：2023华为OD机试(B卷)（C++ Java JS Py） 题目形容停车场有一横排车位，0代表没有停车，1代表有车。至多停了一辆车在车位上，也至多有一个空位没有停车。 为了防剐蹭，需为停车人找到一个车位，使得距停车人的车最近的车辆的间隔是最大的，返回此时的最大间隔。 输出形容一个用半角逗号宰割的停车标识字符串，停车标识为0或1，0为空位，1为已停车。停车位最多100个。

华为OD对立考试A卷+B卷 新题库阐明2023年5月份，华为官网曾经将的 2022/0223Q(1/2/3/4)对立批改为OD对立考试（A卷）和OD对立考试（B卷）。你收到的链接下面会标注A卷还是B卷。请留神：依据反馈，目前大部分收到的都是B卷。然而仍有概率抽到A卷。A卷对应2023的新题库（2022Q4 20223Q1） B卷对应20022局部考题以及新出的题目 专栏：2023华为OD机试(A卷+B卷)（C++JavaJSPy）专栏：2023华为OD机试(A卷)（C++ Java JS Py）专栏：2023华为OD机试(B卷)（C++ Java JS Py） 题目形容运送的快递放在大小不等的长方体快递盒中，为了可能装载更多的快递同时不能让货车超载，须要计算最多能装多少个快递。 注：快递的体积不受限制 快递数最多1000个 货车载重最大50000

华为OD对立考试A卷+B卷 新题库阐明2023年5月份，华为官网曾经将的 2022/0223Q(1/2/3/4)对立批改为OD对立考试（A卷）和OD对立考试（B卷）。你收到的链接下面会标注A卷还是B卷。请留神：依据反馈，目前大部分收到的都是B卷。然而仍有概率抽到A卷。A卷对应2023的新题库（2022Q4 20223Q1） B卷对应20022局部考题以及新出的题目 专栏：2023华为OD机试(A卷+B卷)（C++JavaJSPy）专栏：2023华为OD机试(A卷)（C++ Java JS Py）专栏：2023华为OD机试(B卷)（C++ Java JS Py） 题目形容: 补种未成活胡杨近些年来，我国防沙治沙获得显著成绩。某沙漠新种植N棵胡杨（编号1-N），排成一排。 一个月后，有M棵胡杨未能成活。 现可补种胡杨K棵，请问如何补种（只能补种，不能新种），能够失去最多的间断胡杨树？ 输出形容N 总种植数量，1 <= N <= 100000 M 未成活胡杨数量，M 个空格分隔的数，按编号从小到大排列，1 <= M <= N K 最多能够补种的数量，0 <= K <= M

华为OD对立考试A卷+B卷 新题库阐明2023年5月份，华为官网曾经将的 2022/0223Q(1/2/3/4)对立批改为OD对立考试（A卷）和OD对立考试（B卷）。你收到的链接下面会标注A卷还是B卷。请留神：依据反馈，目前大部分收到的都是B卷。然而仍有概率抽到A卷。A卷对应2023的新题库（2022Q4 20223Q1） B卷对应20022局部考题以及新出的题目 专栏：2023华为OD机试(A卷+B卷)（C++JavaJSPy）专栏：2023华为OD机试(A卷)（C++ Java JS Py）专栏：2023华为OD机试(B卷)（C++ Java JS Py） 题目形容: 较量一个有N个选手加入较量，选手编号为1~N（3<=N<=100），有M（3<=M<=10）个评委对选手进行打分。打分规定为每个评委对选手打分，最高分10分，最低分1分。请计算得分最多的3位选手的编号。如果得分雷同，则得分高分值最多的选手排名靠前(10分数量雷同，则比拟9分的数量，以此类推，用例中不会呈现多个选手得分完全相同的状况)。输出形容第一行为半角逗号宰割的两个正整数，第一个数字示意M（3<=M<=10）个评委，第二个数字示意N（3<=N<=100）个选手。第2到M+1行是半角逗号宰割的整数序列，示意评委为每个选手的打分，0号下标数字示意1号选手分数，1号下标数字示意2号选手分数，顺次类推。

华为OD对立考试A卷+B卷 新题库阐明2023年5月份，华为官网曾经将的 2022/0223Q(1/2/3/4)对立批改为OD对立考试（A卷）和OD对立考试（B卷）。你收到的链接下面会标注A卷还是B卷。请留神：依据反馈，目前大部分收到的都是B卷。然而仍有概率抽到A卷。A卷对应2023的新题库（2022Q4 20223Q1） B卷对应20022局部考题以及新出的题目 专栏：2023华为OD机试(A卷+B卷)（C++JavaJSPy）专栏：2023华为OD机试(A卷)（C++ Java JS Py）专栏：2023华为OD机试(B卷)（C++ Java JS Py） 题目形容企业路由器的统计页面，有一个性能须要动静统计公司拜访最多的网页URL top N。请设计一个算法，能够高效动静统计Top N的页面。输出形容每一行都是一个URL或一个数字，如果是URL，代表一段时间内的网页拜访； 如果是一个数字N，代表本次须要输入的Top N个URL。 输出束缚： 1、总拜访网页数量小于5000个，单网页拜访次数小于65535次； 2、网页URL仅由字母，数字和点分隔符组成，且长度小于等于127字节； 3、数字是正整数，小于等于10且小于以后总拜访网页数；

华为OD对立考试A卷+B卷 新题库阐明2023年5月份，华为官网曾经将的 2022/0223Q(1/2/3/4)对立批改为OD对立考试（A卷）和OD对立考试（B卷）。你收到的链接下面会标注A卷还是B卷。请留神：依据反馈，目前大部分收到的都是B卷。然而仍有概率抽到A卷。A卷对应2023的新题库（2022Q4 20223Q1） B卷对应20022局部考题以及新出的题目 专栏：2023华为OD机试(A卷+B卷)（C++JavaJSPy）专栏：2023华为OD机试(A卷)（C++ Java JS Py）专栏：2023华为OD机试(B卷)（C++ Java JS Py） 题目形容众数是指一组数据中呈现次数量多的那个数，众数能够是多个。中位数是指把一组数据从小到大排列，最两头的那个数，如果这组数据的个数是奇数，那最两头那个就是中位数，如果这组数据的个数为偶数，那就把两头的两个数之和除以2，所得的后果就是中位数。查找整型数组中元素的众数并组成一个新的数组，求新数组的中位数。输出形容输出一个一维整型数组，数组大小取值范畴 0<N<1000，数组中每个元素取值范畴 0<E<1000

华为OD对立考试A卷+B卷 新题库阐明2023年5月份，华为官网曾经将的 2022/0223Q(1/2/3/4)对立批改为OD对立考试（A卷）和OD对立考试（B卷）。你收到的链接下面会标注A卷还是B卷。请留神：依据反馈，目前大部分收到的都是B卷。然而仍有概率抽到A卷。A卷对应2023的新题库（2022Q4 20223Q1） B卷对应20022局部考题以及新出的题目 专栏：2023华为OD机试(A卷+B卷)（C++JavaJSPy）专栏：2023华为OD机试(A卷)（C++ Java JS Py）专栏：2023华为OD机试(B卷)（C++ Java JS Py） 题目形容 用户调度问题在通信零碎中，一个常见的问题是对用户进行不同策略的调度，会失去不同的零碎耗费和性能。 假如以后有n个待串行调度用户，每个用户能够应用A/B/C三种不同的调度策略，不同的策略会耗费不同的系统资源。请你依据如下规定进行用户调度，并返回总的耗费资源数。 规定： 相邻的用户不能应用雷同的调度策略，例如，第1个用户应用了A策略，则第2个用户只能应用B或者C策略。对单个用户而言，不同的调度策略对系统资源的耗费能够归一化后形象为数值。例如，某用户别离应用A/B/C策略的零碎耗费别离为15/8/17。每个用户顺次抉择以后所能抉择的对系统资源耗费起码的策略（部分最优），如果有多个满足要求的策略，选最初一个。

华为OD对立考试A卷+B卷 新题库阐明2023年5月份，华为官网曾经将的 2022/0223Q(1/2/3/4)对立批改为OD对立考试（A卷）和OD对立考试（B卷）。你收到的链接下面会标注A卷还是B卷。请留神：依据反馈，目前大部分收到的都是B卷。然而仍有概率抽到A卷。A卷对应2023的新题库（2022Q4 20223Q1） B卷对应20022局部考题以及新出的题目 专栏：2023华为OD机试(A卷+B卷)（C++JavaJSPy）专栏：2023华为OD机试(A卷)（C++ Java JS Py）专栏：2023华为OD机试(B卷)（C++ Java JS Py） 题目形容有一个非凡的5键键盘，下面有a，ctrl-c，ctrl-x，ctrl-v，ctrl-a五个键。 a键在屏幕上输入一个字母a； ctrl-c将以后抉择的字母复制到剪贴板； ctrl-x将以后抉择的字母复制到剪贴板，并清空抉择的字母； ctrl-v将以后剪贴板里的字母输入到屏幕； ctrl-a抉择以后屏幕上的所有字母。 留神： 剪贴板初始为空，新的内容被复制到剪贴板时会笼罩原来的内容当屏幕上没有字母时，ctrl-a有效当没有抉择字母时，ctrl-c和ctrl-x有效当有字母被抉择时，a和ctrl-v这两个有输入性能的键会先清空抉择的字母，再进行输入给定一系列键盘输入，输入最终屏幕上字母的数量。

华为OD对立考试A卷+B卷 新题库阐明2023年5月份，华为官网曾经将的 2022/0223Q(1/2/3/4)对立批改为OD对立考试（A卷）和OD对立考试（B卷）。你收到的链接下面会标注A卷还是B卷。请留神：依据反馈，目前大部分收到的都是B卷。然而仍有概率抽到A卷。A卷对应2023的新题库（2022Q4 20223Q1） B卷对应20022局部考题以及新出的题目 专栏：2023华为OD机试(A卷+B卷)（C++JavaJSPy）专栏：2023华为OD机试(A卷)（C++ Java JS Py）专栏：2023华为OD机试(B卷)（C++ Java JS Py） 题目形容某学校举办运动会，学生们按编号(1、2、3…n)进行标识，现须要依照身高由低到高排列， 对身高雷同的人，按体重由轻到重排列； 对于身高体重都雷同的人，维持原有的编号程序关系。请输入排列后的学生编号。

题目的意思还是挺好了解的，解决的思路也很简略：因为只有一组差值和其余的不一样，所以最简略的方法能够通过前三组数据确定雷同的差值数据是什么，而后进行判断解决。 1）如果前三组差值数组都相等，那么和以后的差值数组不相等的就是后果；2）如果前三组数据有和其余两组不相等的，那么就是最终的后果，间接返回即可； class Solution {public: string oddString(vector<string>& words) { int n = words.size(); int slen=words[0].size(); vector<int> diff(slen-1, 0); for(int i=1; i<slen; i++){ diff[i-1] = words[0][i] - words[0][i-1]; } bool flag = true; int index=0; for(int i=1; i<slen; i++){ if(words[1][i] - words[1][i-1] != diff[i-1]){ flag = false; index=i; break; } } if(!flag){ return words[2][index] - words[2][index-1] == diff[index-1] ? words[1] : words[0]; }else{ for(int i=2; i<n; i++){ for(int j=1; j<slen; j++){ if(words[i][j] - words[i][j-1] != diff[j-1]){ return words[i]; } } } return ""; } }};

leetcode 977 题目链接：https://leetcode.com/problems/squares-of-a-sorted-array/ 最终ac代码:(双指针法) class Solution{public: vector<int> sortedSquares(vector<int> &nums) { vector<int> v; int left = 0; int right = nums.size() - 1; while (left <= right) { if (nums[left] * nums[left] < nums[right] * nums[right]) { v.push_back(nums[right] * nums[right]); --right; } else { v.push_back(nums[left] * nums[left]); ++left; } } reverse(v.begin(), v.end()); return v; }};std::vector operator[] 不做越界查看，vector::at 才查看 leetcode 209 题目链接:https://leetcode.com/problems/minimum-size-subarray-sum/ ac代码:(滑动窗口) 毛病：圈复杂度比拟大 class Solution{public: int minSubArrayLen(int target, vector<int> &nums) { int wl = 0; int wr = 0; int wsum = 0; int minWlen = INT_MAX; while (true) { if (wsum < target) { if (wr == nums.size()) break; wsum += nums[wr]; ++wr; } else { int wlen = wr - wl; if (wlen < minWlen) minWlen = wlen; wsum -= nums[wl]; ++wl; } } if (minWlen == INT_MAX) return 0; return minWlen; }};双循环版本(复杂度依然是O(n)，圈复杂度升高)： ...

leetcode 704 题目链接：https://leetcode.com/problems/binary-search/ 尝试 c++ 写题，搭建架子代码（尝试搭建ACM格调） class Solution{public: int search(vector<int> &nums, int target) { }};int main(){ Solution sol; vector<int> nums = {-1, 0, 3, 5, 9, 12}; sol.search({-1, 0, 3, 5, 9, 12}, 9); // 十分量援用的初始值必须为左值 // initial value of reference to non-const must be an lvalue}https://blog.csdn.net/hou09tian/article/details/80565343这边文章解释的很分明了，十分量援用传参进去后可能会被批改，如果是个右值显然是不行的 再次运行报不能够初始化，原来vscode默认只反对c++98规范，在.vscode里的task.json增加”-std=c++11“编译参数即可 算法思路文章参考：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E... 最终ac代码：（左闭右开） #include <iostream>#include <vector>using namespace std;class Solution {public: int search(vector<int>& nums, int target) { size_t start = 0; size_t end = nums.size(); while (start < end) { size_t middle = start + ((end - start) >> 1); if (nums[middle] == target) { return static_cast<int>(middle); } else if (nums[middle] > target) { end = middle; } else { start = middle + 1; } } return -1; }};再次尝试左闭右闭： ...

Leetcode 70 题有人问我：烤冷面你这两周怎么总搞简略题？我想说：一步一步来～ 题干简述给定： 假如你正在爬楼梯，须要爬 n 阶你能力达到楼顶。每次你能够爬 1 或 2 个台阶。要求：计算出有多少种爬楼梯的形式。 解题思路如果咱们放大视线（把大问题化为小问题），爬到第 n 阶台阶有两种形式： 从 n-1 阶爬一级台阶从 n-2 阶爬两级台阶用公式表白：dp[n] = dp[n−1] + dp[n−2]，其中的特例是：dp[0]=1 和 dp[1]=1。 嚯！这不就是LeetCode 509(斐波那契数列)么。 代码实现class Solution: def climbStairs(self, n: int) -> int: if n <= 2: return n dp = [0]*(n+1) dp[0] = 1 dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]复杂度工夫复杂度O(n)，空间复杂度O(n)。 关注公众号：「侵蚀脚本」，退出交换群。 文章归档：烤冷面讲算法系列 转载申明：本文章容许转载，原文地址：「动静布局」LeetCode 70(爬楼梯)

一、287. 寻找反复数给定一个蕴含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包含 1 和 n），可知至多存在一个反复的整数。假如只有一个反复的整数，找出这个反复的数。1、HashMap 在没有其它附加条件的状况下，读者第一工夫会想到通过 HashMap 来记录呈现过的数字，从而找到反复数： 上述实现代码的工夫复杂度和空间复杂度都为 O(n)，如果只容许应用 O(1) 的空间复杂度，该如何解决这道题目呢？ 2、Binary Search 这种条件下，最容易想到的就是通过两重循环暴力搜寻以后数字是否与前面的数字反复的办法来解决，然而这种计划的工夫复杂度为 O(n^2)，既然波及到了搜寻，就能够尝试通过二分搜索算法将工夫复杂度升高到 O(nlogn)。 依据后面的刷题教训，能够很容易地找出有序数组：1 到 n 的递增整数序列。 接下来的难点就是通过反复数的个性来确定下一轮搜寻区间是落在左半区间还是右半区间： 首先须要遍历 nums 数组，获取不大于以后两头数的数字的个数；如果个数大于两头数，那么下一轮搜寻区间落在左半区间；如果个数小于两头数，那么下一轮搜寻区间落在右半区间； 二、209. 长度最小的子数组给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的间断子数组。如果不存在符合条件的间断子数组，返回 0。1、Binary Search 这道题目中的有序数组不太好找，须要用到一个技巧：结构前缀和数组。 nums = [2, 3, 1, 2, 4, 3] # 前缀和 sums = [0, 2, 5, 6, 8, 12, 15] 从而上述示例中能够发现前缀和数组是一个有序数组，那么对于任意 i 到 j 的间断子数组之和，能够通过 sums[j+1] - sums[i] 求出。 ...

什么是动静布局动静布局，英文：Dynamic Programming，简称DP，将问题合成为互相重叠的子问题，通过重复求解子问题来解决原问题就是动静布局，如果某一问题有很多重叠子问题，应用动静布局来解是比拟无效的。 求解动静布局的外围问题是穷举，然而这类问题穷举有点特地，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动静布局问题肯定会具备「最优子结构」，能力通过子问题的最值得到原问题的最值。另外，尽管动静布局的核心思想就是穷举求最值，然而问题能够变幻无穷，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」能力正确地穷举。重叠子问题、最优子结构、状态转移方程就是动静布局三要素 动静布局和其余算法的区别动静布局和分治的区别：动静布局和分治都有最优子结构 ，然而分治的子问题不重叠动静布局和贪婪的区别：动静布局中每一个状态肯定是由上一个状态推导进去的，这一点就辨别于贪婪，贪婪没有状态推导，而是从部分间接选最优解，所以它永远是部分最优，然而全局的解不肯定是最优的。动静布局和递归的区别：递归和回溯可能存在十分多的反复计算，动静布局能够用递归加记忆化的形式缩小不必要的反复计算动静布局的解题办法递归+记忆化(自顶向下)动静布局（自底向上） 解动静布局题目的步骤依据重叠子问题定义状态寻找最优子结构推导状态转移方程确定dp初始状态确定输入值斐波那契的动静布局的解题思路[外链图片转存失败,源站可能有防盗链机制,倡议将图片保留下来间接上传(img-f0YqY2hz-1678842912336)(null)] 动画过大，点击查看 暴力递归//暴力递归复杂度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;};70. 爬楼梯 （medium）假如你正在爬楼梯。须要 n 阶你能力达到楼顶。 ...

一、二分搜索算法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. 寻找比指标字母大的最小字母 这道题目次要考查二分搜索算法的根本实现： ...

一、前言 个别状况下，遍历数组（或者字符串）操作，都是采纳单指针从前往后或者从后往前顺次拜访数组（或者字符串）中的元素。 而对于以下状况，只采纳单指针解决，则会徒增工夫复杂度和空间复杂度： 例如：找到两个数使得它们相加之和等于指标数，采纳单指针解决，则须要嵌套循环，使得工夫复杂度增长为 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. 验证回文串给定一个字符串，验证它是否是回文串，只思考字母和数字字符，能够疏忽字母的大小写。阐明：本题中，咱们将空字符串定义为无效的回文串。 回文字符串问题是双指针的经典利用，同时也是面试题中的常客。 ...

一、前言 本篇次要介绍双指针技巧的第二类题型：对数组进行预处理之后，再采纳双指针遍历。 在 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 来去重，然而整个双指针解题的过程中，三个数始终保持着非递加序列的个性，那么遇到反复数字间接跳过即可： ...

深度优先&广度优先 动画过大，点击查看 bfs:实用于层序遍历或者寻找最短门路的问。//bfs伪代码模版function bfs(graph, start, end) { queue = []; queue.append([start]); visited.add(start); while (queue) node = queue.pop(); visited.add(node); process(node); nodes = generate_related_nodes(node); queue.add(nodes);}dfs://dfs伪代码模版//递归function dfs(node, visited) { visited.add(node); for (next_node in node.children()) { if (!next_node in visited) dfs(next_node, visited); }}//非递归function dfs(tree) { if (tree.root === null) { return []; } visited, (stack = []), [tree.node]; while (stack) node = stack.pop(); visited.add(node); process(node); nodes = generate_ralated_nodes(node); stack.push(nodes);}695. 岛屿的最大面积 （medium）给你一个大小为 m x n 的二进制矩阵 grid 。 ...

一、前言 个别状况下，遍历数组（或者字符串）操作，都是采纳单指针从前往后或者从后往前顺次拜访数组（或者字符串）中的元素。 而对于以下状况，只采纳单指针解决，则会徒增工夫复杂度和空间复杂度： 例如：找到两个数使得它们相加之和等于指标数，采纳单指针解决，则须要嵌套循环，使得工夫复杂度增长为 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. 验证回文串给定一个字符串，验证它是否是回文串，只思考字母和数字字符，能够疏忽字母的大小写。阐明：本题中，咱们将空字符串定义为无效的回文串。 回文字符串问题是双指针的经典利用，同时也是面试题中的常客。 ...

思路很奢侈的一个思路就是，程序遍历数组，如果始终都是1，后果count也加1，如果遇到0，把count保留到max后而后置零，最初比照count、max哪个大，哪个大输入哪个。 谬误的题解func findMaxConsecutiveOnes(nums []int) int { max := 0 count := 0 for index := 0; index < len(nums); index++ { if (nums[index] == 1) { count++ } else { if (count > max) { max = count count = 0 } } } if (count > max) { max = count } return max}错在哪里？看了下没通过的那个测试用例，大略是这样散布的 [1, 1, .... , 0, 1, 1, 1, ... , 0, 1, 1, 1, ... 0, 1, ... ,1] ...

前言常常会有人问，作为前端，你在理论工作中用到过哪些算法，之前我答复是，树和位运算，而最近在学习网络模块，发现了和前端，起码是和网络相干的一种算法，那就是 滑动窗口； 咱们晓得在 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 指针只须要保留对应的极值(第一个或者最初一个)，而后求出极值即可最初滑窗是双指针的一种非凡状况，咱们在应用双指针解决问题的时候，可能不会思考前一个窗口里的状态值，只是将所有状况都思考进行，这样就会有很多计算是反复的，滑窗就是一种优化了的双指针状况。 ...

前言明天没啥前言，分治很难，次要难在如何拆分后比拟好治理合并，这比二分这些只有拆了就完结要难上一个 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}剖析 -- 贪婪 ...

汇合与字典 ：汇合常见的模式是Set，字典常见的模式是MapSet 和 Map 次要的利用场景在于 数据重组 和 数据贮存。汇合 与 字典 的区别： 共同点：汇合、字典 能够贮存不反复的值不同点：汇合相似于数组，元素的只有key没有value，value就是key。字典是以 [key, value] 的模式贮存，键的范畴不限于字符串，各种类型的值（包含对象）都能够当作键工夫复杂度： set或map能够用哈希表或均衡二叉搜寻树实现 哈希表实现的map或者set查找的工夫复杂度是O(1)，哈希表长处是查找十分快，哈希表的毛病是失去了数据的程序性，均衡二叉搜寻树实现的map或set查找时间复杂度是O(logn)，它保障了数据程序性 哈希函数哈希函数是一个承受输出值的函数，由此输出计算出一个确定输入。 均匀分布：哈希函数计算出来的地址均匀分布哈希碰撞：哈希函数计算出来的后果抵触 凋谢定址法链地址法 447. 盘旋镖的数量 (medium)给定立体上 n 对 互不雷同 的点 points ，其中 points[i] = [xi, yi] 。盘旋镖 是由点 (i, j, k) 示意的元组 ，其中 i 和 j 之间的间隔和 i 和 k 之间的欧式间隔相等（须要思考元组的程序）。 返回立体上所有盘旋镖的数量。 示例 1： 输出：points = [[0,0],[1,0],[2,0]]输入：2解释：两个盘旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]示例 2： 输出：points = [[1,1],[2,2],[3,3]]输入：2示例 3： 输出：points = [[1,1]]输入：0 提醒： ...

前言常常会有人问，作为前端，你在理论工作中用到过哪些算法，而我答复个别是，树和位运算； 想想 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只呈现一次的数字 -- 所有题目都是线性工夫复杂度，空间复杂度都是常数级复杂度剖析如果题目看错是只有一个值呈现一次，其余都呈现两次，那么间接异或就能够得出后果；当初是有两个值只呈现一次，所以异或和失去的就是这两个值的异或和，所以须要将原数组拆解成两份 ...

注释 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; }}参考视频：传送门 ...

注释在前端中的确用到不少与树相干的的常识，比方说 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 有三种模式，但在形象到具体题目的时候，其实是属于不同的办法的。 ...

85. 最大矩形 (hard)给定一个仅蕴含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只蕴含 1 的最大矩形，并返回其面积。 示例 1： 输出：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输入：6解释：最大矩形如上图所示。示例 2： 输出：matrix = []输入：0示例 3： 输出：matrix = [["0"]]输入：0示例 4： 输出：matrix = [["1"]]输入：1示例 5： 输出：matrix = [["0","0"]]输入：0 提醒： rows == matrix.lengthcols == matrix[0].length1 <= row, cols <= 200matrixi 为 '0' 或 '1' 办法1.枯燥栈 思路：84题的变种，从第一行到第n行造成的柱状图能够利用84题求解，而后循环每一行，计算以这一行为底的柱状图最大面积，而后更新最大矩形面积复杂度：工夫复杂度O(mn)，m、n别离是矩形的高度和宽度，循环m次行，每行里循环每个柱子的高度。空间复杂度O(n)，heights数组的空间。js： var maximalRectangle = function (matrix) { if (matrix.length == 0) return 0; let res = 0; let heights = new Array(matrix[0].length).fill(0);//初始化heights数组 for (let row = 0; row < matrix.length; row++) { for (let col = 0; col < matrix[0].length; col++) { if(matrix[row][col] == '1' ) heights[col] += 1; else heights[col] = 0; }//求出每一层的 heights[] 而后传给84题的函数 res = Math.max(res, largestRectangleArea(heights));//更新一下最大矩形面积 } return res;};const largestRectangleArea = (heights) => { let maxArea = 0 const stack = [] //枯燥递增栈 留神栈存的时下标 heights = [0, ...heights, 0] //在heights数组前后减少两个哨兵 用来清零枯燥递增栈里的元素 for (let i = 0; i < heights.length; i++) { //以后元素对应的高度小于栈顶元素对应的高度时 while (heights[i] < heights[stack[stack.length - 1]]) { const stackTopIndex = stack.pop() //出栈 maxArea = Math.max( //计算面积 并更新最大面积 maxArea, heights[stackTopIndex] * (i - stack[stack.length - 1] - 1)//高乘宽 ) } stack.push(i)//以后下标退出栈 } return maxArea}496. 下一个更大元素 I (easy）nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应地位 右侧 的 第一个 比 x 大的元素。 ...

前言博主最近在刷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;};接下来咱们逐行剖析代码。 ...

目录Stack的特点：先进后出（FILO）应用场景：十进制转2进制 函数调用堆栈js里没有栈，然而能够用数组模仿 42/2 42%2=021/2 21%2=110/2 10%2=05/2 5%2=12/2 2%2=01/2 1%2=1stack: [0,1,0,1,0,1]res: 1 0 1 0 1 0fn1(){ fn2()}fn2(){ fn3() }fn3(){}fn1()stack:[fn1,fn2,fn3]栈的工夫复杂度：入栈和出栈O(1)，查找O(n) 946. 验证栈序列 （medium）给定 pushed 和 popped 两个序列，每个序列中的 值都不反复，只有当它们可能是在最后空栈上进行的推入 push 和弹出 pop 操作序列的后果时，返回 true；否则，返回 false 。 示例 1： 输出：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输入：true解释：咱们能够按以下程序执行：push(1), push(2), push(3), push(4), pop() -> 4,push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1示例 2： 输出：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]输入：false解释：1 不能在 2 之前弹出。 ...

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. 无效的括号 ...

注释 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个最大元素剖析 ...

位运算根底：程序中所有的数载计算机内存中都是以二进制存储的，位运算就是间接对整数在内存中的二进制进行操作，因为间接在内存中进行操作，不须要转成十进制，因而处理速度十分快 常见位运算 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: ...

前言回溯，就是无脑冲，碰壁之后就回撤一步持续搞，属于一种暴力解题的思路； 实际上也是如此，当咱们在遇到一些分类探讨的问题，无奈想到比拟精妙的解决方案，咱们第一工夫思考到的就是暴力枚举所有状况，而后再做解决，而 回溯 就是这样的一个暴力法 下一个 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剖析 ...

前端就该用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}参考视频：传送门 ...

目录Trie树，即字典树，又称前缀树，是一种树形构造，典型利用是用于统计和排序大量的字符串（但不限于字符串），所以常常被搜索引擎用于文本词频统计。它的优先是，最大限度的缩小无谓的字符串比拟，进步查找效率。 Trie的核心思想是空间换工夫，利用字符串的公共前缀来升高查问工夫的开销，以达到提高效率的目标 根本性质 根节点不蕴含字符，除跟节点外每个节点都只蕴含一个字符从根节点到某一个节点，门路上通过的字符连接起来，为该节点对应的字符串每个节点的所有子节点蕴含的字符都不雷同<img src="https://xiaochen1024.com/20211118161003.png" alt="ds_8" style="zoom:50%;" /> 理论利用，例如搜寻 720. 词典中最长的单词 (easy)给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其余单词逐渐增加一个字母组成。 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。 示例 1： 输出：words = ["w","wo","wor","worl", "world"]输入："world"解释： 单词"world"可由"w", "wo", "wor", 和 "worl"逐渐增加一个字母组成。示例 2： 输出：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]输入："apple"解释："apply" 和 "apple" 都能由词典中的单词组成。然而 "apple" 的字典序小于 "apply" 提醒： 1 <= words.length <= 10001 <= words[i].length <= 30所有输出的字符串 words[i] 都只蕴含小写字母。 办法1：sort+hash思路：排序数组，而后遍历字符串数组，判断数组中的每个字符串的子串是否都在数组中复杂度：工夫复杂度O(mn)，m是字符串数组的长度,n是字符串最大长度。空间复杂度O(m)js： var longestWord = function (words) { let set = new Set() words.forEach(v => set.add(v))//set不便查找 //先按长度排序，在按字典序 words.sort((a, b) => a.length === b.length ? a.localeCompare(b) : b.length - a.length) for (let i = 0; i < words.length; i++) { let flag = true for (let j = 1; j < words[i].length; j++) { if (!set.has(words[i].substring(0, j))) {//查看set中是否有该字符串的每个子串 flag = false break } } if (flag) { return words[i] } } return ''};办法2:字典树 ...

前言上一 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. 寻找反复数剖析 -- 双指针法（快慢指针） ...

对于二分题，其实就是设定一个两头值 mid, 而后通过这个值进行一个判断 check(mid)， 通过这个函数的返回值，判断将不可能的一半剪切掉； 在刷题的时候须要留神次要是两局部，check 函数的定义以及边界的抉择（等号的抉择，以及最初是 return left 还是 right） 这次次要是 LC 的二分专题，外面的简略题根本都是比拟显性的提醒了 check 函数的构建，比方说间接找出某个值，而难题个别都是 check 函数比拟难想的，这个时候就须要教训了； 狭义上只有是排好序（部分排序），只有是找某个值，大部分都能够思考用二分，这样复杂度能够升高很多； 对于边界，我的循环完结条件是 left <= right ， 因为如果要多记很多模板，怕会出问题，所以退出条件根本都按这个，而后无论是那种模块，都基于这个完结条件来判断，这样能够把问题膨胀都循环里的断定的 check 函数，多做了就会发现端倪； 而后对于退出之后 left 还是 right ，这个是具体问题具体分析；因为我的完结断定条件是 left<=right ，所以如果没用两头返回，那么必然存在 left === right 的时候，这个时候依据断定条件，就晓得 right 在 left 的后面，而到底是左迫近，还是右迫近，都比拟好判断了，因为这个时候曾经退出去了，left 和 right 所代表的 check 的状态也是不言而喻的，那么看题目要求什么，给什么即可； 对于二分，我感觉这个专题就根本足够了，简略居多，难题也有两个；如果是第一次学习二分，那么依照专栏的三个模板去记忆也 ok， 他人的教训终归是适宜他人本人，做题最重要是把握住本人的节奏，记忆本人最相熟的那个点，强行模拟他人反而落了下乘； 当然那个男人那么强，我的做题就是模拟的他，缓缓大佬的解法就是我本人的节奏了，毕竟模拟多了，其实就是本人的了，除了算法，其余的工程化学习也是一样的； 那么，周末高兴，下周开 dp 吧，毕竟这个听有意思的。 模板 1目标值是一个固定的 target，在二分过程中须要一直的判断，如果胜利就返回对应的值，否则间接返回失败的值返回值如果是向下取，返回 right，如果向上取，则返回 left，还有可能返回一个特定给的失败值；var search = function (fn, target) { let left = 最小值, right = 最大值; while (left <= right) { // 取 mid 值 const mid = ((right - left) >> 1) + left; //这里的 fn 可能是函数，也可能只是数组取值，反正就是能够获得一个值去跟 target 比拟 const temp = fn(mid); if (temp === target) return mid; if (temp < target) { left = mid + 1; } else { right = mid - 1; } } return 没有准确匹配后的值;};704. 二分查找var search = function (nums, target) { const len = nums.length; if (!len) return -1; let left = 0, right = len - 1; while (left <= right) { const mid = ((right - left) >> 1) + left; if (nums[mid] === target) return mid; if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1;};69. x 的平方根// 69. x 的平方根var mySqrt = function (x) { let left = 0, right = x; while (left <= right) { const mid = ((right - left) >> 1) + left; const sqrt = mid * mid; if (sqrt === x) return mid; if (sqrt < x) { left = mid + 1; } else { right = mid - 1; } } // 向下取整 return right;};374. 猜数字大小剖析 ...

剪枝排除那些不符合条件的分支。进步程序的运行效率。 回溯：一层层递归，尝试搜素答案， 找到答案：返回后果，尝试其余的分支找不到答案：返回上一层，尝试其余分支回溯模版： result = [];function backtrack (path, list) { if (满足条件) { result.push(path); return } for () { // 单层逻辑 backtrack (path, list) // 撤销抉择 重置状态 }}回溯四部曲： 回溯参数终止条件单层递归逻辑抉择其余分支（撤销抉择 重置状态）473. 火柴拼正方形 (medium)你将失去一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你能够把它们连在一起，而且每根火柴棒必须 应用一次 。 如果你能使这个正方形，则返回 true ，否则返回 false 。 示例 1: 输出: matchsticks = [1,1,2,2,2]输入: true解释: 能拼成一个边长为2的正方形，每边两根火柴。示例 2: 输出: matchsticks = [3,3,3,3,4]输入: false解释: 不能用所有火柴拼成一个正方形。 提醒: 1 <= matchsticks.length <= 151 <= matchsticks[i] <= 108 ...

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 ...

前言某个男人 动静布局,而我作为一个致力称为厨师界最会写算法的前端，总得刷上一部分题，有那么一点发现吧，当初咱们就来聊聊，菜鸡如我，发现了什么。 注释汇总这周学习的当初，我脑壳疼的慌，啥货色都想不到，然而为了不破本人每周都总结一下下的指标，只能水几句了； 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剖析 ...

目录Stack的特点：先进后出（FILO）应用场景：十进制转2进制 函数调用堆栈js里没有栈，然而能够用数组模仿 42/2 42%2=021/2 21%2=110/2 10%2=05/2 5%2=12/2 2%2=01/2 1%2=1stack: [0,1,0,1,0,1]res: 1 0 1 0 1 0fn1(){ fn2()}fn2(){ fn3() }fn3(){}fn1()stack:[fn1,fn2,fn3]栈的工夫复杂度：入栈和出栈O(1)，查找O(n) 155. 最小栈 (easy)设计一个反对 push ，pop ，top 操作，并能在常数工夫内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。 示例 1: 输出：["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]] 输入：[null,null,null,null,-3,null,0,-2] 解释：MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); --> 返回 -3.minStack.pop();minStack.top(); --> 返回 0.minStack.getMin(); --> 返回 -2. 提醒： -231 <= val <= 231 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 104 次 ...

各类题的解决方案话不多说，零碎整顿下解题的一些算法和解决方案 二叉树二叉树大多应用递归的形式左右两个元素向下递归。比方： 计算二叉树最大深度 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 到指标额度所需的最小硬币数都列出来。 ...

并查集（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'（水）组成的的二维网格，请你计算网格中岛屿的数量。 ...

首先须要理解链表的概念 先把 next 记录下来无论是插入，删除，还是翻转等等操作，先把 next 指针用长期变量保存起来，这能够解决 90% 重组链表中指向出错的问题， 如果不晓得什么时候须要用到守卫，那就都用类型守卫 emptyNode 是创立的一个空的节点，并将它连贯到 head 节点之前，无论链表进行任何操作， emptyNode 都指向最初的头节点，是一个很实用的小办法，如果不晓得什么时候用，什么时候不必，那就先都用起来吧； 其实在大部分时候，emptyNode 都是能用上，即使只是遍历查找值，用上作为第 0 个值，当要找第 k 个值的时候，也不须要再判空解决啊 头节点判空解决如果懒或者常常遗记看题目的给定条件，头节点判空都做起来，对于一些翻转题，还得将 head.next 也判断起来； 到纯熟之后，其实能够不做，然而用上最多就节约一段代码，也还好 画图，画图，画图遇事不决的时候，还是要画图，一步一步的连起来，总可能捋分明的，画图是链表的关键所在 链表的节点是保留在内存中的一个数据结构链表是一个特定的数据结构，在 JS 中能够体现为一个领有 val 和 next 属性的对象，所以遇到形如替换两个链表节点的时候，千万不能替换两个链表的 val 值，尽管 LC 有一些题是能够过，然而实际上是不合理的，而且一旦呈现这种思维，对于一些经典题 160. 相交链表 就会了解不了； 记住，链表是一个数据结构，不是一个值，能够类比成一个对象，替换链表比方不是简略替换值； 都是中等题这里选的都是依照 LC 炽热排序，中等难度的题，感觉纯链表学习做特地难没太大必要，毕竟我只是一个菜鸟，大佬们能够自由选择，一起 ，进大厂； 具体题解剑指 Offer 24. 反转链表剖析 留神爱护好下一个节点 next而后一直保护上一个节点和以后阶段，一直往后推即可var reverseList = function (head) { let prev = null; while (head) { const next = head.next; head.next = prev; prev = head; head = next; } return prev;};面试题 02.05. 链表求和剖析 ...

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

目录Trie树，即字典树，又称前缀树，是一种树形构造，典型利用是用于统计和排序大量的字符串（但不限于字符串），所以常常被搜索引擎用于文本词频统计。它的优先是，最大限度的缩小无谓的字符串比拟，进步查找效率。 Trie的核心思想是空间换工夫，利用字符串的公共前缀来升高查问工夫的开销，以达到提高效率的目标 根本性质 根节点不蕴含字符，除跟节点外每个节点都只蕴含一个字符从根节点到某一个节点，门路上通过的字符连接起来，为该节点对应的字符串每个节点的所有子节点蕴含的字符都不雷同<img src="https://xiaochen1024.com/20211118161003.png" alt="ds_8" style="zoom:50%;" /> 理论利用，例如搜寻 720. 词典中最长的单词 (easy)给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其余单词逐渐增加一个字母组成。 若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。 示例 1： 输出：words = ["w","wo","wor","worl", "world"]输入："world"解释： 单词"world"可由"w", "wo", "wor", 和 "worl"逐渐增加一个字母组成。示例 2： 输出：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]输入："apple"解释："apply" 和 "apple" 都能由词典中的单词组成。然而 "apple" 的字典序小于 "apply" 提醒： 1 <= words.length <= 10001 <= words[i].length <= 30所有输出的字符串 words[i] 都只蕴含小写字母。 办法1：sort+hash思路：排序数组，而后遍历字符串数组，判断数组中的每个字符串的子串是否都在数组中复杂度：工夫复杂度O(mn)，m是字符串数组的长度,n是字符串最大长度。空间复杂度O(m)js： var longestWord = function (words) { let set = new Set() words.forEach(v => set.add(v))//set不便查找 //先按长度排序，在按字典序 words.sort((a, b) => a.length === b.length ? a.localeCompare(b) : b.length - a.length) for (let i = 0; i < words.length; i++) { let flag = true for (let j = 1; j < words[i].length; j++) { if (!set.has(words[i].substring(0, j))) {//查看set中是否有该字符串的每个子串 flag = false break } } if (flag) { return words[i] } } return ''};办法2:字典树 ...

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

前言学习算法的时候，总会有一些让人生畏的名词，比如动静布局，贪婪算法 等，听着就很难；而这一 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. 最大子序和剖析 -- 贪婪 ...

数组操作的工夫复杂度Access：O(1)Search：O(n)Insert： 均匀O(n)，最好的状况下O(1)，也就是在数组尾部插入O(1)，最坏的状况下O(n)Delete；均匀O(n)，最好的状况下O(1)，也就是在数组尾部删除O(1)，最坏的状况下O(n) 75. 色彩分类 （medium）给定一个蕴含红色、红色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得雷同色彩的元素相邻，并依照红色、红色、蓝色顺序排列。 咱们应用整数 0、 1 和 2 别离示意红色、红色和蓝色。 必须在不应用库的sort函数的状况下解决这个问题。 示例 1： 输出：nums = [2,0,2,1,1,0]输入：[0,0,1,1,2,2]示例 2： 输出：nums = [2,0,1]输入：[0,1,2] 提醒： n == nums.length1 <= n <= 300nums[i] 为 0、1 或 2 进阶： 你能够不应用代码库中的排序函数来解决这道题吗？你能想出一个仅应用常数空间的一趟扫描算法吗？ 动画过大，点击查看 办法1.双指针思路：筹备p0，p1两个指针，p0指向0元素，p1指向1，初始化的时候，两个指针都指向数组的第一个地位。而后循环数组 遇见1就替换以后元素和p1，让p1加1，向前挪动一位遇见0就替换以后元素和p0，如果p1小于p0，则此时p0指向的元素是1，与i地位元素替换之后 这个替换过来的1地位就不对了，所以替换过来的1须要在和p1替换一下，这时p0和p1都指向了正确的元素，所以都须要向前挪动一次。如果p0等于p1，则后面的元素都是0，所以p0和p1也要向前挪动一次复杂度：工夫复杂度O(n)，n是数组的长度，空间简单O(1)js： var sortColors = function (nums) { let p0 = 0 //指向0 let p1 = 0 //指向0 for (let i = 0; i < nums.length; i++) { if (nums[i] === 1) {//如果以后i指向的元素等于1，则替换以后元素和p1指向的元素 let temp = nums[p1] nums[p1] = nums[i] nums[i] = temp p1++ } else if (nums[i] === 0) {//如果以后i指向的元素等于0，则替换以后元素和p0指向的元素 let temp = nums[p0] nums[p0] = nums[i] nums[i] = temp //如果p0小于p1 则此时p0指向的元素是1，与i地位元素替换之后 这个替换过来的1地位就不对了 所以替换过来的1须要在和p1替换一下 if (p0 < p1) { temp = nums[i]; nums[i] = nums[p1]; nums[p1] = temp; } //每次替换0之后都要挪动p0和p1，如果p0===p1，则后面都是0，如果p0<p1,后面的代码曾经替换了两次 p0++ p1++ } }};办法2.双指针思路：筹备两指针，p0指向元素0，它右边的都是0，p2指向2，它左边都是2，而后循环数组，当循环到了p2，阐明p2左边的元素都是正确的数，所以i<=p2 ...

一、链表链表（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 记录节点对象，如果呈现反复的节点则有环。 第二种解法是采纳双指针中的快慢指针技巧：当链表中存在环时，快指针必然能追上慢指针。

一、287. 寻找反复数给定一个蕴含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包含 1 和 n），可知至多存在一个反复的整数。假如只有一个反复的整数，找出这个反复的数。1、HashMap 在没有其它附加条件的状况下，读者第一工夫会想到通过 HashMap 来记录呈现过的数字，从而找到反复数： 上述实现代码的工夫复杂度和空间复杂度都为 O(n)，如果只容许应用 O(1) 的空间复杂度，该如何解决这道题目呢？ 2、Binary Search 这种条件下，最容易想到的就是通过两重循环暴力搜寻以后数字是否与前面的数字反复的办法来解决，然而这种计划的工夫复杂度为 O(n^2)，既然波及到了搜寻，就能够尝试通过二分搜索算法将工夫复杂度升高到 O(nlogn)。 依据后面的刷题教训，能够很容易地找出有序数组：1 到 n 的递增整数序列。 接下来的难点就是通过反复数的个性来确定下一轮搜寻区间是落在左半区间还是右半区间： 首先须要遍历 nums 数组，获取不大于以后两头数的数字的个数；如果个数大于两头数，那么下一轮搜寻区间落在左半区间；如果个数小于两头数，那么下一轮搜寻区间落在右半区间； 二、209. 长度最小的子数组给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的间断子数组。如果不存在符合条件的间断子数组，返回 0。1、Binary Search 这道题目中的有序数组不太好找，须要用到一个技巧：结构前缀和数组。 nums = [2, 3, 1, 2, 4, 3] # 前缀和 sums = [0, 2, 5, 6, 8, 12, 15] 从而上述示例中能够发现前缀和数组是一个有序数组，那么对于任意 i 到 j 的间断子数组之和，能够通过 sums[j+1] - sums[i] 求出。 ...

一、前言 二分搜索算法自身并不是特地简单，外围点次要集中在： 有序数组：指的是一个递增或者递加的区间（非凡状况如：【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 必然落在左半区间； ...

一、前言 《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. 水果成篮》的解题思路如出一撤： ...

42. 接雨水 （hard）给定 n 个非负整数示意每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 输出：height = [0,1,0,2,1,0,1,3,2,1,2,1]输入：6解释：下面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 示意的高度图，在这种状况下，能够接 6 个单位的雨水（蓝色局部示意雨水）。 示例 2： 输出：height = [4,2,0,3,2,5]输入：9 提醒： n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105 思路：首先思考暴力做法，找找思路，暴力做法能够遍历数组，在每个地位别离往两边寻找左柱子中的最大高度和右柱子中的最大高度，找到之后，用左右最大高度的较小者减去以后柱子的高度，就是以后地位能接的水量。该办法要循环整个数组，并且每个地位要遍历数组寻找左右柱子高度的最大值，嵌套了一层循环，所以复杂度是O(n^2)。 咱们怎么减速嵌套的这层循环呢，其实能够事后计算从左往右和从右往左的最大高度数组，在循环数组的时候，能够间接拿到该地位左右两边的最大高度，以后地位的接水量就是左右两边高度的较小者减去以后地位柱子的高度 复杂度：工夫复杂度O(n)，寻找左右的最大高度，循环计算每个地位的接水量，总共3个循环，但他们不是嵌套关系。空间复杂度是O(n)，n是heights数组，用到了leftMax和rightMax数组，即寄存左右两边最大高度的数组。办法1.动静布局动画过大，点击查看 js： var trap = function(height) { const n = height.length; if (n == 0) {//极其状况 return 0; } const leftMax = new Array(n).fill(0);//初始化从左往右看的最大值数组 leftMax[0] = height[0]; for (let i = 1; i < n; ++i) { leftMax[i] = Math.max(leftMax[i - 1], height[i]); } const rightMax = new Array(n).fill(0);//初始化从右往左看的最大值数组 rightMax[n - 1] = height[n - 1]; for (let i = n - 2; i >= 0; --i) { rightMax[i] = Math.max(rightMax[i + 1], height[i]); } let ans = 0; //循环数组，每个地位能接的雨水量就是这个地位左右最大值的较小者减去以后的高度 for (let i = 0; i < n; ++i) { ans += Math.min(leftMax[i], rightMax[i]) - height[i]; } return ans;};办法2:枯燥栈动画过大，点击查看 ...

工作太忙没有工夫刷算法题，面试的时候好心虚。这里双手奉上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]二叉树的最小深度给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短门路上的节点数量。阐明: 叶子节点是指没有子节点的节点。 ...

题目形容给定一个整数，写一个函数来判断它是否是 4 的幂次方。如果是，返回 true ；否则，返回 false 。 整数 n 是 4 的幂次方需满足：存在整数 x 使得 n == 4x 示例 1： 输出： n = 16输入： true示例 2： 输出： n = 5输入： false示例 3： 输出： n = 1输入： true力扣原题目地址 4 的幂：https://leetcode.cn/problems/...相似题目还有3的幂，2的幂，用递归思维解决，一个意思 力扣原题目地址 3 的幂：https://leetcode.cn/problems/... 力扣原题目地址 2 的幂：https://leetcode.cn/problems/... 思路剖析整数n如果是0，必定不是4的幂了，如果是1，就是4的0次幂。这样的话，咱们就把整数n不停的除以4，如果除到最初的后果是1，那么是幂。如果除的话，失去的数是一个小数，那么就必定不是幂了这里又延长出一个问题，就是，js中如何判断一个数，是不是整数？ 没关系，语言的设计者们，早曾经思考到这种状况了，于是给咱们一个api叫做：Number.isInteger()，用于判断一个数字是不是整数，如下： Number.isInteger(0); // trueNumber.isInteger(1); // trueNumber.isInteger(-100000); // trueNumber.isInteger(0.1); // falseNumber.isInteger(Math.PI); // falseNumber.isInteger(Infinity); // falseNumber.isInteger(-Infinity); // falseNumber.isInteger("10"); // falseNumber.isInteger(true); // falseNumber.isInteger(false); // falseNumber.isInteger([1]); // false这样的话，咱们间接拿来应用即可 代码附上var isPowerOfFour = function (n) { if (n === 0) { // 0必定不是，间接返回false return false } else if (n == 1) { // 4的0次方等于1，是返回true return true } else { n = n / 4 // 4的幂、3的幂、2的幂 if (Number.isInteger(n)) { // 如果是整数，就持续递归 return isPowerOfFour(n) // return的后果为递归执行的后果 } else { // 如果不是整数，就阐明相对不是4的n次方 return false } }};提交后果图 ...

什么双指针没刷算法之前，一听双指针，感觉很厉害的样子。实际上呢？也确实是一个不错的解题思路形式。 在LeetCode上的双指针是一大类题目的解决形式，看一下，发现有近200题是双指针类型的，如下图： 由此可见，双指针的重要性。 那，什么是双指针？在说双指针之前，咱们先看一下**单指针**。比方咱们平时遍历一个数组，都是定义一个变量let i，通过这个变量i能够拜访到每一项的值，这是罕用的形式，能够权且称之为**单指针**吧，如下代码： for (let i = 0; i < arr.length; i++) { // ......}对应的，通俗易懂地说，双指针是：在遍历循环的时候，定义两个变量作为索引，去做一些查找判断代码操作。 依照双指针的指针静止方向，又分为对撞指针、快慢指针、以及综合类的多指针。 对撞指针对撞指针就是定义两个变量索引，一左一右，因为而后左侧的往右走、右侧的往左走，直至会合相遇相撞停下对撞个别搭配while循环多一些对撞指针是有对应的模板套路公式的，如下：var doublePointerFn = function(params){ let left = 0 // 左侧指针，从第一项开始 let right = params.length - 1 // 左侧指针从最初一项开始 // 当左侧指针的地位小于右侧指针时，始终执行，直到左侧指针大于右侧指针才停下 while(left <= right){ // 代码操作 left = left + 1 // 左侧指针往右走 right = right - 1 // 右侧指针往左走 } // [代码操作]}笔者之前刷题中，有应用双指针形式（对撞指针）进行解题的，如下链接： 力扣之x的平方根（双指针解法思路剖析优化）https://segmentfault.com/a/11...力扣之反转字符串之原地批改输出数组（双指针形式）https://segmentfault.com/a/11...道友有空能够看看，咱们持续往下浏览快慢指针快慢指针也是两个指针都是从一侧登程可能一个指针跑得快，另一个指针跑得慢，直至相遇操作对于快慢指针的利用题目次要是链表的一些操作，笔者还没刷到链表题目，这里先不总结了，后续补上 多指针多指针个别用在略微简单一些的题目上，对 对撞指针和快慢指针 进行综合的考量。 明天咱们持续来应用对撞指针来做一道简略的题目：力扣之回文数 题目形容给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。 回文数是斧正序（从左向右）和倒序（从右向左）读都是一样的整数。 例如，121 是回文，而 123 不是。示例 1： ...

题目形容编写一个函数，其作用是将输出的字符串反转过去。输出字符串以字符数组 s 的模式给出。 不要给另外的数组调配额定的空间，你必须原地批改输出数组、应用 O(1) 的额定空间解决这一问题。 示例 1： 输出： s = ["h","e","l","l","o"]输入： ["o","l","l","e","h"]示例 2： 输出： s = ["H","a","n","n","a","h"]输入： ["h","a","n","n","a","H"]提醒： 1 <= s.length <= 105s[i] 都是 ASCII 码表中的可打印字符力扣原题目地址：https://leetcode.cn/problems/...思路解法剖析大多数人，看到这个题目当前，心想：呵！间接调用数组的reverse()办法不就行啦。其实这确实是一种解决方案。只不过题目要求：原地批改输出数组、应用 O(1)  的额定空间。也就是说，要尽可能应用较小的内存去操作，这也是性能优化的一种尝试。 咱们想一下，其实数组的reverse()办法的最终成果是，反转一个数组，如： let arr = [1,2,3,4,5]console.log(arr); // [1,2,3,4,5]console.log(arr.reverse()); // [5,4,3,2,1]咱们发现，反转当前的数组只不过是首尾对应地位颠倒了罢了，换句话说，就是地位替换，地位替换，地位替换 那么，一说到数组的地位替换，咱们会想到哪几种形式呢？ 1.应用长期变量替换， 如下： let arr = ['甲', '乙']let temp;temp = arr[0]arr[0] = arr[1]arr[1] = tempconsole.log(arr); // ['乙','甲']冒泡排序的感觉...2.应用ES6的解构赋值进行操作， 如下： let arr = ['甲', '乙']arr = ([arr[0], arr[1]] = [arr[1], arr[0]]); // 即：arr = [arr[0], arr[1]] = [arr[1], arr[0]]console.log(arr); // ['乙', '甲']通过上述形式，咱们发现，既然是替换对应地位的两个元素，那么只有这两个元素的索引咱们通晓即可。在心中默念，两个元素的索引、两个元素的索引、两个... ...

Day2977.有序数组的平方题目倡议： 本题关键在于了解双指针思维 暴力解法:先平方 ，后排序。 双指针法 左正数，两头靠近零，右负数，平方后两边大两头小 左右2个指针从头开始，相互比大小，谁更大就把值赋给新的数组，再向两头挪动一格，留神从数组的最大下标开始赋值以满足非递加。 留神i<=j否则最初一个元素无奈赋值到新数组中 209.长度最小的子数组滑动窗口，也是双指针的一种 值大于s，比拟长度后左端就要向右挪动放大窗口 将开始的返回值设置为INT32_MAX,是int类型中最大的值 for外面套while，每次右端向右挪动单位一，如果满足>=s，左端继续向右挪动直到sum<s,之后进行下一次for循环，右端向右挪动一。 如果始终挪动，直到整个数组的和都无奈大于s，则返回0，阐明没有这样的子序列 其中2次应用" ? : "构造简化代码 工夫复杂度：只管for套了while，然而每个元素进出共2次，2*n 所以是O (n)。 59.螺旋矩阵II题目倡议： 本题要害还是在转圈的逻辑，在二分搜寻中提到的区间定义，在这里又用上了。 保持循环不变量准则 如图，区间左开右闭 vector<vector<int>> res(n, vector<int>(n, 0));  // 应用vector定义一个二维数组   j < n - offset; // offset 管制每一圈里每一条边遍历的长度  offset += 1;留神n为奇数时最两头元素须要独自解决，赋值count 别忘了开始int middle的用意

977，有序数组的平方排序 class Solution { public int[] sortedSquares(int[] a) { //每次往两侧找，取两侧最大的一个，放入队列中最初当成最大的 int left = 0; int right = a.length -1; int rail_ptr = a.length -1; int[] b = new int[a.length]; while(left <= right) { if (a[left]*a[left] > a[right]*a[right]) { b[rail_ptr] = a[left] * a[left]; rail_ptr--; left++; } else { b[rail_ptr] = a[right]*a[right]; rail_ptr--; right--; } } return b; }}209，长度最小的子序列办法：滑动窗口 class Solution { public int minSubArrayLen(int target, int[] a) { //i是后指针，j是前指针 //sum用来判断从0到i，这i+1个元素之和有没有达到target的根底条件 //达到之后，再缩小j，看区间能不能放大 //留神，这里的j是枯燥的， 比方i = i1 时，对应[j1,i1]是最小区间 //那么i = i2 > i1， [j1,i2]必然满足条件而且区间长度比[j1,i1]大1， //须要淘汰，前指针从j1+1开始，也就是测试区间从[j1+1,i1+1]开始 int minlen = Integer.MAX_VALUE; int jlen = Integer.MAX_VALUE; int sum = 0; int j = 0; for (int i = 0; i < a.length; i++) { sum += a[i]; while (sum >= target) { sum -= a[j]; jlen = i-j+1; minlen = Math.min(minlen, jlen); j++; } } //min通过批改，阐明找到满足target的区间；min未通过批改，阐明没找到 return minlen = (minlen == Integer.MAX_VALUE)? 0 : minlen; }}59，螺旋矩阵办法：找法则 ...

2022年12月31日，第十二届北京国内网络电影展在北京举办，“醉三皇”作为官网指定用酒品牌亮相闭幕式。北京国内网络电影展创建于2011年，前身是北京国内微电影节，至今已间断举办十一届，是以后最具影响力的国内顶级网络影展品牌。影展涵盖网络电影、网络剧、微电影、短视频、纪录片等网生内容，其最高荣誉为“光年杯”，被业内誉为网络电影界的“奥斯卡”。北京国内网络电影展坚守青年电影人的人文现实和互联网精力，保持以人民为创作核心，弘扬支流价值、彰显时代精神，以新时代美好生活的影像化表白和中华优良传统文化的艺术化转译为使命，致力以艺术+科技、翻新+网络多维伎俩，构建青年电影人的幻想平台和网络影视行业的内容聚合平台、人才赋能平台与我的项目孵化平台。影展举办工夫在每年12月底，品牌流动包含网络影展、年度论坛、创投大会、星耀红毯及年度优秀作品表彰盛典等。本次北京国内网络电影展闭幕式群星璀璨、泛滥影视界编剧、导演、演员、制片人等嘉宾应邀参加，他们是：巩汉林、陈国星、黄军、赵保乐、王劲松等等。“醉三皇”是2022北京国内网络电影展官网指定白酒赞助商，并且作为晚宴指定用酒，在闭幕式上与泛滥明星嘉宾一起亮相。“醉三皇”品牌开创于2017年，产自赤水河畔茅台古镇，以茅台镇特有的红缨子糯高梁与小麦作为酿酒原料，采纳贵州地区传统的“坤沙”酿酒工艺进行酿造。酿酒的整个生产周期为一年，酿造初步实现后还要储备四年。酿酒过程严格遵循古法酿造，端午踩曲，重阳投料，酿造中需九次蒸煮、八次发酵、七次取酒，经分型贮放，总共30道工序，165个工艺环节。美酒既满樽，一吟还一倾。落幕宴会之上，“醉三皇”酱香酒酒体呈微黄通明、酱香突出、优雅细腻、酒味醇厚饱满、回味悠长、空杯留香长久。“醉三皇”以匠心的酿造，舒心的口感，感动着在场嘉宾的味蕾，好电影配好酒，眼与胃均愉悦。尽管严格采纳了“坤沙”酿酒工艺，“醉三皇”酱香酒的价格却十分的亲民，且酿酒过程中采纳固态发酵工艺，相比液态发酵大大减少对身材和口腔的刺激感，是一款非常适合在家庭聚会中饮用的酱香酒，“孝顺前辈的食粮酒”是“醉三皇”礼品酒的外围定位。这次在第十二届北京国内网络电影展上亮相，品牌方也心愿更多人理解“醉三皇”礼品酒，并带给家人品味，共享团圆之乐。

前言回溯，就是无脑冲，碰壁之后就回撤一步持续搞，属于一种暴力解题的思路； 实际上也是如此，当咱们在遇到一些分类探讨的问题，无奈想到比拟精妙的解决方案，咱们第一工夫思考到的就是暴力枚举所有状况，而后再做解决，而 回溯 就是这样的一个暴力法 下一个 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剖析 ...

位运算根底：程序中所有的数载计算机内存中都是以二进制存储的，位运算就是间接对整数在内存中的二进制进行操作，因为间接在内存中进行操作，不须要转成十进制，因而处理速度十分快 常见位运算 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: ...

注释 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个最大元素剖析 ...

前言博主最近在刷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;};接下来咱们逐行剖析代码。 ...

数组操作的工夫复杂度Access：O(1)Search：O(n)Insert： 均匀O(n)，最好的状况下O(1)，也就是在数组尾部插入O(1)，最坏的状况下O(n)Delete；均匀O(n)，最好的状况下O(1)，也就是在数组尾部删除O(1)，最坏的状况下O(n) 167. 两数之和 II - 输出有序数组 (easy)给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递加顺序排列 ，请你从数组中找出满足相加之和等于指标数 target 的两个数。如果设这两个数别离是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。 以长度为 2 的整数数组 [index1, index2] 的模式返回这两个整数的下标 index1 和 index2。 你能够假如每个输出 只对应惟一的答案 ，而且你 不能够 重复使用雷同的元素。 你所设计的解决方案必须只应用常量级的额定空间。 示例 1： 输出：numbers = [2,7,11,15], target = 9输入：[1,2]解释：2 与 7 之和等于指标数 9 。因而 index1 = 1, index2 = 2 。返回 [1, 2] 。示例 2： 输出：numbers = [2,3,4], target = 6输入：[1,3]解释：2 与 4 之和等于指标数 6 。因而 index1 = 1, index2 = 3 。返回 [1, 3] 。示例 3： ...

前言常常会有人问，作为前端，你在理论工作中用到过哪些算法，而我答复个别是，树和位运算； 想想 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只呈现一次的数字 -- 所有题目都是线性工夫复杂度，空间复杂度都是常数级复杂度剖析如果题目看错是只有一个值呈现一次，其余都呈现两次，那么间接异或就能够得出后果；当初是有两个值只呈现一次，所以异或和失去的就是这两个值的异或和，所以须要将原数组拆解成两份 ...

前端就该用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}参考视频：传送门 ...

目录Stack的特点：先进后出（FILO）应用场景：十进制转2进制 函数调用堆栈js里没有栈，然而能够用数组模仿 42/2 42%2=021/2 21%2=110/2 10%2=05/2 5%2=12/2 2%2=01/2 1%2=1stack: [0,1,0,1,0,1]res: 1 0 1 0 1 0fn1(){ fn2()}fn2(){ fn3() }fn3(){}fn1()stack:[fn1,fn2,fn3]栈的工夫复杂度：入栈和出栈O(1)，查找O(n) 155. 最小栈 (easy)设计一个反对 push ，pop ，top 操作，并能在常数工夫内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。 示例 1: 输出：["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]] 输入：[null,null,null,null,-3,null,0,-2] 解释：MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); --> 返回 -3.minStack.pop();minStack.top(); --> 返回 0.minStack.getMin(); --> 返回 -2. 提醒： -231 <= val <= 231 - 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 104 次 ...

前言上一 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. 寻找反复数剖析 -- 双指针法（快慢指针） ...

队列的特点：先进先出（FIFO）队列的工夫复杂度：入队和出队O(1)，查找O(n)优先队列：priorityQueue，按优先级出队，实现 Heap(Binary,Fibonacci...)js里没有队列，然而能够用数组模仿 225. 用队列实现栈 (easy)请你仅应用两个队列实现一个后入先出（LIFO）的栈，并反对一般栈的全副四种操作（push、top、pop 和 empty）。 实现 MyStack 类： void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。 留神： 你只能应用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所应用的语言兴许不反对队列。 你能够应用 list （列表）或者 deque（双端队列）来模仿一个队列 , 只有是规范的队列操作即可。 示例： 输出：["MyStack", "push", "push", "top", "pop", "empty"][[], [1], [2], [], [], []]输入：[null, null, null, 2, 2, false] 解释：MyStack myStack = new MyStack();myStack.push(1);myStack.push(2);myStack.top(); // 返回 2myStack.pop(); // 返回 2myStack.empty(); // 返回 False ...

序章咱们把字符串、数组、正则、排序、递归归为简略算法。接下来系列里，将系列文章里将为大家逐个介绍。 字符串翻转字符串中的单词给定一个字符串，你须要反转字符串中每个单词的字符程序，同时仍保留空格和单词的初始程序。示例 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(' ')}; ...

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. 无效的括号 ...

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(); ...

84. 柱状图中最大的矩形 (hard)给定 n 个非负整数，用来示意柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，可能勾画进去的矩形的最大面积。 示例 1: 输出：heights = [2,1,5,6,2,3]输入：10解释：最大的矩形为图中红色区域，面积为 10示例 2： 输出： heights = [2,4]输入： 4 提醒： 1 <= heights.length <=1050 <= heights[i] <= 104 思路：筹备枯燥递增栈寄存数组下标，因为这样能够从栈顶找到右边第一个比本人小的下标，这样从以后下标登程到第一个比本人小的柱子的下标就是矩形面积的宽度，而后在乘以后柱子的高度就是面积，如果以后柱子大于栈顶的下标对应的柱子高度，就入栈，否则一直出栈，计算栈顶的柱子所能造成的矩形面积，而后更新最大矩形面积复杂度：工夫复杂度O(n)，n是heights的长度，数组里每个元素尽出栈一次。空间复杂度O(n)，栈空间最多为n动画过大，点击查看 js： const largestRectangleArea = (heights) => { let maxArea = 0 const stack = [] //枯燥递增栈 留神栈存的时下标 heights = [0, ...heights, 0] //在heights数组前后减少两个哨兵 用来清零枯燥递增栈里的元素 for (let i = 0; i < heights.length; i++) { //以后元素对应的高度小于栈顶元素对应的高度时 while (heights[i] < heights[stack[stack.length - 1]]) { const stackTopIndex = stack.pop() //出栈 maxArea = Math.max( //计算面积 并更新最大面积 maxArea, heights[stackTopIndex] * (i - stack[stack.length - 1] - 1)//高乘宽 ) } stack.push(i)//以后下标退出栈 } return maxArea}85. 最大矩形 (hard)给定一个仅蕴含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只蕴含 1 的最大矩形，并返回其面积。 ...

什么是树一种分层数据的形象模型。前端工作中常见的树包含：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 ...

对于二分题，其实就是设定一个两头值 mid, 而后通过这个值进行一个判断 check(mid)， 通过这个函数的返回值，判断将不可能的一半剪切掉； 在刷题的时候须要留神次要是两局部，check 函数的定义以及边界的抉择（等号的抉择，以及最初是 return left 还是 right） 这次次要是 LC 的二分专题，外面的简略题根本都是比拟显性的提醒了 check 函数的构建，比方说间接找出某个值，而难题个别都是 check 函数比拟难想的，这个时候就须要教训了； 狭义上只有是排好序（部分排序），只有是找某个值，大部分都能够思考用二分，这样复杂度能够升高很多； 对于边界，我的循环完结条件是 left <= right ， 因为如果要多记很多模板，怕会出问题，所以退出条件根本都按这个，而后无论是那种模块，都基于这个完结条件来判断，这样能够把问题膨胀都循环里的断定的 check 函数，多做了就会发现端倪； 而后对于退出之后 left 还是 right ，这个是具体问题具体分析；因为我的完结断定条件是 left<=right ，所以如果没用两头返回，那么必然存在 left === right 的时候，这个时候依据断定条件，就晓得 right 在 left 的后面，而到底是左迫近，还是右迫近，都比拟好判断了，因为这个时候曾经退出去了，left 和 right 所代表的 check 的状态也是不言而喻的，那么看题目要求什么，给什么即可； 对于二分，我感觉这个专题就根本足够了，简略居多，难题也有两个；如果是第一次学习二分，那么依照专栏的三个模板去记忆也 ok， 他人的教训终归是适宜他人本人，做题最重要是把握住本人的节奏，记忆本人最相熟的那个点，强行模拟他人反而落了下乘； 当然那个男人那么强，我的做题就是模拟的他，缓缓大佬的解法就是我本人的节奏了，毕竟模拟多了，其实就是本人的了，除了算法，其余的工程化学习也是一样的； 那么，周末高兴，下周开 dp 吧，毕竟这个听有意思的。 模板 1目标值是一个固定的 target，在二分过程中须要一直的判断，如果胜利就返回对应的值，否则间接返回失败的值返回值如果是向下取，返回 right，如果向上取，则返回 left，还有可能返回一个特定给的失败值；var search = function (fn, target) { let left = 最小值, right = 最大值; while (left <= right) { // 取 mid 值 const mid = ((right - left) >> 1) + left; //这里的 fn 可能是函数，也可能只是数组取值，反正就是能够获得一个值去跟 target 比拟 const temp = fn(mid); if (temp === target) return mid; if (temp < target) { left = mid + 1; } else { right = mid - 1; } } return 没有准确匹配后的值;};704. 二分查找var search = function (nums, target) { const len = nums.length; if (!len) return -1; let left = 0, right = len - 1; while (left <= right) { const mid = ((right - left) >> 1) + left; if (nums[mid] === target) return mid; if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1;};69. x 的平方根// 69. x 的平方根var mySqrt = function (x) { let left = 0, right = x; while (left <= right) { const mid = ((right - left) >> 1) + left; const sqrt = mid * mid; if (sqrt === x) return mid; if (sqrt < x) { left = mid + 1; } else { right = mid - 1; } } // 向下取整 return right;};374. 猜数字大小剖析 ...

什么是贪婪算法贪婪法，又称贪婪算法，贪心算法，在对问题求解时，总是做出在以后看来最好的抉择，冀望通过每个阶段的部分最优抉择达到全局最优，但后果不肯定最优 实用场景：简略的说，问题可能分解成子问题来解决，子问题的最优解能递推到最终问题的最优解，就能用贪婪算法的到最初的最优解，这种子问题最优解称为最优子结构 贪婪算法与动静布局的不同点在于它对每个子问题的解决方案都做出以后的最优抉择，不能回退，而动静布局会保留之前的运算后果，并依据之前的后果进行抉择，有回退的性能，贪婪是动静布局的理想化的状况。 621. 任务调度器 (medium)给你一个用字符数组 tasks 示意的 CPU 须要执行的工作列表。其中每个字母示意一种不同品种的工作。工作能够以任意程序执行，并且每个工作都能够在 1 个单位工夫内执行完。在任何一个单位工夫，CPU 能够实现一个工作，或者处于待命状态。 然而，两个 雷同品种 的工作之间必须有长度为整数 n 的冷却工夫，因而至多有间断 n 个单位工夫内 CPU 在执行不同的工作，或者在待命状态。 你须要计算实现所有工作所须要的 最短时间 。 示例 1： 输出：tasks = ["A","A","A","B","B","B"], n = 2输入：8解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B 在本示例中，两个雷同类型工作之间必须距离长度为 n = 2 的冷却工夫，而执行一个工作只须要一个单位工夫，所以两头呈现了（待命）状态。 示例 2： 输出：tasks = ["A","A","A","B","B","B"], n = 0输入：6解释：在这种状况下，任何大小为 6 的排列都能够满足要求，因为 n = 0["A","A","A","B","B","B"]["A","B","A","B","A","B"]["B","B","B","A","A","A"]...诸如此类示例 3： 输出：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2输入：16解释：一种可能的解决方案是： ...

简介文中所有题目均为精心筛选过的超高频题目，所以大家能够珍藏起来 适用人群针对有肯定数据结构根底(理解链表, 二叉树, 二叉堆, 递归)的基本概念,并对工夫空间复杂度有根本认知的。 食用指南将文中列出的每道题至多手写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、基本概念 树是计算机科学中常常用到的一种非线性数据结构，以分层的模式存储数据。二叉树是一种非凡的树结构，每个节点最多有两个子树，通常子树被称作“左子树”和“右子树”。 以上述图片为例，介绍二叉树相干的几个术语： 节点的度：节点领有子树的数量，图中节点 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。整个树的坡度就是其所有节点的坡度之和。 解题思路：在后序遍历的过程中，先计算左子树和值以及右子树和值，再计算以后节点的坡度，最初更新以后子树的和值。 ...

目录Trie树，即字典树，又称前缀树，是一种树形构造，典型利用是用于统计和排序大量的字符串（但不限于字符串），所以常常被搜索引擎用于文本词频统计。它的优先是，最大限度的缩小无谓的字符串比拟，进步查找效率。 Trie的核心思想是空间换工夫，利用字符串的公共前缀来升高查问工夫的开销，以达到提高效率的目标 根本性质 根节点不蕴含字符，除跟节点外每个节点都只蕴含一个字符从根节点到某一个节点，门路上通过的字符连接起来，为该节点对应的字符串每个节点的所有子节点蕴含的字符都不雷同<img src="https://xiaochen1024.com/20211118161003.png" alt="ds_8" style="zoom:50%;" /> 理论利用，例如搜寻 # 208. 实现 Trie (前缀树)(medium)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 ...

各类题的解决方案话不多说，零碎整顿下解题的一些算法和解决方案 二叉树二叉树大多应用递归的形式左右两个元素向下递归。比方： 计算二叉树最大深度 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 到指标额度所需的最小硬币数都列出来。 ...

1143. 最长公共子序列 (medium)给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不扭转字符的绝对程序的状况下删除某些字符（也能够不删除任何字符）后组成的新字符串。 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的 公共子序列 是这两个字符串所独特领有的子序列。 示例 1： 输出：text1 = "abcde", text2 = "ace" 输入：3 解释：最长公共子序列是 "ace" ，它的长度为 3 。示例 2： 输出：text1 = "abc", text2 = "abc"输入：3解释：最长公共子序列是 "abc" ，它的长度为 3 。示例 3： 输出：text1 = "abc", text2 = "def"输入：0解释：两个字符串没有公共子序列，返回 0 。 提醒： 1 <= text1.length, text2.length <= 1000text1 和 text2 仅由小写英文字符组成。 办法1:动静布局 ...

前言某个男人 动静布局,而我作为一个致力称为厨师界最会写算法的前端，总得刷上一部分题，有那么一点发现吧，当初咱们就来聊聊，菜鸡如我，发现了什么。 注释汇总这周学习的当初，我脑壳疼的慌，啥货色都想不到，然而为了不破本人每周都总结一下下的指标，只能水几句了； 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剖析 ...

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

73. 矩阵置零（ medium）给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请应用 原地 算法。 示例 1： 输出：matrix = [[1,1,1],[1,0,1],[1,1,1]]输入：[[1,0,1],[0,0,0],[1,0,1]]示例 2： 输出：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]输入：[[0,0,0,0],[0,4,5,0],[0,3,1,0]] 提醒： m == matrix.lengthn == matrix[0].length1 <= m, n <= 200-231 <= matrixi <= 231 - 1 进阶： 一个直观的解决方案是应用 O(mn) 的额定空间，但这并不是一个好的解决方案。一个简略的改良计划是应用 O(m + n) 的额定空间，但这依然不是最好的解决方案。你能想出一个仅应用常量空间的解决方案吗？ 思路:用两个变量标记第一行和第一列是否有0，接着循环一遍矩阵，如果遇见0，将和这个网格雷同的第一行和第一列的元素标记成0，在循环矩阵，如果以后网格对应的第一行和第一列是0，则将这个单元格置为0。最初如果第一列有0 ，则将这第一列全副置为0,如果第一行有0 ，则将这第一行全副置为0复杂度：工夫复杂度O(mn)，m、n为矩阵的行和列。空间复杂度O(1)js: var setZeroes = function(matrix) { const m = matrix.length, n = matrix[0].length; let flagCol0 = false, flagRow0 = false;//示意第一行和第一列有没有0 for (let i = 0; i < m; i++) {//寻找第一列是否存在0 if (matrix[i][0] === 0) { flagCol0 = true; } } for (let j = 0; j < n; j++) { if (matrix[0][j] === 0) { flagRow0 = true; } } for (let i = 1; i < m; i++) {//循环矩阵，如果遇见0，将和这个网格雷同的第一行和第一列的元素标记成0 for (let j = 1; j < n; j++) { if (matrix[i][j] === 0) { matrix[i][0] = matrix[0][j] = 0; } } } for (let i = 1; i < m; i++) {//循环矩阵，如果以后网格对应的第一行和第一列是0，则将这个单元格置为0 for (let j = 1; j < n; j++) { if (matrix[i][0] === 0 || matrix[0][j] === 0) { matrix[i][j] = 0; } } } if (flagCol0) {//如果第一列有0 ，则将这第一列全副置为0 for (let i = 0; i < m; i++) { matrix[i][0] = 0; } } if (flagRow0) {//如果第一行有0 ，则将这第一行全副置为0 for (let j = 0; j < n; j++) { matrix[0][j] = 0; } }};133. 克隆图 （medium）给你无向 连通 图中一个节点的援用，请你返回该图的 深拷贝（克隆）。 ...

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

首先须要理解链表的概念 先把 next 记录下来无论是插入，删除，还是翻转等等操作，先把 next 指针用长期变量保存起来，这能够解决 90% 重组链表中指向出错的问题， 如果不晓得什么时候须要用到守卫，那就都用类型守卫 emptyNode 是创立的一个空的节点，并将它连贯到 head 节点之前，无论链表进行任何操作， emptyNode 都指向最初的头节点，是一个很实用的小办法，如果不晓得什么时候用，什么时候不必，那就先都用起来吧； 其实在大部分时候，emptyNode 都是能用上，即使只是遍历查找值，用上作为第 0 个值，当要找第 k 个值的时候，也不须要再判空解决啊 头节点判空解决如果懒或者常常遗记看题目的给定条件，头节点判空都做起来，对于一些翻转题，还得将 head.next 也判断起来； 到纯熟之后，其实能够不做，然而用上最多就节约一段代码，也还好 画图，画图，画图遇事不决的时候，还是要画图，一步一步的连起来，总可能捋分明的，画图是链表的关键所在 链表的节点是保留在内存中的一个数据结构链表是一个特定的数据结构，在 JS 中能够体现为一个领有 val 和 next 属性的对象，所以遇到形如替换两个链表节点的时候，千万不能替换两个链表的 val 值，尽管 LC 有一些题是能够过，然而实际上是不合理的，而且一旦呈现这种思维，对于一些经典题 160. 相交链表 就会了解不了； 记住，链表是一个数据结构，不是一个值，能够类比成一个对象，替换链表比方不是简略替换值； 都是中等题这里选的都是依照 LC 炽热排序，中等难度的题，感觉纯链表学习做特地难没太大必要，毕竟我只是一个菜鸟，大佬们能够自由选择，一起 ，进大厂； 具体题解剑指 Offer 24. 反转链表剖析 留神爱护好下一个节点 next而后一直保护上一个节点和以后阶段，一直往后推即可var reverseList = function (head) { let prev = null; while (head) { const next = head.next; head.next = prev; prev = head; head = next; } return prev;};面试题 02.05. 链表求和剖析 ...

队列的特点：先进先出（FIFO）队列的工夫复杂度：入队和出队O(1)，查找O(n)优先队列：priorityQueue，按优先级出队，实现 Heap(Binary,Fibonacci...)js里没有队列，然而能够用数组模仿 347. 前 K 个高频元素 （medium）给你一个整数数组 nums 和一个整数 k ，请你返回其中呈现频率前 k 高的元素。你能够按 任意程序 返回答案。 示例 1: 输出: nums = [1,1,1,2,2,3], k = 2输入: [1,2]示例 2: 输出: nums = [1], k = 1输入: [1] 提醒： 1 <= nums.length <= 105k 的取值范畴是 [1, 数组中不雷同的元素的个数]题目数据保障答案惟一，换句话说，数组中前 k 个高频元素的汇合是惟一的 进阶：你所设计算法的工夫复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。 办法1:优先队列 思路：循环数组，退出小顶堆，当堆的size超过k时，出堆，循环实现之后，堆中所有的元素就是前k大的数字复杂度：工夫复杂度O(nlogk)，循环n次，每次堆的操作是O(logk)。空间复杂度O(k)，js： class Heap { constructor(comparator = (a, b) => a - b, data = []) { this.data = data; this.comparator = comparator;//比拟器 this.heapify();//堆化 } heapify() { if (this.size() < 2) return; for (let i = Math.floor(this.size()/2)-1; i >= 0; i--) { this.bubbleDown(i);//bubbleDown操作 } } peek() { if (this.size() === 0) return null; return this.data[0];//查看堆顶 } offer(value) { this.data.push(value);//退出数组 this.bubbleUp(this.size() - 1);//调整退出的元素在小顶堆中的地位 } poll() { if (this.size() === 0) { return null; } const result = this.data[0]; const last = this.data.pop(); if (this.size() !== 0) { this.data[0] = last;//替换第一个元素和最初一个元素 this.bubbleDown(0);//bubbleDown操作 } return result; } bubbleUp(index) { while (index > 0) { const parentIndex = (index - 1) >> 1;//父节点的地位 //如果以后元素比父节点的元素小，就替换以后节点和父节点的地位 if (this.comparator(this.data[index], this.data[parentIndex]) < 0) { this.swap(index, parentIndex);//替换本人和父节点的地位 index = parentIndex;//一直向上取父节点进行比拟 } else { break;//如果以后元素比父节点的元素大，不须要解决 } } } bubbleDown(index) { const lastIndex = this.size() - 1;//最初一个节点的地位 while (true) { const leftIndex = index * 2 + 1;//左节点的地位 const rightIndex = index * 2 + 2;//右节点的地位 let findIndex = index;//bubbleDown节点的地位 //找出左右节点中value小的节点 if ( leftIndex <= lastIndex && this.comparator(this.data[leftIndex], this.data[findIndex]) < 0 ) { findIndex = leftIndex; } if ( rightIndex <= lastIndex && this.comparator(this.data[rightIndex], this.data[findIndex]) < 0 ) { findIndex = rightIndex; } if (index !== findIndex) { this.swap(index, findIndex);//替换以后元素和左右节点中value小的 index = findIndex; } else { break; } } } swap(index1, index2) {//替换堆中两个元素的地位 [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]]; } size() { return this.data.length; }}var topKFrequent = function (nums, k) { const map = new Map(); for (const num of nums) {//统计频次 map.set(num, (map.get(num) || 0) + 1); } //创立小顶堆 const priorityQueue = new Heap((a, b) => a[1] - b[1]); //entry 是一个长度为2的数组，0地位存储key，1地位存储value for (const entry of map.entries()) { priorityQueue.offer(entry);//退出堆 if (priorityQueue.size() > k) {//堆的size超过k时，出堆 priorityQueue.poll(); } } const ret = []; for (let i = priorityQueue.size() - 1; i >= 0; i--) {//取出前k大的数 ret[i] = priorityQueue.poll()[0]; } return ret;};933. 最近的申请次数 (easy)写一个 RecentCounter 类来计算特定工夫范畴内最近的申请。 ...

首先须要理解链表的概念 先把 next 记录下来无论是插入，删除，还是翻转等等操作，先把 next 指针用长期变量保存起来，这能够解决 90% 重组链表中指向出错的问题， 如果不晓得什么时候须要用到守卫，那就都用类型守卫 emptyNode 是创立的一个空的节点，并将它连贯到 head 节点之前，无论链表进行任何操作， emptyNode 都指向最初的头节点，是一个很实用的小办法，如果不晓得什么时候用，什么时候不必，那就先都用起来吧； 其实在大部分时候，emptyNode 都是能用上，即使只是遍历查找值，用上作为第 0 个值，当要找第 k 个值的时候，也不须要再判空解决啊 头节点判空解决如果懒或者常常遗记看题目的给定条件，头节点判空都做起来，对于一些翻转题，还得将 head.next 也判断起来； 到纯熟之后，其实能够不做，然而用上最多就节约一段代码，也还好 画图，画图，画图遇事不决的时候，还是要画图，一步一步的连起来，总可能捋分明的，画图是链表的关键所在 链表的节点是保留在内存中的一个数据结构链表是一个特定的数据结构，在 JS 中能够体现为一个领有 val 和 next 属性的对象，所以遇到形如替换两个链表节点的时候，千万不能替换两个链表的 val 值，尽管 LC 有一些题是能够过，然而实际上是不合理的，而且一旦呈现这种思维，对于一些经典题 160. 相交链表 就会了解不了； 记住，链表是一个数据结构，不是一个值，能够类比成一个对象，替换链表比方不是简略替换值； 都是中等题这里选的都是依照 LC 炽热排序，中等难度的题，感觉纯链表学习做特地难没太大必要，毕竟我只是一个菜鸟，大佬们能够自由选择，一起 ，进大厂； 具体题解剑指 Offer 24. 反转链表剖析 留神爱护好下一个节点 next而后一直保护上一个节点和以后阶段，一直往后推即可var reverseList = function (head) { let prev = null; while (head) { const next = head.next; head.next = prev; prev = head; head = next; } return prev;};面试题 02.05. 链表求和剖析 ...

一、287. 寻找反复数给定一个蕴含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包含 1 和 n），可知至多存在一个反复的整数。假如只有一个反复的整数，找出这个反复的数。1、HashMap 在没有其它附加条件的状况下，读者第一工夫会想到通过 HashMap 来记录呈现过的数字，从而找到反复数： 上述实现代码的工夫复杂度和空间复杂度都为 O(n)，如果只容许应用 O(1) 的空间复杂度，该如何解决这道题目呢？ 2、Binary Search 这种条件下，最容易想到的就是通过两重循环暴力搜寻以后数字是否与前面的数字反复的办法来解决，然而这种计划的工夫复杂度为 O(n^2)，既然波及到了搜寻，就能够尝试通过二分搜索算法将工夫复杂度升高到 O(nlogn)。 依据后面的刷题教训，能够很容易地找出有序数组：1 到 n 的递增整数序列。 接下来的难点就是通过反复数的个性来确定下一轮搜寻区间是落在左半区间还是右半区间： 首先须要遍历 nums 数组，获取不大于以后两头数的数字的个数；如果个数大于两头数，那么下一轮搜寻区间落在左半区间；如果个数小于两头数，那么下一轮搜寻区间落在右半区间； 二、209. 长度最小的子数组给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的间断子数组。如果不存在符合条件的间断子数组，返回 0。1、Binary Search 这道题目中的有序数组不太好找，须要用到一个技巧：结构前缀和数组。 nums = [2, 3, 1, 2, 4, 3] # 前缀和 sums = [0, 2, 5, 6, 8, 12, 15] 从而上述示例中能够发现前缀和数组是一个有序数组，那么对于任意 i 到 j 的间断子数组之和，能够通过 sums[j+1] - sums[i] 求出。 ...

双指针一般指针：两指针同一方向或不同方向对撞指针：两指针相互聚拢快慢指针：一快一慢 141. 环形链表 (easy)给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中有某个节点，能够通过间断跟踪 next 指针再次达到，则链表中存在环。 为了示意给定链表中的环，评测零碎外部应用整数 pos 来示意链表尾连贯到链表中的地位（索引从 0 开始）。留神：pos 不作为参数进行传递 。仅仅是为了标识链表的理论状况。 如果链表中存在环 ，则返回 true 。 否则，返回 false 。 示例 1： 输出：head = [3,2,0,-4], pos = 1输入：true解释：链表中有一个环，其尾部连贯到第二个节点。示例 2： 输出：head = [1,2], pos = 0输入：true解释：链表中有一个环，其尾部连贯到第一个节点。示例 3： 输出：head = [1], pos = -1输入：false解释：链表中没有环。 提醒： 链表中节点的数目范畴是 [0, 104]-105 <= Node.val <= 105pos 为 -1 或者链表中的一个 无效索引 。 进阶：你能用 O(1)（即，常量）内存解决此问题吗？ 办法1.哈希表或set:动画过大，点击查看 思路：筹备一个map或者set，而后循环链表，每次遍历到一个节点的时候，判断以后节点是否在map中存在，如果不存在就把以后节点退出map中，如果存在的话阐明之前拜访过此节点，也就阐明了这条链表有环。复杂度剖析：工夫复杂度O(n)，n是链表的数量，最差的状况下每个节点都要遍历。空间复杂度O(n)，n是存储遍历过的节点的map或者setjs: var hasCycle = (head) => { let map = new Map(); while (head) { if (map.has(head)) return true;//如果以后节点在map中存在就阐明有环 map.set(head, true);//否则就退出map head = head.next;//迭代节点 } return false;//循环实现发现没有反复节点，阐明没环};办法2.快慢指针动画过大，点击查看 ...

一、前言 二分搜索算法自身并不是特地简单，外围点次要集中在： 有序数组：指的是一个递增或者递加的区间（非凡状况如：【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 必然落在左半区间； ...

前言学习算法的时候，总会有一些让人生畏的名词，比如动静布局，贪婪算法 等，听着就很难；而这一 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. 最大子序和剖析 -- 贪婪 ...

常见排序算法复杂度 n^2除nlogn在不同数据规模下的后果 常见排序算法算法可视化起源：http://visualgo.net/ 冒泡排序：工夫复杂度O(n^2) 比拟相邻元素，如果第一个比第二个大，则替换他们一轮下来，能够保障最初一个数是最大的执行n-1轮，就能够实现排序 function bubbleSort(arr) { var len = arr.length; for (var i = 0; i < len; i++) { for (var j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j+1]) { //相邻元素两两比照 var temp = arr[j+1]; //元素替换 arr[j+1] = arr[j]; arr[j] = temp; } } } return arr;}抉择排序：工夫复杂度O(n^2) 找到数组中的最小值，将它放在第一位接着找到第二小的值，将它放在第二位顺次类推，执行n-1轮 function selectionSort(arr) { var len = arr.length; var minIndex, temp; for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; j++) { if (arr[j] < arr[minIndex]) { //寻找最小的数 minIndex = j; //将最小数的索引保留 } } temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } return arr;}插入排序：工夫复杂度O(n^2) ...

一、链表链表（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 记录节点对象，如果呈现反复的节点则有环。 第二种解法是采纳双指针中的快慢指针技巧：当链表中存在环时，快指针必然能追上慢指针。