# 力扣笔试刷题笔记 **Repository Path**: jin-rongda/leetcode ## Basic Information - **Project Name**: 力扣笔试刷题笔记 - **Description**: 开始准备笔试题，刷题+记录，动脑子刷题 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2022-10-10 - **Last Updated**: 2025-08-11 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 11.盛水最多的容器6.12 给定一个长度为 `n` 的整数数组 `height` 。有 `n` 条垂线，第 `i` 条线的两个端点是 `(i, 0)` 和 `(i, height[i])` 。 找出其中的两条线，使得它们与 `x` 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 ``` 输入：[1,8,6,2,5,4,8,3,7] 输出：49 （height[1] && height[8]） ``` ## 1.双指针法 核心思想就是： 如果我们选择了两个index组成墙之后，如果把两个index向中间靠，有三种情况： * 比较矮的那个index向中间靠：盛的水可能会增加（index移动之后比另一个index位置高） * 比较高的index向中间靠：盛的水一定会减少 所以我们用left和right分别指向height数组的两头，每次只让比较矮的指针向中间靠，遍历一遍height来不断更新可能的最大值，最后返回 ~~~js /** * @param {number[]} height * @return {number} */ var maxArea = function(height) { let left = 0; let right = height.length - 1; let ans = 0; let currentContent; while(left < right) { /* 计算当前的容量并更新ans */ currentContent = Math.min(height[left], height[right]) * (right - left); ans = currentContent > ans ? currentContent : ans; if(height[left] === height[right]) { /* 如果两个位置一样高，那么两个index的内部还有可能出现更高的两个墙，但是这两个index不可能了，直接都向中间靠就行 */ left += 1; right -= 1; }else if(height[left] < height[right]) { left += 1; }else if(height[left] > height[right]) { right -= 1; } } return ans; }; ~~~ ## 2.双重for循环计算所有情况 # 15.三数之和6.12-7.30 给你一个整数数组 `nums` ，判断是否存在三元组 `[nums[i], nums[j], nums[k]]` 满足 `i != j`、`i != k` 且 `j != k` ，同时还满足 `nums[i] + nums[j] + nums[k] == 0` 。请 你返回所有和为 `0` 且不重复的三元组。 **注意：**答案中不可以包含重复的三元组。 ~~~javascript /** * @param {number[]} nums * @return {number[][]} */ var threeSum = function(nums) { // 针对某个很长的全零特例 if(nums.every((item) => item === 0)) return [[0, 0, 0]]; let result = []; let left; let right; let sum; nums = nums.sort((a, b) => a - b); for(let i = 0; i < nums.length; i ++) { left = i + 1; right = nums.length - 1; while(left < right) { sum = nums[i] + nums[left] + nums[right]; if(sum === 0) { result.push([nums[i], nums[left], nums[right]]); left ++; right --; } else if(sum > 0) { right --; } else if(sum < 0) { left ++; } } } // ------ 三元组数组如何根据元组内容去重 —— 利用Set，但是转Set前进行stringify（new Set可以接收数组字符串） ------ result = Array.from( new Set( result.map(JSON.stringify) ) ).map(JSON.parse); return result; }; ~~~ 在往`result`数组中放三元组时来者不拒，只要和等于0都放进来了，到后面再去重 核心思想可以理解为：给一个数组nums，**通过一次遍历，**找出所有和为xxx的两个数（所有满足条件的两元组集合） 1. 把nums进行排序，由小到大 2. 定义两个指针分别指向最左和最右，看两个指针位置的数之和与目标值的大小关系，比目标值小，左指针右移；比目标值大，右指针左移 **如何理解这两个指针的移动：**这两个指针指向的数为我们手头最大和最小的两个数，如果和小于目标，针对左指针的值来说，给他我们手头上最大的值都比目标小，所以左指针处的值加上一个数永远不可能得到目标，所以要放弃左指针。 三数之和基于上面两数之和的思想，我们先确定一个数，即最外层一个`for`，然后循环体内执行`while`寻找两数之和的逻辑即可 优化思路：在把找到的答案加入`result`数组之前进行判断是否重复，这样就不用最后去重。需要明确的是，查找两数之和的算法逻辑是能查找全部可能的（可能重复但不会遗漏），所以针对外层`for`的一个`i`，如果当前`i`与上一个相同，那么可以直接跳过当前`i`。 ~~~js // 数组中为引用类型，利用Set进行数组去重前进行JSON.stringify const arr = [{name: "jrd"}, {name: "jrd"}]; /* [ { "name": "jrd" }, { "name": "jrd" } ] */ new Set(arr.map(JSON.stringify)) // Set(1) {'{"name":"jrd"}'} ~~~ # 16.最接近的三数之和6.12 遍历思路完全一样，外层`for`，内层双指针。**双指针遍历，如果要找两数之和等于几，一定能找出所有满足的两数；在这里，寻找最接近某值的两数，遍历一次，遍历过程中记录过程值，一定能找到最值** 这里解释一下15，16题为什么选择外层`for`，内层双指针，而且左指针等于`i + 1`是正确的，因为双指针法寻找的目标是唯一的：两数之和等于某个值，指针的移动全部基于靠近这个目标。举个例子，下标为`3, 6, 7`为要找的最有优解，也就是说`i = 3`，如果`i`等于4时，还考虑`i`之前的元素，那么如果找到的最优解中包含`i`之前的元素`x`，那么一定在`i`等于`x`时就已经发现了这组解。所以左指针等于`i + 1`即可，是不会遗漏最优解的。 ~~~js /** * @param {number[]} nums * @param {number} target * @return {number} */ var threeSumClosest = function(nums, target) { let result; let right; let left; let minimumDiffAbs = Infinity; nums = nums.sort((a, b) => a - b); for(let i = 0; i < nums.length; i ++) { let twoSum = target - nums[i]; left = i + 1; right = nums.length - 1; while(left < right) { let diffAbs = Math.abs(twoSum - nums[left] - nums[right]); if(diffAbs < minimumDiffAbs) { minimumDiffAbs = diffAbs; result = nums[i] + nums[left] + nums[right]; } if(nums[left] + nums[right] < twoSum) { left ++; }else if(nums[left] + nums[right] > twoSum) { right --; } else { return nums[i] + nums[left] + nums[right]; } } } return result; }; ~~~ ```ts function threeSumClosest(nums: number[], target: number): number { let result = nums[0] + nums[1] + nums[2]; // 升序排列 const sortedNums = [...nums].sort((a, b) => a - b); for(let i = 0; i < sortedNums.length - 2; i++) { const firstNumber = sortedNums[i]; let leftPointer = i + 1; let rightPointer = sortedNums.length - 1; while(leftPointer < rightPointer) { const sum = firstNumber + sortedNums[leftPointer] + sortedNums[rightPointer]; const diff = sum - target; if(diff === 0) return target; if(Math.abs(diff) < Math.abs(result - target)) result = sum; if(diff < 0) { leftPointer++; } else { rightPointer--; } } } return result; }; ``` # 19.删除链表倒数第n个结点6.12 给你一个链表，删除链表的倒数第 `n` 个结点，并且返回链表的头结点。 ## 链表定位——快慢指针法 ~~~js /** * @param {ListNode} head * @param {number} n * @return {ListNode} */ var removeNthFromEnd = function(head, n) { // 首先创建一个链表结点指向head，快慢指针同时指向这个结点，至于为什么创建这个头，其实是倒推而来的：我们想利用指针的距离差来定位链表，那么快指针停下来的标志就是next为null，随便举个例子，链表长度为3，删除倒数第三个，那么快指针停下来时（指向最后一个结点），满指针应该指向head的前一个结点——这样方便删除第一个结点，所以推断得知：初始时快慢指针都指向head的前一个合适 let newHead = new ListNode(0, head), slow = fast = newHead; for(let i = 0;i < n; i ++) { fast = fast.next; } while (fast.next !== null) { fast = fast.next; slow = slow.next }; slow.next = slow.next.next; return newHead.next; }; ~~~ **2023，10，10最新理解：`for(let i = 0;i < n; i ++) `这里for循环n次其实就是让快指针领先慢指针n个位置，比如我们要找倒数第一个结点，那么快指针不需要领先慢指针，只需要两者同步即可，但是我们是删除倒数第n个结点，所以我们多循环一次，让慢指针停在要删除的结点前面。** ```ts /** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null { if(!head) return null; // 创建一个指向头节点的指针 let fastPointer = new ListNode(0, head); let slowPointer = new ListNode(0, head); for(let i = 0; i < n; i++) { fastPointer = fastPointer.next; } if(fastPointer.next === null && n === 1) return null; if(fastPointer.next === null) return head.next; while(fastPointer.next !== null) { fastPointer = fastPointer.next; slowPointer = slowPointer.next; } slowPointer.next = slowPointer.next.next; return head; }; ``` # 20.有效的括号（栈与队列）6.12 给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串 `s` ，判断字符串是否有效。 有效字符串需满足： 1. 左括号必须用相同类型的右括号闭合。 2. 左括号必须以正确的顺序闭合。 3. 每个右括号都有一个对应的相同类型的左括号。 **示例 1：** ``` 输入：s = "()" 输出：true ``` **示例 2：** ``` 输入：s = "()[]{}" 输出：true ``` **示例 3：** ``` 输入：s = "(]" 输出：false ``` **遍历整个字符串，遇到左括号入栈，遇到右括号`pop`栈顶元素，检查是否为对应的左括号，相当于所有的右括号是检查当前字符串是否出现了括号混乱的情况，但是此时检查还不完全，因为左括号可能比较多，比如`((()`，这样单纯依靠右括号检查不出来，所以最后判断栈是否为空，为空则说明既通过了右括号匹配检查，而且左右括号相等，是有效的括号。** ~~~js /** * @param {string} s * @return {boolean} */ var isValid = function(s) { const stack = []; for(let i = 0; i < s.length; i ++) { switch(s[i]) { case "(": case "[": case "{": stack.push(s[i]); break; case ")": if(stack.pop() !== '(') { return false; } break; case "]": if(stack.pop() !== '[') { return false; } break; case "}": if(stack.pop() !== '{') { return false; } break; } } if(stack.length === 0) { return true; } return false }; ~~~ # 32.给你一个只包含 `'('` 和 `')'` 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 2022.11.29字节实习一面 困难题，感觉技巧性偏多 示例： ``` 输入：s = "((())" 输出：4 解释：最长有效括号子串是 "(())" ``` 示例： ``` 输入：s = ")()())" 输出：4 解释：最长有效括号子串是 "()()" ``` 通过上面的示例可知：所谓有效括号，并不一定是一个整体，比如`((()))`这种，而是`()()`这种并列型的括号也算是有效括号，所以我们遍历找子有效括号的时候，不能用`)`的序号减去`(`的序号得到有效括号的长度，因为这样对于并列型括号是不对的，我们应该用`)`的序号减去**有效区间起点**，这里的区间就是指子有序括号，比如`")()())"`的中间的`()()`就是一个有效区间。 上面我们明确了题目的意思之后，难点就在于如何来记录这个区间了。 首先对于这种括号匹配的题目，毋庸置疑使用一个数组当作栈，然后用栈方法`pop`和`push`来进行操作。 首先确定核心逻辑：拿`)`的序号减去栈顶（区间起点）得到有效括号的长度，所以如何设计才能**让栈顶始终为区间起点**就是解决的关键。 * 因为要让栈顶为区间起点，所以我们设计了让`(`无脑进栈的情况下，遇见`)`就得让栈顶出栈，这样就可以把结合成功的括号排出栈外，保证栈顶序号为区间起点 * 初始化栈顶为`-1`，这样对于正常情况下的括号整体`(())`和并列括号`()()`，能满足`)`的序号减去`-1`就是区间长度 * 对于`)))`这种情况，我们应该修改区间起点，因为对于`)`我们的第一部逻辑就是`stack.pop();`，这样会导致栈空，所以判断，如果栈空，我们就让此时正在处理的`)`的序号入栈去做区间起点 * 对于`(((`这种情况，我们没必要刻意去处理，因为我们设计的逻辑就是栈顶为区间起点。对于`(`我们无脑入栈，我们取区间起点始终是在栈顶取，所以不影响 这里我的代码实现是： ~~~js /** * @param {string} s * @return {number} */ var longestValidParentheses = function(s) { let maxLength = 0; let temp = 0; let stack = []; stack.push(-1); for(let i = 0;i < s.length; i ++) { if(s[i] == "(") { stack.push(i); }else { stack.pop(); if(stack.length === 0) { stack.push(i); } /* 每次遇见`)`时会更新temp，更新temp时就判断是否超过了全局最大值 */ temp = i - stack[stack.length - 1]; if(temp > maxLength) { maxLength = temp; } } } return maxLength; }; ~~~ 说不上来学到了什么，感觉只学会了这个题目的这一种方法，这种方法设计能力需要锻炼 # 42.接雨水 ![image-20221130000119647](./image/42接雨水.png) 解法核心就是遍历整个数组，累计横向上每个位置接的雨水量 每一个柱子接的水 = min（左边最高的柱子， 右边最高的柱子） - 当前柱子的高度—简单理解就是木桶效应，这个柱子存多少水取决于两侧最矮的柱子多高 这个柱子能积水的前提是左边和右边都有比这个柱子高的柱子 按照上面的逻辑： ~~~js /** * @param {number[]} height * @return {number} */ var trap = function(height) { let sum = 0; for(let i = 0;i < height.length;i ++) { /* left 和 right 为布尔型变量，意思是判断height数组中左边和右边有没有比height[i]大的数 这里先用slice切割数组，然后用find方法判断数组中是否存在满足某种条件的数据 */ let left = height.slice(0, i).find((value) => value > height[i]); let right = height.slice(i+1, height.length).find((value) => value > height[i]); if(left && right) { /* Math.max搭配数组的拓展运算符实现寻找数组的最大值 */ sum += Math.min(Math.max(...height.slice(0, i)), Math.max(...height.slice(i+1, height.length))) - height[i]; } } return sum; }; ~~~ 优化思路：每个位置不去判断是否两侧有比当前位置高的柱子，而是都按照积水公式进行计算，如果两侧任意一侧没有比当前位置的高的柱子，那么这个位置的积水量的计算值为负数，所以求和时省略负数即可。 # 49.字母异位词分组 给你一个字符串数组，请你将 **字母异位词** 组合在一起。可以按任意顺序返回结果列表。 **字母异位词** 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。 **示例 1:** ``` 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]] ``` **示例 2:** ``` 输入: strs = [""] 输出: [[""]] ``` **示例 3:** ``` 输入: strs = ["a"] 输出: [["a"]] ``` 解决思路，同一组异位单词，将他们用`sort`函数排序后得到同一个字符串，所以我们遍历一遍`strs`数组，然后用一个`Map`记录排序字符串与对应的异位单词数组即可，最后再`for of`遍历一遍`Map`构造答案数组即可。 ~~~js /** * @param {string[]} strs * @return {string[][]} */ var groupAnagrams = function(strs) { const map = new Map(); for(let i = 0;i < strs.length; i ++) { let orderedStr = strs[i].split("").sort((a, b) => a > b ? -1 : 1).join(""); if(map.has(orderedStr)) { map.get(orderedStr).push(strs[i]); } else { map.set(orderedStr, [strs[i]]); } } const result = []; for(let value of map.values()) { result.push(value); } return result; }; ~~~ ```ts function groupAnagrams(strs: string[]): string[][] { // 原字符 => { sortedStr(排序后字符), count(原字符出现次数) } const sortedStrMap = new Map(); strs.forEach((str) => { const sortedStr = str.split('').sort((a, b) => a > b ? 1 : -1).join(''); const config = sortedStrMap.get(str); if(config) { sortedStrMap.set(str, {...config, count: config.count + 1}); } else { sortedStrMap.set(str, {sortedStr, count: 1}); } }) // 排序后字符 => 原字符集合 const originStrsMap = new Map>(); sortedStrMap.forEach((sortedConfig, origin) => { const { sortedStr, count } = sortedConfig; const curValues = originStrsMap.get(sortedStr); const newValue = getArray(count, origin); if(!curValues) { originStrsMap.set(sortedStr, [...newValue]); } else { originStrsMap.set(sortedStr, [...curValues, ...newValue]); } }) return Array.from(originStrsMap.values()); }; // 构造一个包含n个m的数组 function getArray(n, m) { const result = []; for(let i = 0; i < n; i++) { result.push(m); } return result; } ``` # 50.实现 pow(*x*, *n*)，即计算 `x` 的整数 `n` 次幂函数（即，`xn` ）。 ## 1.暴力（原创）： **暴力（时间超限），核心思路就是for循环n次，每次都乘个x**，最后返回的时候考虑负数幂次的情况。 ~~~js var myPow = function(x, n) { if(n === 0) return 1; let x_origin = x; //通过Math.abs获取n的绝对值 let absoluteN = Math.abs(n); for(let i = 1;i < absoluteN; i++ ) { x = x * x_origin; } return n > 0 ? x : 1 / x; }; ~~~ 时间复杂度：`O(n)` 空间复杂度：`0(1)` ## 2.分治法（快速幂）（题解）： ~~~js var myPow = function(x, n) { if(n === 1) return x; if(n === 0) return 1; if(n < 0) { x = 1/x; n = Math.abs(n); } //n为偶数 if(n % 2 === 0) { return myPow(x*x, n/2); } else { return x*myPow(x*x, Math.floor(n/2)); } }; ~~~ 时间复杂度：`0(logn)`，一个数的n次幂每次函数体执行都变成另一个数的n/2次幂，哪个数的幂这个数多大不重要，因为我们函数结束条件是n决定的，n足够小，函数才结束。所以经过logn次函数体执行，n就变成1了，也就是标志递归结束。然后每次函数体的执行，也就是这个规模缩小的过程，所花费的时间是单位1，执行logn次，所以时间复杂度就是`O(logn)` 空间复杂度：`0(logn)`：递归栈的深度。 方法收集： * `Math.abs(n)`：获取n的绝对值 * `Math.pow(n,m)`：获取n的m次幂 # 51.N皇后（回溯） 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 **n 皇后问题** 研究的是如何将 `n` 个皇后放置在 `n×n` 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 `n` ，返回所有不同的 **n 皇后问题** 的解决方案。 每一种解法包含一个不同的 **n 皇后问题** 的棋子放置方案，该方案中 `'Q'` 和 `'.'` 分别代表了皇后和空位。 ``` 输入：n = 4 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释：如上图所示，4 皇后问题存在两个不同的解法。 ``` **示例 2：** ``` 输入：n = 1 输出：[["Q"]] ``` ## 思路 主函数`solveNQueens`思路就是回溯法，根据皇后的攻击规则容易得知一行只放一个，所以`n * n`的棋盘放`n`个皇后问题转化为每行放一个皇后，皇后应该放在哪一列，**主函数思路看注释，两个辅助函数最重要的就是要时刻弄清楚row和col是对应实际意义的行和列还是对应的真实坐标，这个只要清晰就可以，辅助函数row和col确定清楚，函数体内就问题不大，然后主函数中传参时也注意转化即可。** ~~~js /** * @param {number} n * @return {string[][]} */ var solveNQueens = function(n) { let result = []; const backTrace = (currentRow, aPosition) => { // currentRow代表现在放了几行了，如果放了n行了，表示找到答案 if(currentRow === n) { result.push(aPosition); return; } // 处理一层的搜索逻辑 // i代表下一行的第i列 for(let i = 0;i < n; i ++) { // isPeace函数判断下一行放在第（i + 1）列会不会冲突，不冲突返回true if(isPeace(aPosition, i + 1, n)) { // 更新aPosition（一种位置），createRow即创建题目要求的'...Q'类型的行 let newPosition = [...aPosition, createRow(i + 1, n)]; // 递归调用 backTrace(currentRow + 1, newPosition) } } } // 执行 backTrace(0, []); // 返回 return result; }; // 列col和行row都按照从一开始的实际意义 const isPeace = (currentQueenPosition, col, n) => { let row = currentQueenPosition.length + 1; // 往左上进行验证 // 按照实际意义坐标先左上平移 let rowTemp = row - 1; let colTemp = col - 1; // 下面 - 1 为转真实坐标 while(colTemp - 1 >= 0 && rowTemp - 1 >= 0) { if(currentQueenPosition[rowTemp - 1][colTemp - 1] === "Q") { console.log("@@@"); return false; } rowTemp --; colTemp --; } // 往右上验证 // 先按照实际意义进行右上平移 rowTemp = row - 1; colTemp = col + 1; // - 1为转真实坐标 while(colTemp - 1 <= n && rowTemp - 1 >= 0) { if(currentQueenPosition[rowTemp - 1][colTemp - 1] === "Q") { return false; } rowTemp --; colTemp ++; } // 往上验证 // 先按照实际意义向上平移 rowTemp = row - 1; // colTemp 为真实坐标 colTemp = col - 1; while(rowTemp - 1 >= 0) { if(currentQueenPosition[rowTemp - 1][colTemp] === "Q") { return false; } rowTemp --; } return true; } const createRow = (col, n) => { let row = ''; for(let i = 0;i < n;i ++) { if(i === col - 1) { row += "Q"; }else { row += "."; } } return row; } ~~~ # 54.给你一个 `m` 行 `n` 列的矩阵 `matrix` ，请按照 **顺时针螺旋顺序** ，返回矩阵中的所有元素 ``` 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5] ``` ## 1.模拟法 题目要的数组就是我们由外到内转圈的遍历matrix出来的，那么我们就进行遍历： ### 两个技巧： * 构造标记（标记是否遍历过某位置）数组时，构造的标记数组`matrixCopy`比原数组大一圈，好处就是遍历`matrix`的时候，如果不大一圈，我们在走最外圈的时候走完一条边的判断条件就是数组不越界，而到了内圈标记数组才能发挥作用：判断条件根据标记数组得知有没有走过。但是我们如果标记数组构造的大一圈，就可以**从头到尾统一判断条件：根据标记数组看是否走过。**（注意标记数组和对应原数组位置坐标有一个单位的偏移即可） * 第二个技巧：while循环的结束条件怎么写： * 首先模拟走圈的时候，最外层有一个while循环，内层有四个while循环，对应一圈的四个边，不管是外层的while还是内层的while，写代码的时候我都并没有直接写出来while的结束条件，而都是`while(true)`，回头看来，这个操作属实可圈可点。 * 先说最外层的while，从结构来看，while的退出是内部满足了一定条件之后`break`，从逻辑来看，之后遍历完一条边，转换到下一条边的时候，如果没位置（matrixCopy为false）,就说明整个遍历完成。不管四个方向向哪走的时候，都有可能满足最外层的退出条件，所以总结：`while(true)`的结构内`break`可以让while退出的逻辑变得简单（不用高度凝练的写在while后面的括号里） * 内层的while退出，并不和外层一样很多种退出的场景，内层的while就是完成一定的任务：走完一条边。所以内层这里`while(true)`的目的和上面不同。内层while的结束条件就是下一个位置没发走了（`matrixCopy[x][y]`为`false`），while内部肯定是每次都沿着遍历的方向让坐标变化一个单位，但是这里我们不盲目每次都加一，因为如果每次都稳定加一，然后while内部判断条件是`matrixCopy[x][y]`为`true`，就会造成最后一下坐标变化之后虽然坐标不满足while的条件了，while推出了，但是相当于多加了一下，往后坐标也不能用了，就好比for循环，每次i++，然后最后一次不满足条件了，此时i就已经“走远了"。所以我们在while内部进行退出判断：先预先判断一下坐标移动之后的状态，然后再移动： ~~~js while(true) { ... //预先判断移动之后的状态是否合理再移动 if(matrixCopy[x-1][y]) { x -= 1; }else { break; } } ~~~ 代码： ~~~js /** * @param {number[][]} matrix * @return {number[]} */ var spiralOrder = function(matrix) { let ans = []; let matrixCopy = new Array(matrix.length + 2); for(let i = 0;i < matrixCopy.length; i ++) { matrixCopy[i] = new Array(matrix[0].length + 2); } for(let i = 0;i < matrixCopy.length;i ++) { for(let j = 0;j < matrixCopy[0].length;j ++) { //初始化标记数组 /* 根据边界条件特殊处理最外面一圈 最外面一圈设置为false，表示不能遍历 */ if((i == 0) || (i == matrixCopy.length-1) || (j == 0) || (j == matrixCopy[0].length-1)) { matrixCopy[i][j] = false; }else { matrixCopy[i][j] = true; } } } let x = 1; let y = 1; while(true) { //向右走 //判定位置总结while中判定，就会导致状态已经错误了,或者说目前的状态修改不是盲目每轮都修改，而是只有保证状态修改后正确再修改 while(true) { ans.push(matrix[x-1][y-1]); matrixCopy[x][y] = false; if(matrixCopy[x][y+1]) { y += 1; }else { break; } } //改变坐标位置为向下的起点 if(matrixCopy[x+1][y]) { x = x+1; }else {//如果没法转弯了，那就是遍历完成了 break; } //向下走 while(true) { ans.push(matrix[x-1][y-1]); matrixCopy[x][y] = false; if(matrixCopy[x+1][y]) { x += 1; }else { break; } } if(matrixCopy[x][y-1]) { y = y-1; }else { break; } while(true) { ans.push(matrix[x-1][y-1]); matrixCopy[x][y] = false; if(matrixCopy[x][y-1]) { y -= 1; }else { break; } } if(matrixCopy[x-1][y]) { x = x-1; }else { break; } //向上走 while(true) { ans.push(matrix[x-1][y-1]); matrixCopy[x][y] = false; if(matrixCopy[x-1][y]) { x -= 1; }else { break; } } if(matrixCopy[x][y+1]) { y = y+1; }else { break; } } return ans; }; ~~~ 时空复杂度都是：`O(mn)`，都是两层循环 # 55.跳跃游戏 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 **示例 1：** ``` 输入：nums = [2,3,1,1,4] 输出：true 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。 ``` 我觉着这个题最重要的就是悟到题目的核心：说白了，只要不被0卡住，就一定能到最后。 **如果被题目的标题（跳跃游戏）所误导，用模拟跳跃的方法去解题，那么事倍功半。** ## 1.贪心法—遍历更新 **对于每个位置，我们都跳最远，更新我们能到达的最远距离（贪心）**，遍历完之后，只需要比较我们能到达的最远距离是否够用即可。 ~~~js /** * @param {number[]} nums * @return {boolean} */ var canJump = function(nums) { let lengthMax = 0 for(let i = 0; i < nums.length-1; i ++) { /* 更新lengthMax有个前提条件: 目前的我们能到达的位置lengthMath要大于位置i */ if(lengthMax >= i && (i + nums[i]) > lengthMax) { lengthMax = i + nums[i]; } } if(lengthMax >= (nums.length-1)) { return true; } return false; }; ~~~ 时间复杂度：`O(n)`，遍历一次数组 空间复杂度：`O(1)` # 56.合并区间 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。 **示例 1：** ~~~ 输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. ~~~ ## 1.排序+遍历 首先先把intervals中的区间按照区间起点的升序排列目的是方便判断相邻区间是否有重叠，这样遍历intervals数组考察每一个区间，如果新考察的区间左边界小于结果集最后一个区间的右边界，说明存在重叠的可能，如果新考察的区间的右边界要大于结果集最后一个区间的右边界，即可更新结果集中的最后一个区间的右边界；如果没有重叠的可能，就直接把新考察的区间放进结果集。 ~~~js /** * @param {number[][]} intervals * @return {number[][]} */ var merge = function(intervals) { let ans = []; //升序排序 intervals.sort((a, b) => a[0] - b[0]); //循环开始前初始化:先放进去第一个元素，这样从第二考察区间开始就有比较的对象了 ans.push(intervals[0]); for(let i = 1;i < intervals.length; i ++) { //如果新考察的区间的起点小于结果集最后一个区间的终点，那么有可能重叠（还需要比较新考察区间的终点是否大于结果集最后一个区间的终点） if(intervals[i][0] <= ans[ans.length-1][1]) { if(intervals[i][1] > ans[ans.length-1][1]) {//如果存在重叠，那么更新结果集的区间的终点即可 ans[ans.length-1][1] = intervals[i][1]; } }else {//两个区间没有交集，不存在重叠的可能 ans.push(intervals[i]); } } return ans; }; ~~~ 时间复杂度：`O(nlog n)`，其中 n 为区间的数量。排序`O(nlog n)`>构造答案`0(n)` 空间复杂度：`O(nlog n)`，其中 nn 为区间的数量。**这里计算的是存储答案之外，使用的额外空间**。`O(nlog n)` 即为排序所需要的空间复杂度。 # 88.合并两个有序数组 给你两个按 **非递减顺序** 排列的整数数组 `nums1` 和 `nums2`，另有两个整数 `m` 和 `n` ，分别表示 `nums1` 和 `nums2` 中的元素数目。 请你 **合并** `nums2` 到 `nums1` 中，使合并后的数组同样按 **非递减顺序** 排列。 **注意：**最终，合并后数组不应由函数返回，而是存储在数组 `nums1` 中。为了应对这种情况，`nums1` 的初始长度为 `m + n`，其中前 `m` 个元素表示应合并的元素，后 `n` 个元素为 `0` ，应忽略。`nums2` 的长度为 `n` 。 **示例 1：** ``` 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。 ``` **示例 2：** ``` 输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。 ``` 分析：本身是一道简单题嘛，思路就没啥好总结的，比较清晰，明确，当然手段也可能比较多。看实例1就知道，我的思路是先把`nums1`中后面的`n`个`0`给删掉，然后挨个遍历`nums2`中的元素，把他们插入到`nums1`中正确的位置。 通过这个题搞清楚`Array.splice`api的用法就好，两种用法： * 删除：`splice(index, number)`，即算上下标为`index`的元素，然后删除`number`个，比如代码中`nums1.splice(m, n)`即删除了`nums1`最后的`n`个`0`。 * 添加：`splice(index, 0, newItem1, newItem2...)`，效果就是`splice`添加完成后数组中下标为`index`的位置为`newItem1`，然后添加之前下标为`index`的元素排在`newItem`插入进来的元素之后。 **摸清楚这个api的行为，删除操作与添加操作分开使用，这样可能会更清晰自己在做什么** ~~~js /** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ var merge = function(nums1, m, nums2, n) { nums1.splice(m, n); for(let i = 0; i < n; i ++) { let current = nums2[i]; // 将要插入nums1中的元素 let insertPosition = 0; // 要插入的位置 // 寻找正确的插入位置 // 这里考虑一种情况，current比nums1中的最大的元素（最后一个元素）还要大，这时候经过下面的while循环之后insertPosition是等于nums1.length的，这时候nums1.splice(insertPosition, 0, current)就相当于在nums1的最后添加元素。 while(current > nums1[insertPosition] && insertPosition < nums1.length) { insertPosition ++; } nums1.splice(insertPosition, 0, current); } }; ~~~ # [110. 平衡二叉树](https://leetcode.cn/problems/balanced-binary-tree/) 给定一个二叉树，判断它是否是高度平衡的二叉树。 本题中，一棵高度平衡二叉树定义为： > 一个二叉树*每个节点* 的左右两个子树的高度差的绝对值不超过 1 。 **需要计算二叉树高度或者深度的时候，千万不要回避，非常好算呐，一个递归就完事了。**然后这个题目本身，平衡二叉树要保证结点（二叉树）本身是平衡二叉树，自己的左右孩子也要是平衡二叉树。所以最后的return就明确怎么写了。 **** ~~~js /** * 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 {boolean} */ var isBalanced = function(root) { const getHeiht = (root) => { if(root === null) return 0; if(root.left === null && root.right === null) { return 1; } else { return 1 + Math.max(getHeiht(root.left), getHeiht(root.right)); } } if(root === null) return true; return Math.abs(getHeiht(root.left) - getHeiht(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); }; ~~~ # [129. 求根节点到叶节点数字之和](https://leetcode.cn/problems/sum-root-to-leaf-numbers/)（7.24字节提前批1面，a了） 给你一个二叉树的根节点 `root` ，树中每个节点都存放有一个 `0` 到 `9` 之间的数字。 每条从根节点到叶节点的路径都代表一个数字： - 例如，从根节点到叶节点的路径 `1 -> 2 -> 3` 表示数字 `123` 。 计算从根节点到叶节点生成的 **所有数字之和** 。 **叶节点** 是指没有子节点的节点。 ``` 输入：root = [1,2,3] 输出：25 解释： 从根到叶子节点路径 1->2 代表数字 12 从根到叶子节点路径 1->3 代表数字 13 因此，数字总和 = 12 + 13 = 25 ``` **思路就是dfs对二叉树进行遍历，在遍历的过程中对result进行累加（如果到了叶子结点就累加），最终返回result** ~~~js /** * 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 sumNumbers = function(root) { let result = 0; const dfs = (node, sum) => { let current = node.val; sum = (sum * 10 + current); if(node.left === null && node.right === null) { result += sum; } else { if(node.left !== null) dfs(node.left, sum); if(node.right !== null) dfs(node.right, sum); } } dfs(root, 0); return result; }; ~~~ # 146.LRU缓存 请你设计并实现一个满足 [LRU (最近最少使用) 缓存](https://baike.baidu.com/item/LRU) 约束的数据结构。 实现 `LRUCache` 类： - `LRUCache(int capacity)` 以 **正整数** 作为容量 `capacity` 初始化 LRU 缓存 - `int get(int key)` 如果关键字 `key` 存在于缓存中，则返回关键字的值，否则返回 `-1` 。 - `void put(int key, int value)` 如果关键字 `key` 已经存在，则变更其数据值 `value` ；如果不存在，则向缓存中插入该组 `key-value` 。如果插入操作导致关键字数量超过 `capacity` ，则应该 **逐出** 最久未使用的关键字。 函数 `get` 和 `put` 必须以 `O(1)` 的平均时间复杂度运行。 **示例：** ``` 输入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4] 解释 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4 ``` ## 完全Map模拟 * `Map.set`放入`Map`结构中的`(key, value)`其实是有顺序的，我们用`Map.keys().next().value`即可获取最早放入`Map`中的**键**（`Map.keys()`方法获取迭代器，`Map.keys().next()`迭代器的`next`方法获取一个具体的对象，包含`value`与`done`属性，`value`的值即为最早放入集合中的键值对的键）： ~~~js const map = new Map() map.set("xhr", 456); // Map(1) {'xhr' => 456} map.set("jrd", 123); // Map(2) {'xhr' => 456, 'jrd' => 123} map.keys() // MapIterator {'xhr', 'jrd'} —— 迭代器对象 map.keys().next() // {value: 'xhr', done: false} —— 迭代器对象调用next方法获取具体的迭代器元素（一个迭代器元素就对应了一个map中的元素） ~~~ * 剩下的就是利用map去按照要求模拟即可： * `get`一个元素时先删了再重新放进去，这样相当于刷新了最近使用时间 * `put`元素时朝map里普通放入就行了（题目要求放入一个重复的key时，更新value，这些都按要求来写就行）。主要是关于`capacity`的维护问题，`Map`也帮我们解决了——`Map.size`属性返回map的大小，所以不用我们维护动态的`capacity`，`capacity`初始化时存放一个静态容量即可，然后如果超出容量，直接`this.map.delete(this.map.keys().next().value);`删除第一个元素（最久未使用的元素）即可。 ~~~js /** * @param {number} capacity */ var LRUCache = function(capacity) { this.map = new Map(); this.capacity = capacity; }; LRUCache.prototype.get = function(key) { if(this.map.has(key)) { const value = this.map.get(key); this.map.delete(key); this.map.set(key, value); return value; } return -1; }; /** * @param {number} key * @param {number} value * @return {void} */ LRUCache.prototype.put = function(key, value) { if(this.map.has(key)) { this.map.delete(key); } this.map.set(key, value); if(this.map.size > this.capacity) { this.map.delete(this.map.keys().next().value); } }; /** * Your LRUCache object will be instantiated and called as such: * var obj = new LRUCache(capacity) * var param_1 = obj.get(key) * obj.put(key,value) */ ~~~ ~~~ts // 第二题：LRU缓存（中等题） // 题目：设计和实现一个LRU（最近最少使用）缓存机制，要求： // 支持get和put操作 // 时间复杂度O(1) // 当缓存容量满时，删除最久未使用的数据 // 要求：请用TypeScript实现，并分析空间复杂度 class LRU { // ts亮点：通过在constructor参数列表中添加访问修饰符，来省略this.xxx = xxx的赋值操作 constructor(private capacity: number, private cache: Map = new Map()) {} // 提高get target的优先级 & 返回get value get(key: string) { const val = this.cache.get(key); if (!val) return null; this.cache.delete(key); this.cache.set(key, val); return val; } // (如果key存在: 提高target优先级 & set覆盖value； 如果key不存在: set即可) & 处理容量问题—超出就删除最久未使用的 put(key: string, val: unknown) { if (this.cache.has(key)) { this.cache.delete(key); } this.cache.set(key, val); if (this.cache.size > this.capacity) { // 先通过map.keys()获取所有key的迭代器，所谓迭代器（{ next: () => {value, done} }），就是有一个next方法，调用就返回{value, done}对象。 const targetKey = this.cache.keys().next().value as string; this.cache.delete(targetKey); } } } const LRUInstance = new LRU(2); LRUInstance.put('ONE', 1); LRUInstance.put('ONE', 2); LRUInstance.put('TWO', 2); // console.log(LRUInstance.get('ONE')); LRUInstance.put('THREE', 3); console.log(LRUInstance.get('ONE')); ~~~ # 150.逆波兰表达式求值（栈与队列、栈） 给你一个字符串数组 `tokens` ，表示一个根据 [逆波兰表示法](https://baike.baidu.com/item/逆波兰式/128437) 表示的算术表达式。 请你计算该表达式。返回一个表示表达式值的整数。 **注意：** - 有效的算符为 `'+'`、`'-'`、`'*'` 和 `'/'` 。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。 - 两个整数之间的除法总是 **向零截断** 。 - 表达式中不含除零运算。 - 输入是一个根据逆波兰表示法表示的算术表达式。 - 答案及所有中间计算结果可以用 **32 位** 整数表示。 **示例 1：** ``` 输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9 ``` **示例 2：** ``` 输入：tokens = ["4","13","5","/","+"] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6 ``` 代码注意点： 1. 用栈可以很简单的模拟逆波兰式的计算，遇见数字就入栈，遇见运算符就出栈两个元素，然后把运算结果放入栈中继续运算即可，最后栈的唯一元素就是最终的运算结果。 2. **向零截断，为了防止负数情况，就不能用`Math.floor`或者`Math.ceil`了，用`parseInt`即可** 3. 除法计算和减法计算对操作数的顺序有要求，注意一下 ~~~js /** * @param {string[]} tokens * @return {number} */ var evalRPN = function(tokens) { const stack = []; let left; let right; for(let i = 0; i < tokens.length; i ++) { switch(tokens[i]) { case "+": stack.push(stack.pop() + stack.pop()); break; case "-": right = stack.pop(); left = stack.pop(); stack.push(left - right); break; case "*": stack.push(stack.pop() * stack.pop()); break; case "/": right = stack.pop(); left = stack.pop(); stack.push(parseInt(left / right)); break; default: stack.push(parseInt(tokens[i])); } } return stack[0]; }; ~~~ # 200.岛屿的数量 给你一个由 `'1'`（陆地）和 `'0'`（水）组成的的二维网格，请你计算网格中岛屿的数量。 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外，你可以假设该网格的四条边均被水包围。 **示例 1：** ``` 输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1 ``` **示例 2：** ``` 输入：grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 输出：3 ``` ## 1.沉岛法 我们遍历整个地图，如果遇见了`"1"`，我们就算遇见了一个岛屿，岛屿数量＋1，但是我们在继续遍历下一个位置之前，需要把与这个位置相连的陆地都变成`"0"`，也就是所谓的沉岛 ~~~js /** * @param {character[][]} grid * @return {number} */ var numIslands = function(grid) { let ans = 0; for(let i = 0;i < grid.length; i ++) { for(let j = 0;j < grid[0].length;j ++) { if(grid[i][j] === "1") { ans ++; turnZero(i, j, grid); } } } return ans; }; function turnZero(x, y, grid) { if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] === '0') return; grid[x][y] = "0"; turnZero(x - 1, y, grid); turnZero(x + 1, y, grid); turnZero(x, y - 1, grid); turnZero(x, y + 1, grid); } ~~~ # 203.移除链表元素（链表、添加虚拟头节点以统一操作、指针遍历）6.12 给你一个链表的头节点 `head` 和一个整数 `val` ，请你删除链表中所有满足 `Node.val == val` 的节点，并返回 **新的头节点** 。 **示例 1：** ``` 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5] ``` **示例 2：** ``` 输入：head = [], val = 1 输出：[] ``` **示例 3：** ``` 输入：head = [7,7,7,7], val = 7 输出：[] ``` ~~~js /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @param {number} val * @return {ListNode} */ var removeElements = function(head, val) { // 创建一个虚拟头节点，这样可以统一操作，统一第一个节点与其他节点。最后返回也是直接返回virtualHead.next const virtualHead = new ListNode(0, head); // 创建一个pointer指针用于遍历链表，遍历变量统一为pointer.next let pointer = virtualHead; while(pointer.next != null) { // 拥有虚拟头节点，遍历变量统一成了pointer.next if(pointer.next.val === val) { // 删除pointer.next pointer.next = pointer.next.next; } else { // 移动指针 pointer = pointer.next; } } // 返回的是从未变过的链表头virtualHead.next（pointer变量就是创建出来的遍历工具） return virtualHead.next; }; ~~~ # 225.用队列实现栈（栈与队列） ~~~js var MyStack = function() { this.queue = []; }; /** * @param {number} x * @return {void} */ MyStack.prototype.push = function(x) { this.queue.push(x); }; /** * @return {number} */ MyStack.prototype.pop = function() { for(let i = 0; i < this.queue.length - 1; i ++) { this.queue.push(this.queue.shift()); } return this.queue.shift(); }; /** * @return {number} */ MyStack.prototype.top = function() { return this.queue[this.queue.length - 1]; }; /** * @return {boolean} */ MyStack.prototype.empty = function() { return this.queue.length === 0; }; /** * Your MyStack object will be instantiated and called as such: * var obj = new MyStack() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.top() * var param_4 = obj.empty() */ ~~~ 用一个队列即可模拟栈，栈与队列`push`的行为都一样，增加元素就`push`，但是出元素时，我们要用我们的队列的`shift`方法弹出队列的最后一个（队尾）元素，这就需要我们进行一个循环，把队头除了最后一个元素之外的所有元素都依次加入队尾即可。 # 232.用栈实现队列（栈与队列） ~~~js var MyQueue = function() { this.inStack = []; this.outStack = []; }; /** * @param {number} x * @return {void} */ MyQueue.prototype.push = function(x) { while(this.outStack.length !== 0) { this.inStack.push(this.outStack.pop()); } this.inStack.push(x); }; /** * @return {number} */ MyQueue.prototype.pop = function() { while(this.inStack.length !== 0) { this.outStack.push(this.inStack.pop()); } return this.outStack.pop(); }; /** * @return {number} */ MyQueue.prototype.peek = function() { while(this.inStack.length !== 0) { this.outStack.push(this.inStack.pop()); } return this.outStack[this.outStack.length - 1]; }; /** * @return {boolean} */ MyQueue.prototype.empty = function() { return this.outStack.length === 0 && this.inStack.length === 0; }; /** * Your MyQueue object will be instantiated and called as such: * var obj = new MyQueue() * obj.push(x) * var param_2 = obj.pop() * var param_3 = obj.peek() * var param_4 = obj.empty() */ ~~~ 用两个栈模拟队列，只需要出队列的时候把入栈元素依次移动到出栈里，然后用出栈实现出队列；同理如队列用入栈实现，也需要把元素全移动到入栈中。 # 239.滑动窗口最大值（正解是单调队列） 给你一个整数数组 `nums`，有一个大小为 `k` 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 `k` 个数字。滑动窗口每次只向右移动一位。 返回 *滑动窗口中的最大值* 。 **示例 1：** ``` 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 ``` **示例 2：** ``` 输入：nums = [1], k = 1 输出：[1] ``` js的api这么强大，为啥要单调队列啊，但是下面的代码超时... ~~~js /** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSlidingWindow = function(nums, k) { let ans = []; for(let i = 0; i <= nums.length - k; i ++) { ans.push(Math.max(...nums.slice(i, i + k))); } return ans; }; ~~~ # 347.前k个高频元素（奇技淫巧、自创哈希——根据value排序最后拿key） 给你一个整数数组 `nums` 和一个整数 `k` ，请你返回其中出现频率前 `k` 高的元素。你可以按 **任意顺序** 返回答案。 **示例 1:** ``` 输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2] ``` **示例 2:** ``` 输入: nums = [1], k = 1 输出: [1] ``` **用对象`{}`来代替`Map`，因为对象可以依据`value`进行排序，而`map`不可以，通过`Object.keys`拿到`keysArr`，通过`sort`函数拿着`value`值排序即可。最后截取我们想要的`key`** ~~~js var topKFrequent = function(nums, k) { let hash = {} nums.forEach(num => { hash[num] ? hash[num]+=1 : hash[num] = 1; }) return Object.keys(hash).sort((key1,key2) => hash[key2] - hash[key1]).slice(0,k) }; ~~~ **2023.10.10最新理解：map咋就不能根据value排序了...`Array.from(map)`轻松打破map与数组之间的障壁：** ~~~js /** * @param {number[]} nums * @param {number} k * @return {number[]} */ var topKFrequent = function(nums, k) { let map = new Map(); for(let i = 0; i < nums.length; i ++) { if(map.has(nums[i])) { map.set(nums[i], map.get(nums[i]) + 1); } else { map.set(nums[i], 1); } } return Array.from(map).sort((a, b) => b[1] - a[1]).map((item) => item[0]).slice(0, k); }; ~~~ # [692. 前K个高频单词](https://leetcode.cn/problems/top-k-frequent-words/)（方法同347） 给定一个单词列表 `words` 和一个整数 `k` ，返回前 `k` 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， **按字典顺序** 排序。 **示例 1：** ``` 输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2 输出: ["i", "love"] 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。 注意，按字母顺序 "i" 在 "love" 之前。 ``` **示例 2：** ``` 输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4 输出: ["the", "is", "sunny", "day"] 解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词， 出现次数依次为 4, 3, 2 和 1 次。 ``` 思路与代码基本与347一模一样，只是有个细节，如果出现次数相同的单词，需要按照字典序进行排序，所以我们只需要稍微修改一下排序的逻辑即可：优先根据出现次数排序，如果次数相等则根据字典序排列两个字符串。 ~~~js /** * @param {string[]} words * @param {number} k * @return {string[]} */ var topKFrequent = function(words, k) { let keyToTimes = {}; for(let i = 0; i < words.length; i ++) { keyToTimes[words[i]] ? keyToTimes[words[i]] += 1 : keyToTimes[words[i]] = 1; } return Object.keys(keyToTimes).sort((key1, key2) => { if(keyToTimes[key2] - keyToTimes[key1] !== 0) { return keyToTimes[key2] - keyToTimes[key1]; } else { return key1 < key2 ? -1 : 1; } }).slice(0, k); }; ~~~ # 518 -> 377.组合总和 Ⅳ 给你一个由 **不同** 整数组成的数组 `nums` ，和一个目标整数 `target` 。请你从 `nums` 中找出并返回总和为 `target` 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 **示例 1：** ``` 输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。 ``` **示例 2：** ``` 输入：nums = [9], target = 3 输出：0 ``` **说白了就是求完全背包之装满背包的排列数**，由518的分析直接秒杀： ~~~js /** * @param {number[]} nums * @param {number} target * @return {number} */ var combinationSum4 = function(nums, target) { const dp = new Array(target + 1).fill(0); dp[0] = 1; for(let j = 0; j <= target; j ++) { for(let i = 0; i < nums.length; i ++) { if(j - nums[i] >= 0) { dp[j] += dp[j - nums[i]]; } } } return dp[dp.length - 1]; }; ~~~ # 494.目标和（0-1背包变式、动态规划、装满背包有多少种组合、详细分析） 给你一个整数数组 `nums` 和一个整数 `target` 。 向数组中的每个整数前添加 `'+'` 或 `'-'` ，然后串联起所有整数，可以构造一个 **表达式** ： - 例如，`nums = [2, 1]` ，可以在 `2` 之前添加 `'+'` ，在 `1` 之前添加 `'-'` ，然后串联起来得到表达式 `"+2-1"` 。 返回可以通过上述方法构造的、运算结果等于 `target` 的不同 **表达式** 的数目。 **示例 1：** ``` 输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3 ``` **示例 2：** ``` 输入：nums = [1], target = 1 输出：1 ``` 问题分析： **（用背包去装正数）** 其实就是我们给`nums`数组中的数决定正负，然后判断符合标准的有多少种可能。假设`nums`数组中所有数的和为`sum`，然后我们计算一下正数的和（也就是我们想要装满的背包的大小，即`bagValueSize`）：`bagValueSize - (sum - bagValueSize) = target`（正数减去负数等于`target`），这样我们就计算出了`bagValueSize`，问题转换为**我们恰好装满`bagValueSize`大小的背包有多少种装法，自然nums数组中的每一项都是物品，其价值与体积相同。** 定义`dp`数组的含义：（用前`i`件物品）`dp[j]`即代表装满容量为`j`的背包有`dp[j]`种装法 递推公式：`dp[j] = ∑(i = 0 -> i = nums.length - 1)dp[j - nums[i]]`，举个例子理解一下，求`dp[5]`即求（用`nums`数组中的物品）装满容量为5的背包有多种装法。如果我们有重量（价值）为`1`的物品，要想装满容量为5的背包，基于这个物品就相当于要装满容量为4的背包即可，同理如果我们有重量为3的物品，基于这个物品要想装满容量为5的背包就相当于要装满容量为2的背包。所以针对`nums`数组中的每一个数，都可以给`dp[j]`提供一些“组成”，但是我们又不能直接计算出来`dp[j]`，因为其实这里隐藏了一个信息是`dp[j]`是针对`i = nums.length - 1`，即物品要包含所有的物品，所以我们要外层`i`遍历物品数量，对于这个`i`正确的理解就是给所有的`dp[j]`都加上一个数，这个数就是针对`nums[i]`这个物品给`dp[j]`提供的装满背包的方法数，直到算到最后一个`i`，这时候内层遍历`j`时计算出来的每一个`dp[j]`才是正确的、最终的`dp[j]`，因为这时候`dp[j] += dp[j - nums[i]]; `加上这个`dp[j - nums[i]]`才算是把最后一个物品所提供的可能加进`dp[j]`去。 然后`dp[j]`所依赖的是`j`比较小的`dp`值，为了保证计算`dp[j]`时用到数据的正确性，所以我们内层`for`倒序遍历。 所以`dp`数组的计算过程在代码中的实现如下： ~~~js for(let i = 0; i < nums.length; i ++) { for(let j = bagValueSize; j - nums[i] >= 0; j --) { dp[j] += dp[j - nums[i]]; } } ~~~ 但是我们需要初始化一开始的`dp[0]`，究竟是`0`还是啥，这个不能凭感觉的，举个具体的简单的例子，然后看看真实场景下`dp[0]`初始化为多少正确就初始化为多少。 举个例子，第一个物品即`nums[0]`为1，然后我们第一层`for`的`i = 0`，即计算物品集合为只有第一个物品的`dp[j]`，然后我们计算`dp[1]`，也就是我们的背包容量为1，按照我们的递推公式`dp[1] += (dp[1 - nums[0]] = dp[0])`，因为我们知道`dp[1]`等于1，只有放进去第一个物品这个唯一的可能，所以推导得知，（为了符合递推公式的计算逻辑）我们应该把`dp[0]`初始化为`1`。 最终题解代码： ~~~js /** * @param {number[]} nums * @param {number} target * @return {number} */ var findTargetSumWays = function(nums, target) { const bagValueSize = (target + nums.reduce((previous, current) => { return previous + current; }, 0)) / 2 if(bagValueSize % 1 !== 0) return 0; if(bagValueSize < 0) return 0; const dp = new Array(bagValueSize + 1).fill(0); // dp数组初始化 dp[0] = 1; // 计算dp数组 for(let i = 0; i < nums.length; i ++) { for(let j = bagValueSize; j - nums[i] >= 0; j --) { dp[j] += dp[j - nums[i]]; } } return dp[dp.length - 1]; }; ~~~ ![](image/装满背包有几种方式.jpg) # 504.进制转换——七进制数 给定一个整数 `num`，将其转化为 **7 进制**，并以字符串形式输出。 ~~~js /** * @param {number} num * @return {string} */ var convertToBase7 = function(num) { if(num === 0) return "0"; /* 我们的核心逻辑只处理num为正数的情况，所以我们先记录一下正负，如果是负数最后加个"-" */ let isNegative = num < 0 ? true : false; num = Math.abs(num); /* 核心逻辑：ans字符串的逐位构造 */ let ans = ''; while(num > 0) { /* 模7直接得到最低位 */ let last = num % 7; ans = last + ans; // 构造ans /* num更新：减去最低位然后除7 */ num -= last; num /= 7; } return isNegative ? ('-' + ans) : ans; }; ~~~ # 300 -> 674.最长连续递增子序列的长度（动态规划、子序列问题） 给定一个未经排序的整数数组，找到最长且 **连续递增的子序列**，并返回该序列的长度。 **连续递增的子序列** 可以由两个下标 `l` 和 `r`（`l < r`）确定，如果对于每个 `l <= i < r`，都有 `nums[i] < nums[i + 1]` ，那么子序列 `[nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]` 就是连续递增子序列。 **示例 1：** ``` 输入：nums = [1,3,5,4,7] 输出：3 解释：最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 ``` **示例 2：** ``` 输入：nums = [2,2,2,2,2] 输出：1 解释：最长连续递增序列是 [2], 长度为1。 ``` ~~~js /** * @param {number[]} nums * @return {number} */ var findLengthOfLCIS = function(nums) { let ans = 1; // dp数组含义: dp[i]表示以nums[i]结尾的最长连续子序列长度为dp[i] // dp数组初始化: dp[0] = 1，即以下标为0的元素结尾的最长递增子序列长度为1（本身长度就为1） const dp = new Array(nums.length).fill(1); for(let i = 1; i < nums.length; i ++) { // i表示正在计算dp[i] if(nums[i] > nums[i - 1]) { // nums[i] > nums[i - 1]说明以nums[i - 1]结尾的递增子序列加上第i个元素仍然满足递增子序列，所以dp[i] = dp[i - 1] + 1 dp[i] = dp[i - 1] + 1; if(dp[i] > ans) { ans = dp[i]; } } } return ans; }; ~~~ # [796. 旋转字符串](https://leetcode.cn/problems/rotate-string/) 给定两个字符串, `s` 和 `goal`。如果在若干次旋转操作之后，`s` 能变成 `goal` ，那么返回 `true` 。 `s` 的 **旋转操作** 就是将 `s` 最左边的字符移动到最右边。 - 例如, 若 `s = 'abcde'`，在旋转一次之后结果就是`'bcdea'` 。 **没啥好说的，纯纯简单题。遍历每个可以拆分的位置即可，所以是len + 1** ~~~js /** * @param {string} s * @param {string} goal * @return {boolean} */ var rotateString = function(s, goal) { let len = s.length; // .a.b.c. for(let i = 0; i < len + 1; i ++) { let result = s.slice(i) + s.slice(0, i); if(result === goal) return true; } return false; }; ~~~ # 1047.删除字符串中的所有相邻重复项（栈与队列、栈） 给出由小写字母组成的字符串 `S`，**重复项删除操作**会选择两个相邻且相同的字母，并删除它们。 在 S 上反复执行重复项删除操作，直到无法继续删除。 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。 **示例：** ``` 输入："abbaca" 输出："ca" 解释： 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。 ``` **这种相邻消除的场景，优先考虑一下栈。** ~~~js /** * @param {string} s * @return {string} */ var removeDuplicates = function(s) { const stack = []; stack.push(s[0]); // 先放进去一个，为下面的for循环逻辑构造一个初始结构 if(s.length === 1) return s; for(let i = 1; i < s.length; i ++) { if(s[i] === stack[stack.length - 1]) { stack.pop(); } else { stack.push(s[i]); } } return stack.join(""); }; ~~~ # 大数相加 ~~~js // 大数相加（因为数字类型有存储上限，所以用字符串进行数字运算） function sum(a, b) { // 先给较短的字符数字前面补上0 let maxLen = Math.max(a.length, b.length); for(let i = a.length; i < maxLen; i ++) { a = '0' + a; } for(let i = b.length; i < maxLen; i ++) { b = '0' + b; } // 模拟加法的流程即可，借助一个jinWei变量辅助进位计算，不断构造低位即可 let result = ''; let jinWei = 0; for(let i = maxLen - 1; i >= 0; i --) { let sum = +a[i] + +b[i] + jinWei; jinWeil = 0; if(sum >= 10) { jinWei = 1; result = sum - 10 + result; } else { result = sum + result; } } return result; } console.log(sum("2136876483947893627", "2136876483947893627")); ~~~ # 二分法 ## 细节一、while的退出条件 使用场景：有序数组中查找元素 关于`while`循环的终止判断条件是`left < right`还是`left <= right`，其实都可以，`< 和 <=`分别对应了对搜索区间两种不同的描述，具体来说也就是两种情况，第一种是初始化`right = arr.lenght - 1`，这就表示我们的搜索区间是`arr`数组的`[left, right]`。`arr[right]`也在搜索的范围之内，对应`while`的终止条件是`left <= right`，退出循环时对应的情况是`left > right`，自然`[left, right]`（区间表示大于等于`left`且小于等于`right`的元素）区间内就没有元素了，即搜索区间为空，也就是所有元素搜索完毕（所谓搜索完毕，就是所有元素都因为我们的逻辑判断，被pass掉了，反映在边界指针`left`与`right`身上就是它们围成的搜索区间里面没有元素），**即`right = arr.length - 1`与`while`中`left <= right`的判断条件是对应的**，如下示例： ~~~javascript let left = 0; let right = arr.length - 1; while(left <= right) { // 缩小区间(增大left，缩小right)，寻找(并返回)答案 } ~~~ 第二种情况，初始化`right = arr.length`就代表我们的搜索区间是`[left, right)`（因为`arr[right]`出界嘛），对应`while(left < right)`，因为`left < right`终止时的情况是`left == right`，这时候搜索区间`[left, right)`中就没有元素了，就表示搜索完毕了，如下示例： ~~~js let left = 0; let right = arr.length; while(left < right) { // 缩小区间(增大left，缩小right)，寻找(并返回)答案 } ~~~ ## 细节二、搜索区间缩小的力度 然后在`while`循环的内部，在缩小搜索区间范围，即修改`left`和`right`的时候，具体是把`left`修改为`center`还是`center + 1`、`right`修改为`center`还是`center - 1`呢？说白了这就是一个缩小搜索区间从而缩小答案所在范围的过程，所以修改`left & right`遵循两个原则即可： * 与搜索区间的定义对齐：搜索区间的定义是在`while`循环开始之前定义`right`之时就已经确定的，比如`right = arr.length`，即搜索区间是左闭右开区间，这时候我们在`while`内部修改`right`为新值时，就要保持以左闭右开区间的定义为基础设置`right`，具体举个例子，在搜索区间为左闭右开的前提下，`right`设置为`center`，那么我们就相当于把`arr[center]`这个元素排除在搜索区间之外了，如果`right`设置为`center + 1`，那么就相当于`arr[center]`仍在搜索区间内。 * 与想要的目标对齐：说白了就是针对不同的目的，自行设计如何缩小区间，这就不属于规律性的东西了，完全属于需要我们自己设计的、算法的一部分，举个简单的例子，我们利用二分法寻找数组内的目标元素`target`，在搜索区间为左右都是闭区间的前提下，某一次`while`循环体内`arr[center] > target`，那么我们既然是就要寻找指定的元素`target`，目的很单纯，自然`arr[center]`判断不等于`target`之后就可以排除搜索区间了，自然`right`可以设置为`center - 1`，而不是`center`，**小总结：二分是方法，是指导思想，但不是具体的答案，细节的确定需要我们根据情况来具体设计。** ## 细节三、中间元素选择时的取整方向 最后，二分算法要防止死循环，概括来说，就是不能让`while`跳不出去，这里就牵扯最后一个需要注意的细节——**中心下标的取整方向**，我们先宏观感受一下所谓的`while`死循环，如果我们每次都能让区间有效缩小，那么跳出`while`循环是早晚的事儿！但什么情况下会导致区间无法缩小呢，举个抽象的描述性的例子，搜索区间内剩下最后两个元素了，我们向上取整算中间值，然后根据较大的那个元素进入一个`if`中，这个`if`中搜索区间不变，这就导致死循环，**确定取整方向防止死循环的方法就是：假设只剩下最后两个元素，（这时候向下取整总是会取到较小的元素，向上取整总是会取到较大的元素），这时候看区间的缩小，选择一个取整方向，这个取整方向可以稳定让`left`增加或者`right`减小。**下面的例子二中可以具体感受一下。 plus：判断左区间右移还是右区间左移有个技巧，就是把`arr[center]`与`target`按从小到大排列，加上`left`和`right`之后，脑子里想象一个从小到大的队列，比如`left arr[center] target right`，因为我们是缩小`target`所在的区间大小，此时`arr[center]`小于`target`，移动`left`或者`right`后保证`target`仍然在`left`和`right`中间，自然是`left`右移。 ## 二分实战 ### 例一、寻找有序数组`arr`中`target`元素的下标 ~~~js function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; // 同时相当于定义了搜索区间为闭区间[left, right] while (left <= right) { // left <= right，即当不满足搜索条件时left > right，此时搜索区间[left, right]内没有元素，搜索完毕 let centerIndex = Math.floor((left + right) / 2); // 这里向上或向下取整都行，因为下面三种if的情况搜索区间都能得到缩减（或者直接return），保证了每一次while循环体的执行都离着跳出循环近了一步，不会陷入死循环 let centerItem = arr[centerIndex]; if (target === centerItem) { return centerIndex; } else if (target < centerItem) { right = centerIndex - 1; // centerItem已经判断过了，所以直接排除在搜索区间之外即可 } else if (target > centerItem) { left = centerIndex + 1; // 与上同理，left = centerIndex + 1即排除centerItem } } return "数组中没有target元素"; } ~~~ ### 例二、寻找目标元素数组中从左到右第一个小于等于的元素的位置（vue3中`getSequence`方法源码中的二分应用） 举个例子，对于数组`[1, 2, 4, 8]`，我们给一个值`3`，那么从左到右`3`第一个小于等于的是`4`，所以返回`4`的位置下标`2`。 我们明确二分为整体思想后，就要设计算法，即 1. 选用哪一种区间（完全闭区间还是左闭右开） 2. `arr[center]`大于小于等于`target`时如何缩小区间（如何改变`left`和`right`） 3. 最后返回什么（经过设计最后哪个变量可以代表答案） 算法设计： 选用左闭右开区间，即`while(left < right)`，最后返回`left`。其实我也不知道这个算法从零到一应该怎么分析，前面这两个设计怎么来的我也说不清楚，但是基于这两个头和尾的设计，我来补充一下中间区间缩小的细节： 1. 如果`arr[center] < target`，因为我们要找的元素起码是大于`target`的，最后返回`left`，所以自然可以把`arr[center]`排除出搜索区间了，自然而然更新`left`为`center + 1`。 2. 如果`arr[center] === target`，这个元素满足`target`小于等于它，这时候我们缩小右边界，令`right = center`，这里我们是照应返回值与区间定义的，因为`while(left < right)`退出循环时`left === right`，所以我们把右边界缩小为`center`是合适的，这样最后退出循环时`arr[left]`一定是一个大于等于`target`的值，换句话说就是`right`指针指向的元素一定是满足大于等于`target`的元素，最后返回时`left`等于`right`，这里我表述不清楚，自己悟一悟没问题的。 3. 如果`arr[center] > target`，即`target < arr[center]`（方便想象那个递增队列进而确定移动哪个指针），`right`左移，`arr[center]`可以保证是`target`小于的元素，但不一定是从左到右第一个（最小的），所以同上，我们也让`right = center`即可。 算法实现： ~~~js function binarySearch(arr, target) { let left = 0; let right = arr.length - 1; while (left < right) { let centerIndex = Math.floor((left + right) / 2); // 一定要选择向下取整，运用上面的分析方法，在算法的最后，搜索区间内剩下了两个元素，左右指针分别指向2和4，然后目标元素是3，如果我们向上取整，那么中间元素就是4，那么右指针左移，进入到下面二个if中，...，进入死循环。 // 所以选择向下取整，因为left = centerIndex + 1，即区间必定缩小，这样永远不会因为最后时因为取整而导致区间无法缩小 let centerItem = arr[centerIndex]; if (target < centerItem) { right = centerIndex; } else if(target === centerItem) { right = centerIndex; } else if (target > centerItem) { left = centerIndex + 1; } } return left; } ~~~ # 判断字符串是否为循环字符串（某银行笔试） 比如输入"abcabcab"，他就是"abc"的循环，但是第三次没循环完整，输出`true` ~~~js const isCircle = (str) => { // 依次截取前i个字符，然后重复这个子串，生成一个比输入串长的子串，如果生成的长串一开始就是输入串，那么返回true for(let i = 1; i <= str.length; i ++) { let subStr = str.slice(0, i); if(judge(subStr, str)) { return true; } } return false; } const judge = (subStr, str) => { const lenMultiple = Math.ceil(str.length / subStr.length); const tempStr = subStr.repeat(lenMultiple); return tempStr.indexOf(str) === 0; } console.log(isCircle("avbbcavbbca")) ~~~ # 代码随想录——链表 # 代码随想录——二叉树 ## 二叉树理论基础 ### 二叉树种类 1. 满二叉树：每一层都是最多节点，比如三层的满二叉树，1、2、3层分别1、2、4个节点。节点数量`2**k - 1` 2. 完全二叉树：底层不一定满，但从左到右是连续的。 3. 二叉搜索树：对节点的结构没有具体的要求，唯一的要求就是对任意一个节点来说，左侧节点的值都小于节点值，右侧节点的值大于节点值 4. 平衡二叉搜索树：在二叉搜索树的基础上，对二叉树的结构增加了一个要求：对每一个节点来说，左右子树的高度差小于等于1。 ### 二叉树的存储方式 链式存储 & 线性存储 ### 遍历方式 前序中序后序都是指中间节点，对应中间节点在前、在中、在右。实现方式的话两种——递归和非递归 ### 手写二叉树定义 ~~~js /** * 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) * } */ ~~~ ## 递归遍历 1. 确定递归函数的参数以及返回值 2. 确定终止条件 3. 确定单层递归的逻辑 中序遍历（左根右）二叉树，并返回遍历顺序的数组 **本质就是定义`traversel(node)`函数的作用：中序遍历node结点，所以函数体中，我们要信赖此函数并使用（递归的本质），定义好递归的退出条件之后，中序遍历左节点直接使用本函数，遍历当前结点，中序遍历右结点。** ~~~js const traversel = (currentNode, ans) => { if(currentNode == null) return; // 递归结束条件 traversel(currentNode.left, ans); ans.push(currentNode.val); traversel(currentNode.right, ans); } ~~~ ## 94.二叉树的中序遍历 ~~~js /** * 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 inorderTraversal = function(root) { const ans = []; const traversal = (current) => { if(current === null) return; traversal(current.left); ans.push(current.val); traversal(current.right); } traversal(root); return ans; }; ~~~ ## 144.二叉树的前序遍历 ## 145.二叉树的后序遍历 ## 非递归实现前序遍历 一般用栈代替递归也就是这种简单的场景，对于前序遍历——根左右，我们一开始把`root`放入栈中然后开始循环： 1. 每次取出栈顶，（判断非空后）操作当前节点（如下即为记录遍历顺序） 2. 右节点入栈 3. 左节点入栈。**注：处理完根节点后需要处理左节点，但是栈后进才先出，所以左节点后入栈。** 4. 栈空推出循环 ~~~js /** * 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 preorderTraversal = function(root) { const ans = []; const stack = []; stack.push(root); while(stack.length !== 0) { const cur = stack.pop(); if(cur != null) { ans.push(cur.val); }else { continue; } stack.push(cur.right); stack.push(cur.left); } return ans; }; ~~~ ## 非递归实现后序遍历 在前序遍历的基础上（即根左右），我们先修改入栈顺序为先左再右，所以遍历结果为根右左，最后把结果数组进行反转`reverse`即为左右根，即为后序遍历。 ## 非递归实现中序遍历 不是很理解，感觉暂时需要死记硬背 ~~~js var inorderTraversal = function(root, res = []) { const stack = []; let cur = root; // 用来遍历二叉树的指针 while(stack.length || cur) { // 关于循环的推出条件，其实核心就是stack完全为空时退出，因为cur指针也可以（有可能）给stack带来元素，所谓完全为空即栈当前为空且cur指针此时为空指针（null） // 考虑最简单的二叉树：一个根root，左右两个孩子(左右孩子的孩子都为null) // 一开始拿到root，对于当前的指针指向的节点，直接入栈即可，然后再把指针移动到root.left if(cur) { stack.push(cur); cur = cur.left; } else { // 如果指针为空，那么意味着该处理栈中的节点了：pop出栈顶，然后操作栈顶元素，紧接着将指针改为栈顶的right孩子 cur = stack.pop(); res.push(cur.val); cur = cur.right; } }; return res; }; ~~~ ## 二叉树层序遍历（广度优先搜索模版题目）（力扣102） ### 思路总结 我们创建一个队列，一开始把根节点放进去，理论上来讲就可以开始循环了，循环体内就是放入取出队头（`shift`）操作，然后放入左孩子和右孩子即可，然后直到队列为空代表整个层序遍历结束。 但是题目要求对同一层的节点进行区分： ``` 输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]] ``` 所以我们在开始循环之前还需要在外层定义一个`currentFloorSize`变量用来记录下一个for循环需要出队的节点的数量，也就是同一层的节点数量，然后在循环体内更新这个`currentFloorSize`为下一个循环做准备。（看改进） ~~~js /** * 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 ans = []; const queue = []; // 队列 queue.push(root); // 初始化队列：放入根节点 let currentFloorSize = 1; // 记录层的节点数量 while(queue.length !== 0) { // 队列空即为所有节点都遍历完毕 const floor = []; // 当前层的节点数组 let node; let newFloorSize = 0; for(let i = 0; i < currentFloorSize; i ++) { // 每次循环只currentFloorSize个节点出队 node = queue.shift(); if(node != null) { floor.push(node.val); queue.push(node.left, node.right); newFloorSize += 2; } } currentFloorSize = newFloorSize; // 更新currentFloorSize if(floor.length != 0) { ans.push(floor); // 构造答案 } } return ans; }; // 改进版，没必要麻麻烦烦的写一堆逻辑来维护currentFloorSize，这个变量根本没有存在的必要，因为我们每次while循环体内（一个while循环体代表了遍历一层） // 所以我们只需要在开始遍历之前记录当前队列的长度即可，这个长度即为当前层的节点数量 var levelOrder = function(root) { const ans = []; const queue = []; // 队列 queue.push(root); // 初始化队列：放入根节点 while(queue.length !== 0) { // 队列空即为所有节点都遍历完毕 const floor = []; // 当前层的节点数组 const currentFloorSize = queue.length; // --------------------- 直接在循环体内开始遍历之前获取队列长度即为下一层的节点数量 -------------------- let node; for(let i = 0; i < currentFloorSize; i ++) { // 每次循环只currentFloorSize个节点出队 node = queue.shift(); if(node != null) { floor.push(node.val); queue.push(node.left, node.right); } } if(floor.length != 0) { ans.push(floor); // 构造答案 } } return ans; }; ~~~ ### 相关题目 #### 力扣107 给你二叉树的根节点 `root` ，返回其节点值 **自底向上的层序遍历** 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） ``` 输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]] ``` 思路：获取正常层序遍历的结果数组后直接`reverse`即可。 #### 力扣199.二叉树的右视图 给定一个二叉树的 **根节点** `root`，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 思路：说白了就是取出层序遍历每一层的最后一个节点。 ## 226.翻转二叉树（递归 + 二叉树遍历） 给你一棵二叉树的根节点 `root` ，翻转这棵二叉树，并返回其根节点。 **递归函数invertTree(root)的功能定义：反转root结点，那么我们信任此函数，确定函数退出条件后，反转的本质就是交换当前结点的left与right，并且对left与right也进行反转即可。** ~~~js /** * 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 {TreeNode} */ const swap = (node) => { const temp = node.left; node.left = node.right; node.right = temp; } var invertTree = function(root) { // 1.首先确定递归函数结束的条件，即二叉树节点为空（null === null返回true） if(root === null) { return root; } // 2.相当于前序遍历，swap先处理根节点，然后左节点和右节点 swap(root); invertTree(root.left); invertTree(root.right); return root; }; ~~~ ## 101.对称二叉树 给你一个二叉树的根节点 `root` ， 检查它是否轴对称。 **定义递归函数`compare(left, right)`的作用：判断`left`与`right`是否为对称的两个树** ~~~js /** * 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 {boolean} */ var isSymmetric = function(root) { // compare函数接收两个树，判断两个树是否是对称的 // compare是递归函数，只处理一层即可 const compare = (left, right) => { // 先处理两个树的根节点 if(left === null && right !== null || left !== null && right === null) { // 一个空一个非空——>不对称，直接返回false return false; } else if(left === null && right === null) { // 两个都空，直接返回true return true; } else if(left.val !== right.val) { // 经过上面的判断这里已经是保证两个节点非空了 return false; // 值不相等返回false } // 两个节点值相等，也就是说到这里可以保证两个节点不考虑孩子的情况下是对称的 const outSide = compare(left.left, right.right); // 比较两个节点的外侧孩子节点是否对称 const innerSide = compare(left.right, right.left); // 比较内侧孩子是否对称 return outSide && innerSide; } return compare(root.left, root.right); }; ~~~ ## 104.二叉树的最大深度 给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 **说明:** 叶子节点是指没有子节点的节点。 **示例：** 给定二叉树 `[3,9,20,null,null,15,7]`， ``` 3 / \ 9 20 / \ 15 7 ``` 返回它的最大深度 3 。 ### 前置概念——二叉树的深度与高度的区别 对于某个二叉树上的节点来说，深度就等于从根节点到这个节点所跨越的节点数量；高度是指某个节点为根节点的二叉树有几层 ### 题目分析 这里求二叉树的最大深度，其实就是算根节点二叉树的高度。 ~~~js /** * 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 maxDepth = function(root) { // 递归函数getHeight，接收根节点返回对应二叉树的高度 const getHeight = (root) => { // 1.递归终止条件——空节点时返回0即可（所谓递归终止，就是指返回一个常量，而非递归函数的调用） if(root === null) { return 0; } // 2.处理一层的逻辑，把当前根节点算为一个高度，然后加上孩子二叉树的高度 return 1 + Math.max(getHeight(root.left), getHeight(root.right)); } return getHeight(root); }; ~~~ # 回溯法 > 标准的回溯是递归过程中只用一个path变量空间并且维护其状态，这样可以节省空间，但是如果我们把path等设置为函数入参，并且递归调用时进行深拷贝，就没必要维护唯一path的状态了，也就没有了“回溯”的动作，编码更容易理解。但“回溯”可以作为一个优化方向，节省空间 ## 39.组合总和（回溯） 给你一个 **无重复元素** 的整数数组 `candidates` 和一个目标整数 `target` ，找出 `candidates` 中可以使数字和为目标数 `target` 的 所有 **不同组合** ，并以列表形式返回。你可以按 **任意顺序** 返回这些组合。 `candidates` 中的 **同一个** 数字可以 **无限制重复被选取** 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 `target` 的不同组合数少于 `150` 个。 **示例 1：** ``` 输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。 ``` **示例 2：** ``` 输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]] ``` **示例 3：** ``` 输入: candidates = [2], target = 1 输出: [] ``` 首先本题找所有组合，关键词**组合**——暴力搜索，考虑回溯法 ### 回溯法模版 ~~~ void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } } ~~~ **回溯法剪枝切入点：针对`for`循环，要么减少for循环的循环次数，要么在`for`循环内根据新的递归参数，决定要不要进行这次递归** 一般来说，存放结果存放的一般就是`path`，即我们遍历过程中产生的东西，相当于`map(当前遍历的数组)`，我感觉这种声明一个全局变量`path`的操作针对js语言来说，没必要，其他语言需要这样的原因是不方便声明一个数组，而我们js写个`[]`就是一个新数组，结合拓展运算符也非常方便进行扩充。但是这样声明全局`path`自然也有好处，节省空间，而且在我们`for`循环递归调用回溯算法之前进行回溯函数参数的计算，可以更灵活的进行剪枝（决定要不要进行递归调用） 标准回溯： ~~~js var combinationSum = function (candidates, target) { let res = []; let path = []; candidates.sort((a, b) => a - b); //这个是为了后面剪枝 const bt = (sum, startIndex) => { if (sum > target) return; if (sum === target) { res.push(path.slice()); return; } for (let i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) { let cur = candidates[i]; if (sum + cur > target) break; //剪枝 sum += cur; path.push(cur); bt(sum, i); path.pop(); sum -= cur; } } bt(0, 0); return res; }; ~~~ 简写回溯（但这里的简写不是说无剪枝，是指**`for`循环递归调用回溯函数之前不进行参数的计算，直接在函数调用中完成计算，并且回溯函数执行完毕之后，因为参数都是独立的拷贝，所以也无需进行参数（全局变量）还原**）： 如下代码具体针对题目，进行注释： ~~~javascript /** * @param {number[]} candidates * @param {number} target * @return {number[][]} */ var combinationSum = function(candidates, target) { let result = []; // 回溯函数的参数不着急写，直接写函数体，用到什么参数到回到这里补 // 关于startIndex参数，即for循环的遍历起始变量，这是针对题目本身**组合**的特点加入的变量，因为我们寻找的所有组合，组合是无序的，所以前面i = 0 到i = startIndex遍历的时候已经把所有包含0到startIndex的结果加入到结果集合中了——因为回溯本身就是暴力搜索，不会遗漏的搜索每种可能，举个例子：for(let i = 0...) { 递归调用 }，当i等于0时，就把包含candidates[0]的可能结果都找全了，i等于1时，调用递归函数就没必要考虑i=0的情况了 const backTrace = (startIndex, currentSum, currentArr) => { // 确定回溯的退出条件，本题都是正数求和，所以一旦求和大于target，就可以退出了；如果求和等于target，就放入结果集再退出 // 并且这里我们知道了应该补充一个参数currentSum来记录当前的求和 if(currentSum === target) { result.push(currentArr); return; } else if(currentSum > target) { return; } // 处理好一层的搜索逻辑即可 for(let i = startIndex; i < candidates.length; i ++) { // startIndex为i，更新currentSum，更新currentArr，进行递归调用 backTrace(i, currentSum + candidates[i], [...currentArr, candidates[i]]); } } backTrace(0, 0, []); return result; }; ~~~ 进行剪枝，参考如上标准回溯：先对`candidates`数组进行排序，对`for`循环的条件加强限制：`for (let i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++)`，即减少搜索树的一整个树枝（防止树的宽度增长）；进入递归调用前增加限制：`if (sum + cur > target) break;`，即不让搜索树这个树枝的深度增长。 ## 22.括号生成 数字 `n` 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 **有效的** 括号组合。 **示例 1：** ``` 输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"] ``` **示例 2：** ``` 输入：n = 1 输出：["()"] ``` ### 1.回溯法（递归➕剪枝） ~~~js /** * @param {number} n * @return {string[]} */ var generateParenthesis = function(n) { let result = []; // 递归（回溯）算法 // 有效括号 <===> 从左至右遍历括号字符串，累计左括号与右括号的数量，始终保持leftNum >= rightNum function backtracking(result, leftNum, rightNum, str) { if(str.length == 2*n) { // 括号数量累计完成，即找到一种有效括号 result.push(str); return; } // 剪枝 if(leftNum < rightNum) { // 已经是无效括号了，往后也不用再累积了 return; } if(leftNum >= rightNum) { // 当前还是有效括号 if(leftNum === n) { // 有效括号，自然左括号是比右括号多的，所以只判断左括号到没到n即可，如果到了n，说明左括号的数量用完了 backtracking(result, leftNum, rightNum + 1, str + ")"); } else { backtracking(result, leftNum + 1, rightNum, str + "("); backtracking(result, leftNum, rightNum + 1, str + ")"); } } } backtracking(result, 0, 0, ""); return result; }; ~~~ ## 剑指 Offer 38. 字符串的排列 输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 **示例:** ``` 输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"] ``` ### 1.dfs ~~~js /** * @param {string} s * @return {string[]} */ var permutation = function(str) { str = str.split("").sort((a, b) => (a > b ? 1 : -1)).join(""); let ans = []; const dfs = (currentStr, leftStr) => { if(leftStr.length === 0) { ans.push(currentStr); return; } for(let i = 0;i < leftStr.length;i ++) { if(i > 0 && leftStr[i] === leftStr[i - 1]) { continue; } dfs(currentStr + leftStr[i], leftStr.slice(0, i) + leftStr.slice(i + 1)); } } dfs("", str); return ans; }; ~~~ 1. 首先我们接收到一个str，可能是"abcb"这种有重复字母的字符串，我们希望处理这个字符串之后让相同的字符靠着比如"abbc"： ~~~js str = str.split("").sort((a, b) => (a > b ? 1 : -1)).join(""); ~~~ * split分割字符串为字符数组 * sort排序，js中字符虽然不可以做加减运算，但是不同的字符是可以比较大小的，比如"a">"b"会返回一个布尔值，所以sort函数中我们根据a与b的大小关系手动返回一个正数或者负数，就可以实现相同字符的相邻处理 2. 我们dfs函数接收两个参数currentStr和leftStr，dfs的退出条件是leftStr的长度为0，也就是我们字符串已经拼接完成了； 3. dfs中如果leftStr长度不为0，就对leftStr字符串进行逐字符遍历：把leftStr中的每一个字符都拼接到currentStr的最后，递归调用dfs 其实我们就是给currentStr字符串的最后那个位置选择字符，leftStr中的每个字符都可以放到currentStr最后的那个位置，所以我们要遍历leftStr，就相当于把leftStr的每一个字符放到currentStr字符串的最后那个位置，但是有一种情况不能放：leftStr中有重复的字符，自然这个字符不能放到同一位置两次，所以我们第一步处理字符串就是为了这个，如果`leftStr[i] === leftStr[i - 1]`，就说明leftStr[i]这个字符前面已经放到过currentStr字符串的最后那个位置了，所以我们就跳过。 ### 同类题目 #### 46.数组元素全排列 给定一个不含重复数字的数组 `nums` ，返回其 *所有可能的全排列* 。你可以 **按任意顺序** 返回答案。 **示例 1：** ``` 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ``` **示例 2：** ``` 输入：nums = [0,1] 输出：[[0,1],[1,0]] ``` **示例 3：** ``` 输入：nums = [1] 输出：[[1]] ``` 纯简化版（数组元素无重复） ~~~js /** * @param {number[]} nums * @return {number[][]} */ var permute = function(nums) { const result = []; const dfs = (currentArr, leftArr) => { if(leftArr.length === 0) { result.push(currentArr); return ; } for(let i = 0;i < leftArr.length; i ++) { dfs([...currentArr, leftArr[i]], [...leftArr.slice(0, i), ...leftArr.slice(i + 1, leftArr.length)]); } } dfs([], nums); return result; }; ~~~ #### 47.全排列2 给定一个可包含重复数字的序列 `nums` ，***按任意顺序*** 返回所有不重复的全排列。 **示例 1：** ``` 输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]] ``` **示例 2：** ``` 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] ``` 完全同38.字符串排列 ~~~js /** * @param {number[]} nums * @return {number[][]} */ var permuteUnique = function(nums) { const result = []; const dfs = (currentArr, leftArr) => { if(leftArr.length === 0) { result.push(currentArr); return ; } for(let i = 0;i < leftArr.length; i ++) { if(i > 0 && leftArr[i] === leftArr[i - 1]) { continue; } dfs([...currentArr, leftArr[i]], [...leftArr.slice(0, i), ...leftArr.slice(i + 1, leftArr.length)]); } } // 排列数组让相同元素相邻 nums = nums.sort((a, b) => a - b); dfs([], nums); return result; }; ~~~ # 动态规划 ## 509.斐波那契数（动态规划入门） **斐波那契数** （通常用 `F(n)` 表示）形成的序列称为 **斐波那契数列** 。该数列由 `0` 和 `1` 开始，后面的每一项数字都是前面两项数字的和。也就是： ``` F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 ``` 给定 `n` ，请计算 `F(n)` 。 ### 动态规划 动态规划（dynamic programming动态编程），即原问题可以分解成更简单的子问题，通过解决简单子问题最终得到目标问题的解 ### 五部曲 1. 定义dp数组的含义：动态规划，我们需要借助一个dp数组来描述问题的含义，可能是一维数组或者二维数组，比如斐波纳切问题中`dp`数组的含义：`dp[i]`就表示第i个斐波纳切数为`dp[i]` 2. 递推公式：`dp[i] = dp[i - 1] + dp[i - 2]`，对于斐波那契数列递推公式已经告诉我们了，也就是说计算`dp[i]`的问题可以被分解为计算`dp[i - 1]`和`dp[i - 2]`两个子问题。 3. `dp`数组如何初始化：对于斐波那契数列，初始化也告诉我们了，即`dp[0] = 1 & dp[1] = 1` 4. 遍历顺序：求斐波那契数列问题时，遍历顺序也很显然，因为第`i`个斐波那契数由第`i-1`和`i-2`个数得到，所以自然是从前往后遍历 5. 打印dp数组：对于动态规划问题`debug`的方式。 6. 或许可以压缩dp数组：比如斐波那契数列问题中只需要两个数组位置➕一个`sum`即可存储状态： ~~~js let sum = dp[1] + dp[0]; dp[0] = dp[1]; dp[1] = dp[2]; dp[2] = sum; ~~~ 代码： ~~~js /** * @param {number} n * @return {number} */ var fib = function(n) { const dp = [0, 1]; if(n === 0) return 0; if(n === 1) return 1; let sum; for(let i = 1; i < n; i ++) { // i = 1表示当前已经知道dp[1]了，只需要算出来dp[n]即可，根据举例法(n = 2时，需要计算一次即可)得知 i < n。 sum = dp[1] + dp[0]; dp[0] = dp[1]; dp[1] = sum; } return sum; }; ~~~ ## 70.爬楼梯（动态规划入门） 假设你正在爬楼梯。需要 `n` 阶你才能到达楼顶。 每次你可以爬 `1` 或 `2` 个台阶。你有多少种不同的方法可以爬到楼顶呢？ ### 1.递归（时空复杂度因为重复计算严重超限） ~~~js /** * @param {number} n * @return {number} */ var climbStairs = function(n) { if(n === 0) { return 0; } if(n === 1) { return 1; } if(n === 2) { return 2; } return climbStairs(n - 1) + climbStairs(n - 2); }; ~~~ ### 2.dp动态规划——>记录每个高度的跳法数量避免重复计算 dp[n]代表楼梯高度为n的跳法数量，初始化0，1，2高度后逐个向后计算即可（正向模拟，正向计算） ~~~js /** * @param {number} n * @return {number} */ var climbStairs = function(n) { const dp = [0,1,2]; for(let i = 3 ; i <=n ; i++){ dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }; ~~~ 复杂度： - 时间复杂度: O(n) - 空间复杂度: O(n) ### 3.优化2的空间复杂度 只用length为3的数组存储，dp[2]为高度为n的台阶的跳法（dp[0]为n-2高度的跳法、dp[1]为n-1高度的跳法） ~~~js /** * @param {number} n * @return {number} */ var climbStairs = function (n) { const dp = [0, 0, 1]; for (let i = 1; i <= n; i++) { dp[0] = dp[1]; dp[1] = dp[2]; dp[2] = dp[0] + dp[1] } return dp[2]; }; ~~~ ### 动态规划全新理解 说白了就是一个斐波那契数列，可以看509题动态规划套路 下面具体分析一下代码 ~~~js /** * @param {number} n * @return {number} */ // 爬到n阶的楼梯上这个问题有多少种爬法，可以分解为爬到n-1阶和爬到n-2阶爬法数之和，即问题分解 var climbStairs = function (n) { // 这里的三个return相当于处理一些边界情况，因为n=1、n=2，n值太小了，所以不满足动态规划分解问题的条件，我们直接返回 if(n === 0) return 1; // 没有实际意义，为了契合判题标准罢了，即n=0，结果就是1 if(n === 1) return 1; if(n === 2) return 2; // 对于n大于2的问题的解，由n-1和n-2两个子问题的解得到，所以我们的dp数组长度为2记录两个状态即可 let step; const dp = [1, 2]; for(let i = 2; i < n; i ++) { // i=2表示我们已经得到了n=2之前的问题的解，举例法确定i的限制：n=3，我们只需要计算一次即可，所以是ii=2到i<=3是两次计算** 3. dp数组初始化：因为我们一开始就可以站在第1阶或者第0阶，或者`dp[1] === dp[0] === 0` 4. 确定遍历顺序：这里高阶问题的答案是由低阶确定的，所以自然i从小到大遍历 ## 62.不同路径（动态规划） 一个机器人位于一个 `m x n` 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？ 分析： 首先，美团2020前端校招做这个题的时候用的暴力dfs，没超时，但是感觉确实挺蠢的。为什么呢，为啥能直接确定这个可以动态规划呢，**对于每一个m，n，都是由上面或者左边移动而来的，所以这里明显符合dp的思想，即复杂问题的解由简单子问题的解进行简单计算而来。**构造m*n的二维dp数组，确定`dp[i][j]`的含义：即从左上角走到i行j列的路径数；递推公式：`dp[i][j] = dp[i - 1][j] + dp[i][j - 1]`；初始化dp数组：因为dp[i]依赖的是左边和上边的dp值，所以我们把第一行和第一列初始化，初始化的值都是1（到达第一行或者第一列的每一个点都只有一条路径）；确定遍历顺序：从左到右 && 从上到下。最后计算完dp数组返回`dp[m - 1][n - 1]`即可。 ~~~js /** * @param {number} m * @param {number} n * @return {number} */ var uniquePaths = function(m, n) { let dp = []; for(let i = 0; i < m; i ++) { dp.push(new Array(n)); } for(let i = 0; i < n; i ++) { dp[0][i] = 1; } for(let i = 0; i < m; i ++) { dp[i][0] = 1; } for(let row = 1; row < m; row ++) { for(let col = 1; col < n; col ++) { dp[row][col] = dp[row][col - 1] + dp[row - 1][col]; } } return dp[m - 1][n - 1]; }; ~~~ ## 63.有障碍的不同路径（动态规划） 一个机器人位于一个 `m x n` 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？ 网格中的障碍物和空位置分别用 `1` 和 `0` 来表示。 ``` 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右 ``` 说白了这个和62唯一的区别就是**dp数组初始化时不能直接全初始化为1**以及**构造dp数组时障碍处为0**： ~~~js /** * @param {number[][]} obstacleGrid * @return {number} */ var uniquePathsWithObstacles = function(obstacleGrid) { let dp = []; const m = obstacleGrid.length; const n = obstacleGrid[0].length; for(let i = 0; i < m; i ++) { dp.push(new Array(n)); } // 初始化第一行 for(let i = 0; i < n; i ++) { dp[0][i] = 0; } for(let i = 0; (i < n) && (obstacleGrid[0][i] !== 1); i ++) { dp[0][i] = 1; } // 初始化第一列 for(let i = 0; i < m; i ++) { dp[i][0] = 0; } for(let i = 0; i < m && (obstacleGrid[i][0] !== 1); i ++) { dp[i][0] = 1; } for(let row = 1; row < m; row ++) { for(let col = 1; col < n; col ++) { if(obstacleGrid[row][col] === 1) { dp[row][col] = 0; } else { dp[row][col] = dp[row][col - 1] + dp[row - 1][col]; } } } for(let i = 0; i < m; i ++) { let str = ''; for(let j = 0; j < n; j ++) { str += dp[i][j] + ' '; } console.log(str); } return dp[m - 1][n - 1]; }; ~~~ ## 343.整数拆分（动态规划） 给定一个正整数 `n` ，将其拆分为 `k` 个 **正整数** 的和（ `k >= 2` ），并使这些整数的乘积最大化。 返回 *你可以获得的最大乘积* 。 **示例 1:** ``` 输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。 ``` **示例 2:** ``` 输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。 ``` **重点在于递推公式** ~~~js /** * @param {number} n * @return {number} */ var integerBreak = function(n) { // 确定dp数组的含义：dp[i]即为拆分i能得到的最大乘积 const dp = []; // dp数组初始化，dp[2]为1（必须拆分为2个以上的数，所以dp[0]、dp[1]也没必要理会，不是题目考察的范围） dp[2] = 1; for(let i = 3; i <= n; i ++) { // 第一层循环i表示计算dp[i] dp[i] = 0; // j代表从i中拆出来的一个数，拆分dp[i]的可能有三种： // 1.拆分为j和i-j即为最大 // 2.没拆出来最大解，但是当前拆分出来j的选择是正确的 // 3.dp[i]已经是最大了 for(let j = 1; j < i - 1; j ++) { // 遍历j，不断更新dp[i] dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j]); } } return dp[n]; }; ~~~ ## 0-1背包问题（动态规划） 给定一个背包容量`x`，然后有一些物品，每个物品都有对应的体积和价值，问背包最多可以装多少价值 定义`dp[i][j]`含义：对前`i`个物品（物品集合为前i个），我们背包容量为`j`时我们最多可以装`dp[i][j]`价值。 递推公式：`dp[i][j] = Math.max( dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i] )`，理解：我们计算`dp[i][j]`时理解为动态拓展物品集合的过程（物品集合从前1件，到前i件），基于这个前提理解，对于物品集从前`i - 1`件到前`i`件无非就两种可能： * 第`i`件物品是构成最优解的一个物品，即`dp[i][j] = dp[i - 1][j - weight[i]] + value[i]`，即对于物品集合为前`i - 1`个变成`i`个时，背包想获取第`i`个物品的价值，就需要给第`i`个物品腾出来它的体积。 * 第`i`件物品不是构成最优解的一个物品，所以物品集合多了它也白扩充，即`dp[i][j] = dp[i - 1][j]` 初始化：由递推公式可知，dp数组`dp[i][j]`依赖于更小的i和j的dp值，所以初始化第一行`dp[i][0]`和`dp[0][j]`即可满足后续推导了，容量为0或者物品集合为0，dp值都为0 遍历顺序：肯定是i和j都从小到大 ~~~js function testWeightBagProblem (weight, value, size) { // 定义 dp 数组 const len = weight.length, dp = Array(len).fill().map(() => Array(size + 1).fill(0)); // 初始化 for(let j = weight[0]; j <= size; j++) { dp[0][j] = value[0]; } // weight 数组的长度len 就是物品个数 for(let i = 1; i < len; i++) { // 遍历物品 for(let j = 0; j <= size; j++) { // 遍历背包容量 if(j < weight[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } } console.table(dp) return dp[len - 1][size]; } function test () { console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6)); } test(); ~~~ ### 滚动数组——一维dp数组 递推公式：`dp[i][j] = Math.max( dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i] )`，可以看成`dp[i] = Math.max( dp[i - 1][g(j)], dp[i - 1][fn(j)] )`，也就是`dp[i]`是由`dp[i - 1]`推导出来的，所以可以把原来的`i`行dp数组压缩为1行。 还是双重`for`循环，外层遍历物品，内层遍历容量，但是这里需要内层进行倒叙遍历，因为：倒叙计算每一个`dp[j]`的时候其实隐藏信息是我们正在计算第`i`行的`dp[j]`，也就是`dp[i][j]`，用到的`dp[小于j]`其实都是上一行的才对，也就是`dp[i - 1][小于j]`，所以如果我们正序遍历`j`，所造成的后果就是我们计算`dp[j]`的时候用到的前面的`dp[小于j]`其实都是第`i`行的`dp[小于j]`了，递推公式的就错了。 ~~~js function testWeightBagProblem(wight, value, size) { const len = wight.length, dp = Array(size + 1).fill(0); for(let i = 1; i <= len; i++) { for(let j = size; j >= wight[i - 1]; j--) { dp[j] = Math.max(dp[j], value[i - 1] + dp[j - wight[i - 1]]); } } return dp[size]; } function test () { console.log(testWeightBagProblem([1, 3, 4, 5], [15, 20, 30, 55], 6)); } test(); ~~~ ## 416.分割等和子集（动态规划、0-1背包变式、滚动数组） 给你一个 **只包含正整数** 的 **非空** 数组 `nums` 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 **示例 1：** ``` 输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11] 。 ``` **示例 2：** ``` 输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。 ``` **题目分析** 这个题目给了一个`nums`数组，能不能分割成两个等和的子集，说白了就是从数组中挑元素能不能挑出满意的集合，所谓满意，就是挑出`nums`数组总和的一半。这种精确挑出一个目标的问题，我们可以转化为背包问题：我们定义一个背包，容量为`nums`数组总和的一半，`nums`数组中的每个数字都看成物品，其体积和价值都是其值本身，0-1背包的递推公式意义还是不变，就是`dp[i][j]`的含义还是代表前`i`个物品，体积`j`的背包能装的最大价值，但是针对这个问题本身，我们背包容量为`nums`数组总和的一半而且物品体积和价值相同，我们就计算他能装的最大价值，考察每一个`i`对应`j=nums总和一半`时`dp`数组的值，如果`dp[i][target](这里target代表背包容量) === target(target代表物品价值)`，就说明原问题数组可以分成等和子集。 ~~~js /** * @param {number[]} nums * @return {boolean} */ var canPartition = function(nums) { // 计算target，并且数组总和如果不能整除2，就不可能被一堆整数分成等和的两部分 let target = nums.reduce((previous, current)=> { return previous + current; }, 0); if((target % 2) === 0) { target = target / 2; } else { return false; } // 这里我们使用滚动数组优化（一维dp数组） let dp = new Array(target + 1).fill(0); // 坑点：背包问题中根据背包容积申请数组大小时数组长度一定是容积加1，因为（容积为0）和（容积等于容积）都是背包数组的大小范围 for(let i = 0; i < nums.length; i ++) { for(let j = target; j - nums[i] >= 0; j --) { // 滚动数组需要倒序计算 dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]); } // 对于每一个i，即每一种物品组合，都要考虑背包容量为target时是不是能装target价值 if(dp[target] === target) { return true; } } return false; }; ~~~ ## 1049.最后一块石头的重量 II（0-1背包变式、动态规划、滚动数组） 有一堆石头，用整数数组 `stones` 表示。其中 `stones[i]` 表示第 `i` 块石头的重量。 每一回合，从中选出**任意两块石头**，然后将它们一起粉碎。假设石头的重量分别为 `x` 和 `y`，且 `x <= y`。那么粉碎的可能结果如下： - 如果 `x == y`，那么两块石头都会被完全粉碎； - 如果 `x != y`，那么重量为 `x` 的石头将会完全粉碎，而重量为 `y` 的石头新重量为 `y-x`。 最后，**最多只会剩下一块** 石头。返回此石头 **最小的可能重量** 。如果没有石头剩下，就返回 `0`。 **示例 1：** ``` 输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。 ``` **示例 2：** ``` 输入：stones = [31,26,33,21,40] 输出：5 ``` 问题转化：计算出来体积为石头总重量一半的背包最多可以装多少石头，`stones[i]`既为石头体积，也为石头价值，然后就可以用题目中描述的粉碎法去计算最终的结果了 ~~~js /** * @param {number[]} stones * @return {number} */ var lastStoneWeightII = function(stones) { let sum = stones.reduce((previous, current) => { return previous + current; }, 0) let target = Math.ceil(sum / 2); // 为了防止石头总重为奇数new Array报错所以取整，但是一定要用ceil向上取整（为了保证能出现答案0，背包体积只能大，不能小） // 总之这里target具体取值需不要要精确为一半，还是说多点也行，我也没想明白，题目可能测例也有特殊性（比如石头总重都可以整出2），反正这个题目掌握转换为0-1背包的思想就完事了 const dp = new Array(target + 1).fill(0); for(let i = 0; i < stones.length; i ++) { for(let j = target; j >= stones[i]; j --) { dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]); } } return Math.abs(sum - 2 * dp[target]); }; ~~~ 完全背包问题 ## 完全背包问题（动态规划） ### **定义：** 0-1背包即每个物品只有一件，完全背包是n种物品，每个物品可以选任意次，求某容量的背包能盛放的最大价值。 ### **递推公式：** 二维：`dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])` 滚动数组：`dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]`（同0-1背包的滚动数组递推公式） ### **理解：** 1. 还是以第`i`个物品放不放为线索，如果第`i`个物品不在构成最优解的集合种，也就是`dp[i][j] = dp[i - 1][j]`； 2. 关于`dp[i][j] = dp[i][j - weight[i]] + value[i])`，这里其实是第`i`种物品在构成最优解的集合中，但是因为并不是每种物品只有一个，所以说这里这个递推描述的动态过程是第`i`种物品的第若干个来了，要不要的过程。具体举个例子，`dp[i][j]`为当前的一个最优解，但是如果再来一个第`i`种物品，并且添加这一个第`i`种物品是属于新的最优解的，所以我们就要给这个物品腾出来空间，才能加上它的价值 3. 当初0-1背包中其实也是具体考虑的每一个单独的物品，而不是物品的种类，`dp[i][j] = dp[i - 1][j - weight[i]] + value[i]`其实就是说`dp[i][j]`最优解的情况下，加进来这一个物品（属于`i`类），可能能构成更优解，但正好第`i`类物品只有一个，所以添加这一个物品之前，`dp`的物品状态为`i - 1`；换句话说，对于完全背包，这个物品加进来之前，`dp`的状态还是`i`，这个物品的可能是第`i`类物品的第`n`个 ### **滚动数组遍历顺序：** **说白了这个遍历顺序就是为了保证计算新一行（新`i`）的`dp`数据（本质还是`dp[i][j]`）时他所依赖数据都是正确的（一维数组能正确读取到正确的二维数组的信息）** 之所以0-1背包中更新`dp`数组要倒序遍历，是因为`dp[i][j]`所依靠的是`i(第一维) = i - 1`且`j(第二维) < j`时的`dp`数据，所以倒序遍历更新`dp`才能保证用到的是`i = i - 1`时的数据（还未被更新的上一行数据） 完全背包中需要正序遍历更新`dp`数组，分析一下计算`dp[j]`时（`dp[i][j]`）所需要的两个数据即可，`dp[i - 1][j]`即上一行正上方的数据，所以这个没影响，我们更新`dp[j]`之前自然它本身就代表了`dp[i - 1][j]`；然后`dp[i][j - w[i]] + v[i]`用到的是第`i`行的数据，并且`j(第二维) < j`，所以计算`dp[j]`就需要我们正序遍历，先把第`i`行前面的`dp`计算出来，这样就能保证计算`dp[j]`时读取到正确的数据。 ## 494 -> 518.零钱兑换 II 给你一个整数数组 `coins` 表示不同面额的硬币，另给一个整数 `amount` 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 `0` 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 **示例 1：** ``` 输入：amount = 5, coins = [1, 2, 5] 输出：4 解释：有四种方式可以凑成总金额： 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 ``` **示例 2：** ``` 输入：amount = 3, coins = [2] 输出：0 解释：只用面额 2 的硬币不能凑成总金额 3 。 ``` **示例 3：** ``` 输入：amount = 10, coins = [10] 输出：1 ``` 这个题目更直白，思路完全与494转换后的背包问题一样，但唯一不同的是，这里**每个物品可以用无数次** 我们在494目标和中举例中说过，针对每一个`nums[i]`（物品），都构成了`dp[j]`的值的一部分，也就是`dp[j - nums[i]]`，494因为每个物品只有一个，所以这样针对第`i`件物品，它所提供的解的一部分就全了；但是这里每个物品可以用无限次，所以说要考虑基于这个物品有1件、有两件、有3件...的情况，每一种情况都是`dp[j]`的一部分。 **但是这里要明确一点——dp数组的含义，这里`dp[j]`同494，还是表示的每个物品都是一个独立的个体的情况下对于背包容量j能装满的方式，而并没有切换到完全背包的思路上来。** ~~~js /** * @param {number} amount * @param {number[]} coins * @return {number} */ var change = function(amount, coins) { const dp = new Array(amount + 1).fill(0); dp[0] = 1; for(let i = 0; i < coins.length; i ++) { // 第一层for还是遍历物品种类 let j = amount; while(j - coins[i] >= 0) { // 第二层同样还是循环遍历背包容量 let k = 1; while((j - k * coins[i]) >= 0) { // 这里完全背包相较于494——0-1背包装满问题，增加一层for循环，考虑同一类物品选的各种个数 dp[j] += dp[j - k * coins[i]]; k ++; } j --; } } return dp[dp.length - 1]; }; ~~~ ### 完全背包 `dp[i][j]`表示前`i`种硬币中凑出金额为`j`的硬币组合数/方案数。 递推公式： ~~~js dp[i][j] = dp[i - 1][j] + dp[i][j - weight[i]] ~~~ 这个递推公式就是单纯的字面意思，`dp[i][j]`就是完全由两部分组成，理解：考虑`dp[i][j]`的来源组成，我们要考虑的是如果才能全面（表达式全面覆盖`dp[i][j]`）且简单（表达式尽可能少）的表达清楚`dp[i][j]`的来源：我们把来源分成两大类，分别是：1.物品集合里不存在第`i`个元素 2.物品集合里存在第`i`个元素。首先这一定是一个覆盖全面的“全集”，然后针对第1类，因为不包含第`i`个物品，dp第一维肯定是`i - 1`（不能是`i - 2`...，那样就包含不全面了），dp第二维限制背包的容积，那肯定也是`j`，所以第1类所给`dp[i][j]`提供的组成就是`dp[i - 1][j]`；然后考虑第2类，我们需要保证这个组成包含了第`i`个物品，我们直接解释一下`dp[i][j - weight[i]]`吧，首先dp第一维为`i`，没啥好说的，表示我们物品集合为前`i`个物品，至于dp第二维为什么是`j - weight[i]`，可能会有疑问，这不是表示了只放了一个第`i`件物品吗，是不是没表示全面呢，其实这就陷入误区了，这里这个`weight[i]`表示的是最后一个加入背包中的第`i`类物品，不管前面的`j - weight[i]`中有几个第`i`种物品，这不需要关心了，只要是最后一个，也就是`j - weight[i]`加入这一个后变成`j`的这一个是第`i`种物品，就足够了。不像0-1背包装满背包的问题中，需要西格玛求和对于每一个物品提供的可能（即对于物品1，物品2，物品3，`dp[j] = dp[j - weight[0]] + dp[j - weight[1]] + dp[j - weight[2]]`）。 **我觉着上面总结的还是不清晰，只是大概表示了一种意思，这里最终解释一下`dp[i][j]`的递推公式的组成，即分成两类：有第i种物品和没有第i中物品两类，从这两类里找`dp[i][j]`的直接来源，我们要装满容量为`j`背包，自然没有第`i`种物品，加上第`i`种物品之前肯定是`dp[i - 1][j]`，这里一定不要陷入去理解`dp`如何来的这个误区，我们假设出来dp数组的含义之后，它怎么来的就不要管了，这不也正是动态规划的秒处吗！！，至于有第`i`种物品，直接转化到`dp[i][j]`的就是`dp[i][j - weight[i]]`，这里的直接转换说白了就是指与`dp[i][j]`的值一样（在前`i`件物品集合条件下）** （真不行就记住吧...） 然后如果用滚动数组进行空间压缩的话，递推公式： ~~~ dp[j] = dp[j] + dp[j - weight[i]] ~~~ **但它的实际所表示的完整递推含义就是上面的二维的，计算`dp[i][j]`时所依赖的是上面和左边的数据，所以最内层的for循环需要正序遍历以保证使用数据的正确性。** 多说一句，这里完全背包的装满问题的递推公式，其实和0-1背包的装满问题就完全不一样了，这个就是意义很清晰的二维数组的转化，和0-1背包装最大价值是完全类似的。换句话说，0-1背包的装满问题，它的dp数组并不能用二维数组去描述，没有正确的意义，它的i只是一种迭代计算，对每一个背包容量去遍历累加所有物品提供的可能。 题解： 滚动数组的本质还是二维数组的状态转换，`dp[0] = 1`也是举例法得知的符合递推公式的一个初始值。 ~~~js /** * @param {number} amount * @param {number[]} coins * @return {number} */ var change = function(amount, coins) { const dp = new Array(amount + 1).fill(0); dp[0] = 1; for(let i = 0; i < coins.length; i ++) { for(let j = coins[i]; j <= amount; j ++) { dp[j] = dp[j] + dp[j - coins[i]]; } } return dp[dp.length - 1]; }; ~~~ ### 组合数 or 排列数 先遍历物品种类，内层再便利背包容量这样求的是组合数： ~~~js for(let i = 0; i < coins.length; i ++) { for(let j = coins[i]; j <= amount; j ++) { dp[j] = dp[j] + dp[j - coins[i]]; } } ~~~ 先遍历背包容量，再遍历物品种类（写法上单纯交换两个for循环顺序，其他代码原封不动）这样求的是排列数： ~~~js for(let j = coins[i]; j <= amount; j ++) { for(let i = 0; i < coins.length; i ++) { dp[j] = dp[j] + dp[j - coins[i]]; } } // 意思就是上面的意思，但是上面的写法会报错，因为第一层for循环里访问不到i，所以 // 1. j从0开始遍历 // 2. 把保证j - coins[i] >= 0的逻辑放在最里面 for(let j = 0; j <= target; j ++) { for(let i = 0; i < nums.length; i ++) { if(j - nums[i] >= 0) { dp[j] += dp[j - nums[i]]; } } } ~~~ 我并不是很理解透彻里面的奥妙，也花了不少时间去尽力给自己一个理解了，暂时用别人的评论来帮助记忆吧： * 第一种：先遍历物品，再遍历背包，背包盛放的重量由`j - weight[i]`到`j`进行状态变化时其实默认是物品放到最后，所以不会出现物品的重复排放（大概感知一下意思罢了，这里确实不很懂） * 第二种：先遍历背包容量，再遍历物品，本质上是针对每一个背包容量，把每一个物品都放进去，然后剩余的容量再摆放物品，所以背包盛放的重量由`j - weight[i]`到`j`进行状态变化时相当于把每一个物品都放在最后一个的位置了一次，所以会出现逆序的情况（重复的组合），所以求的是排列数（大概理解、理解即可） **对于咱来说，重要的是把它当作工具去用。就像用Vue取开发一样，不一定知道Vue是怎么实现的。** ## 198.打家劫舍 **题目概括就是只能选数组中不相邻的元素，找出最大的和** 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，**如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警**。 给定一个代表每个房屋存放金额的非负整数数组，计算你 **不触动警报装置的情况下** ，一夜之内能够偷窃到的最高金额。 **示例 1：** ``` 输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 ``` **示例 2：** ``` 输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。 ``` ~~~js /** * @param {number[]} nums * @return {number} */ var rob = function(nums) { const dp = new Array(nums.length).fill(0); // dp[i]表示考虑前i个房屋(数组前i项)所能偷到的最多现金 dp[0] = nums[0]; // 值考虑前0项，自然是偷第一个屋子里的钱 dp[1] = Math.max(nums[0], nums[1]); // 因为不能偷相邻的，所以考虑前两个屋子，也就是dp[1]，就nums[1],nums[2]取最大 for(let i = 2; i < nums.length; i ++) { // 往后计算dp[i]，举例法得出遍历范围 dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); // 递推公式很简单：表示第i个屋子里的钱偷还是不偷（最优解里有没有nums[i]），偷的话就是nums[i] + dp[i - 2]，不偷的话就是dp[i - 1] } return dp[nums.length - 1] }; ~~~ ## 213.打家劫舍2 将打家劫舍1中的房子连成环，然后不能偷相邻的，问能偷的最多钱是多少 其实只需要把环拆开就好： * 不考虑数组第一个元素求解打家劫舍1 * 不考虑数组最后一个元素求解打家劫舍1 * 两者取最大值 ~~~js /** * @param {number[]} nums * @return {number} */ // 封装打家劫舍1的函数即可： var rob = function(nums) { const rob1 = (nums) => { const dp = new Array(nums.length).fill(0); dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for(let i = 2; i < nums.length; i ++) { dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]); } return dp[nums.length - 1]; } if(nums.length === 1) return nums[0]; if(nums.length === 2) return Math.max(nums[0], nums[1]); return Math.max(rob1(nums.slice(1)), rob1(nums.slice(0, nums.length - 1))); }; ~~~ ## [337. 打家劫舍 III（树形dp）](https://leetcode.cn/problems/house-robber-iii/) ~~~js /** * 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 rob = function(root) { const treeWalk = (root) => { // 返回[DoNot不偷, Do偷] if(root === null) return [0, 0]; // 如果不偷当前root结点 let doNotLeft = Math.max(...treeWalk(root.left)); let doNotRight = Math.max(...treeWalk(root.right)); let DoNot = doNotLeft + doNotRight; // 如果偷当前结点 let Do = root.val + treeWalk(root.left)[0] + treeWalk(root.right)[0]; return [DoNot, Do]; } const result = treeWalk(root); // result[0]和resutl[1]就分别代表不偷根结点/偷根结点所能获取的最大利益 return Math.max(...result); }; ~~~ ## 322.零钱兑换（动态规划、装满背包所需的最少物品数量） 给你一个整数数组 `coins` ，表示不同面额的硬币；以及一个整数 `amount` ，表示总金额。 计算并返回可以凑成总金额所需的 **最少的硬币个数** 。如果没有任何一种硬币组合能组成总金额，返回 `-1` 。 你可以认为每种硬币的数量是无限的。 **示例 1：** ``` 输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1 ``` **示例 2：** ``` 输入：coins = [2], amount = 3 输出：-1 ``` **示例 3：** ``` 输入：coins = [1], amount = 0 输出：0 ``` 定义`dp[i][j]`：前`i`个物品去装满容量为`j`的背包最少需要`dp[i][j]`个硬币。 递推公式：**`dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - weight[i]] + 1)`**，理解的话还是把`dp[i][j]`的来源分两类，一类就是不涉及第`i`个物品，或者说多了第`i`种物品我不用，所以`dp[i - 1][j]`是转变为`dp[i][j]`的一种可能；然后就是使用了第`i`种物品，最直接转变到`dp[i][j]`的状态就是`dp[i][j - weight[i]] + 1`，表示我们最少用了一个第`i`种物品，在背包装了`j - weight[i]`的东西时再装一个第`i`种物品，所以再加1，就转换为`dp[i][j]`。 如果我们不用滚动数组进行空间压缩，申请二维数组空间的时候，千万不要这么写： ~~~js const dp = new Array(coins.length + 1).fill(new Array(amount + 1).fill(0)) ~~~ 总之就是用`new Array`去填充数组的第二维，这样会使`dp[x]`都是同一个数组的引用。 正确的申请空间： ~~~js const dp = new Array(coins.length + 1); for(let i = 0; i <= coins.length; i ++) { dp[i] = new Array(amount + 1).fill(Infinity); } ~~~ `dp`数组初始化： 根据递推公式发现`dp[i][j]`依赖的是左边和上面的`dp`值，所以我们至少要把第一行和第一列进行初始化，然后才能用递推公式进行计算。题目的示例3已经告诉我们`amount = 0`时`dp`值为0，即第一列为`0`，意思是我们要装满大小为`0`的背包，只需要`0`个物品，然后初始化第一行，第一行表示我们拥有的物品集合为前`0`个，所以我们想装满背包是不可能的，所以我们把第一行初始化为无穷大，因为`dp`值的推导依赖的是正上方和正左方的值，所以`dp[0][0]`是不会影响计算的，是`0`是`Inifinty`都无所谓。 然后进行`dp`推导计算就可以了： ~~~js for(let i = 1; i <= coins.length; i ++) { // i代表当前的物品集合为前i个 // 因为我们要求的是两者中的较小值，所以我们这里j的for循环中不能进行j - coins[i - 1] >= 0的判断，这是为了保证dp[i][j] = dp[i - 1][j]; 的稳定执行，换句话说不能因为j - coins[i - 1] < 0，dp[i][j]就一直是Infinty，它的另一个来源是稳定可以访问的。 for(let j = 0; j <= amount; j ++) { // j代表背包的容量 dp[i][j] = dp[i - 1][j]; if(j - coins[i - 1] >= 0) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1); } } } ~~~ 题解代码： ~~~js /** * @param {number[]} coins * @param {number} amount * @return {number} */ var coinChange = function(coins, amount) { const dp = new Array(coins.length + 1); for(let i = 0; i <= coins.length; i ++) { dp[i] = new Array(amount + 1).fill(Infinity); } for(let i = 0; i <= coins.length; i ++) { dp[i][0] = 0; } for(let i = 1; i <= coins.length; i ++) { for(let j = 0; j <= amount; j ++) { dp[i][j] = dp[i - 1][j]; if(j - coins[i - 1] >= 0) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1); } } } if(dp[coins.length][amount] == Infinity) { return -1; } return dp[coins.length][amount] }; ~~~ ## 322 -> 279.完全平方数（动态规划、装满背包所需的最少物品数量） 给你一个整数 `n` ，返回 *和为 `n` 的完全平方数的最少数量* 。 **完全平方数** 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，`1`、`4`、`9` 和 `16` 都是完全平方数，而 `3` 和 `11` 不是。 **示例 1：** ``` 输入：n = 12 输出：3 解释：12 = 4 + 4 + 4 ``` **示例 2：** ``` 输入：n = 13 输出：2 解释：13 = 4 + 9 ``` 题目给的`n`即为背包大小，我们的任务就是填满背包，用完全平方数填满，所以我们手动构造一个由完全平方数构成的物品集合`goods`（`[1, 4, 9, 16, ... ]`），然后问题就转化为了322。 注意构造`goods`数组时要尽可能小的构造，防止超限即可 ~~~js /** * @param {number} n * @return {number} */ var numSquares = function(n) { // 我们构造的物品集合要在包含所有可能的前提下尽可能的小，不然会超限：一个数的完全平方不大于n即可，Math.ceil(n**(1/2)) <= n // new Array的数组fill之后才能map正确访问index const goods = new Array(Math.ceil(n**(1/2))).fill(0).map((item, index) => { return (index + 1)**2; }); // 申请初始空间 const dp = new Array(goods.length + 1); for(let i = 0; i < dp.length; i ++) { dp[i] = new Array(n + 1).fill(Infinity); // dp数组初始化 dp[i][0] = 0; } for(let i = 1; i <= goods.length; i ++) { for(let j = 0; j <= n; j ++) { dp[i][j] = dp[i - 1][j]; if(j >= goods[i - 1]) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - goods[i - 1]] + 1); } } } return dp[goods.length][n]; }; ~~~ ## 300.最长递增子序列（动态规划之子序列问题、子序列问题入门题）（TODO：最大子数组和整理一下，序列连续or不连续——动态规划问题） 给你一个整数数组 `nums` ，找到其中最长严格递增子序列的长度。 **子序列** 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，`[3,6,2,7]` 是数组 `[0,3,1,6,2,2,7]` 的子序列。 **示例 1：** ``` 输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。 ``` **示例 2：** ``` 输入：nums = [0,1,0,3,2,3] 输出：4 ``` **示例 3：** ``` 输入：nums = [7,7,7,7,7,7,7] 输出：1 ``` ~~~js /** * @param {number[]} nums * @return {number} */ var lengthOfLIS = function(nums) { // dp数组含义：dp[i]表示以nums[i]为结尾的最长子序列的长度 // 我们最后要返回的实际上是dp数组中最大的那一项，而不是dp数组的最后一项 let ans = 1; // dp数组初始化：把dp[0]初始化为1即可 const dp = new Array(nums.length).fill(1); for(let i = 1; i < nums.length; i ++) { // i 即为 dp[i]中的i，表示当前正在计算dp[i] for(let j = 0; j < i; j ++) { if(nums[i] > nums[j]) { // 如果nums[i] > nums[j]，说明加上第i个元素满足递增的条件，就可以去尝试更新dp[i] // 递推公式：dp[i]对应的子序列可能由任何一个dp[j]（j < i）对应的子序列加上第i个元素组成，长度也就是dp[j] + 1 dp[i] = Math.max(dp[j] + 1, dp[i]); if(dp[i] > ans) { ans = dp[i]; // 顺便更新ans } } } } return ans; }; ~~~ ## 53.给你一个整数数组 `nums` ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 **子数组** 是数组中的一个连续部分 **示例 1：** ``` 输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。 ``` ### 1.核心思想其实与动态相似（原创）： 从头到尾遍历一遍nums，不断更新最大和 我们需要借助一个beforeSum来记录当前指针位置之前连续项的和。 贪心思想：指针新遍历一个值的时候，**有可能更新最大和**的情况有两种： * beforeSum大于零，所以我们把当前项加上beforeSum * beforeSum小于零，当前项自身 这个beforeSum是帮助当前项“冲击“最大和的，所以如果曾经的beforeSum小于零，那么指针新考察过一个项之后，就把beforeSum换成这个刚考察的项即可；如果beforeSum大于零，它就对于”冲击“最大和有帮助，所以我们要保留它并累加上当前项。 ~~~js /** * @param {number[]} nums * @return {number} */ var maxSubArray = function(nums) { let currentMax = nums[0]; let beforeSum = nums[0]; for(let i = 1;i < nums.length;i ++) { if(beforeSum<0) { //beforeSum小于零，可能产生的最大和：nums[i] if(nums[i] > currentMax) { currentMax = nums[i]; } beforeSum = nums[i]; }else { //beforeSum大于零，可以产生的最大和：beforeSum+nums[i] beforeSum += nums[i]; if(beforeSum > currentMax) { currentMax = beforeSum; } } } return currentMax; }; ~~~ * 时间复杂度：我们只遍历了一次数组，所以`0(n)` * 空间复杂度：我们只借助了两个变量，使用了常数空间，所以`O(1)` ### 2.动态规划 定义子问题：以`nums`数组中第`i`项结尾的子数组的最大和记为`f(i)` **`f(i) = max{(f(i-1)+nums[i]), nums[i]}`** 所以遍历nums数组时，就用`nums[i]`表示`f(i)`：如果nums[i-1] > 0，那么f(i) = nums[i] = nums[i-1] + nums[i] ~~~js /** * @param {number[]} nums * @return {number} */ var maxSubArray = function(nums) { let currentMax = nums[0]; for(let i = 1;i < nums.length;i ++ ) { currentMax = Math.max((nums[i] + nums[i - 1]), nums[i], currentMax); if(nums[i-1] > 0) { nums[i] += nums[i - 1]; } } return currentMax; }; ~~~ 我感觉和方法一思想完全相同，只是说我们直接利用了nums数组本身来记录方法一中的beforeSum。 时空复杂度也是`O(n)`和`O(1)` ## 53 & 300总结 递增子序列双重for循环，但是连续子数组就是一重for循环，核心区别就在于连续不连续的区别：新加进来第i个元素的时候，如果是子序列那种不要求连续的，那么dp[i]的值可能由前面的i-1项任何一个得到；但是如果是要求连续的子数组，那么dp[i]只是由dp[i-1]得到。 # 递归终止条件理解 写递归时首先确定入参和递归函数的目标返回值之后，**函数体的第一步就是确定终止条件**，所谓递归终止，就是指返回一个常量或者直接结束函数，而非递归函数的调用。 # 贪心算法 ## 455.分发饼干 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。 对每个孩子 `i`，都有一个胃口值 `g[i]`，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 `j`，都有一个尺寸 `s[j]` 。如果 `s[j] >= g[i]`，我们可以将这个饼干 `j` 分配给孩子 `i` ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。 **示例 1:** ``` 输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。 所以你应该输出1。 ``` **示例 2:** ``` 输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2. ``` 思路：我们先把小孩的胃口和饼干的大小都按照从小到大的顺序排序，核心思路就是用尽量小的饼干依次喂胃口小的小孩。所以俩指针，一个while循环，直到把饼干消耗完即可返回答案 ~~~js /** * @param {number[]} g * @param {number[]} s * @return {number} */ var findContentChildren = function(g, s) { let result = 0; g.sort((a, b) => a - b); s.sort((a, b) => a - b); let gPointer = 0; let sPointer = 0; while(sPointer < s.length) { if(s[sPointer] >= g[gPointer]) { // 饼干可以满足孩子 sPointer ++; gPointer ++; result ++; } else { sPointer ++; // 用更大的饼干 } } return result; }; ~~~ # [秋招刷题挑战](https://juejin.cn/post/6947842412102287373) ## [234 回文链表（简单）](https://leetcode.cn/problems/palindrome-linked-list/description/) 遍历一次链表转数组，然后前后指针对比数组 ~~~js /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {boolean} */ var isPalindrome = function(head) { let listArr = []; let pointer = head; while(pointer !== null) { listArr.push(pointer.val); pointer = pointer.next; } let left = 0; let right = listArr.length - 1; while(left < right) { if(listArr[left] !== listArr[right]) { return false; } left ++; right --; } return true; }; ~~~ ## [206.反转链表（简单）](https://leetcode.cn/problems/reverse-linked-list/submissions/) 遍历一遍链表，遍历的过程中改变链表的next指针 每遍历一个结点时，我们的核心目标就是改变它的next为上一个结点；所以我们需要一个before指针用来记录当前节点的上一个结点，自然还需要一个pointer指针用作遍历指针。不断向后移动pointer并且修改before为下一次修改`pointer.next`做准备即可。 ~~~js /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var reverseList = function(head) { let before = null; let pointer = head; while(pointer !== null) { let next = pointer.next; pointer.next = before; before = pointer; // 因为我们要返回原本的最后一个有值的结点（null之前的结点），所以下一个为null的时候就不要向后移动了 if(next === null) break; else pointer = next; } return pointer; }; ~~~ ## [23.合并k个升序链表（困难）](https://leetcode.cn/problems/merge-k-sorted-lists/description/) 两两合并，对于k个升序链表，合并k - 1次即可，最后剩一个，就是答案。 ~~~js /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode[]} lists * @return {ListNode} */ var mergeKLists = function(lists) { if(lists.length === 0) return null; let mergeTime = lists.length - 1; for(let i = 0; i < mergeTime; i ++) { lists.splice(0, 2, merge2Lists(lists[0], lists[1])); } return lists[0]; }; const merge2Lists = (l1, l2) => { let arr = []; while(l1 !== null) { arr.push(l1.val); l1 = l1.next; } while(l2 !== null) { arr.push(l2.val); l2 = l2.next; } arr.sort((a, b) => a - b); let head = new ListNode(); let pointer = head; arr.forEach((val) => { let node = new ListNode(val); pointer.next = node; pointer = pointer.next; }) return head.next; } ~~~ ## [5. 最长回文子串（中等）](https://leetcode.cn/problems/longest-palindromic-substring/) 写一个函数，更新最大回文子串，这个函数接收俩下标，尽可能向外扩张。 主函数里，遍历一遍字符串，每个字符都有可能为回文子串的中心，调用更新函数即可。 ~~~js /** * @param {string} s * @return {string} */ var longestPalindrome = function(s) { if(s.length === 1) return s; let maxStr = ''; for(let i = 0; i < s.length - 1; i ++) { if(s[i] === s[i + 1]) { updateMax(i, i); updateMax(i, i + 1); } else { updateMax(i, i); } } function updateMax(left, right) { // 以下标为准 while(left - 1 >= 0 && right + 1 < s.length && s[left - 1] === s[right + 1]) { left --; right ++; } if(right - left + 1 > maxStr.length) { maxStr = s.slice(left, right + 1); } } return maxStr; }; ~~~ ## [14. 最长公共前缀（简单）](https://leetcode.cn/problems/longest-common-prefix/) 先拿到公共前缀可能的最大长度，也就是最短的字符串 然后遍历这个最大长度，每次检验一个字符，也就是看看所有的字符串这个位置的字符是不是相同，相同就加上这个字符；当然这个比较的过程还需要遍历一遍所有字符串，我用了Set判断是否相同。 ~~~js /** * @param {string[]} strs * @return {string} */ var longestCommonPrefix = function(strs) { let result = ''; let lenArr = strs.map(str => str.length); let maxLen = Math.min(...lenArr); for(let i = 0; i < maxLen; i ++) { let set = new Set(); for(let j = 0; j < strs.length; j ++) { set.add(strs[j][i]); } if(set.size === 1) { result += strs[0][i]; } else { break; } } return result; }; ~~~ ## [46. 全排列（中等）](https://leetcode.cn/problems/permutations/) dfs达成一定条件构造result ~~~js /** * @param {number[]} nums * @return {number[][]} */ var permute = function(nums) { let len = nums.length; let result = []; const dfs = (current, leftNumber) => { if(current.length === len) { result.push(current); return; } for(let i = 0; i < leftNumber.length; i ++) { dfs([...current, leftNumber[i]], leftNumber.slice(0, i).concat(leftNumber.slice(i + 1))); } } dfs([], nums); return result; }; ~~~ ## [剑指 Offer 42. 连续子数组的最大和](https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/) ~~~ 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例1: 输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 ~~~ 滑动窗口的思想，遍历一遍记录某个连续子数组的和，**for循环体中不要以`nums[i]`为考察对象**，考察tempSum。大于0就继续累加；小于零就更新窗口起点为`nums[i]`。 ~~~js /** * @param {number[]} nums * @return {number} */ var maxSubArray = function(nums) { let maxSum = nums[0]; let tempSum = nums[0]; for(let i = 1; i < nums.length; i ++) { if(tempSum > 0) { tempSum += nums[i]; } else { tempSum = nums[i]; } if(tempSum > maxSum) { maxSum = tempSum; } } return maxSum; }; ~~~ ## [1143. 最长公共子序列（中等）](https://leetcode.cn/problems/longest-common-subsequence/) ~~~js /** * @param {string} text1 * @param {string} text2 * @return {number} */ var longestCommonSubsequence = function(text1, text2) { // ↓为text1的长度，→为text2的长度 // dp[i][j]表示text1.slice(0, i + 1)与text2.slice(0, j + 1)的最长公共子序列长度 let dp = new Array(text1.length + 1).fill(); dp = dp.map(() => { return new Array(text2.length + 1).fill(0); // 目的是初始化第一行第一列，其中一个字符串长度为0，自然dp值为0 }) for(let i = 1; i <= text1.length; i ++) { for(let j = 1; j <= text2.length; j ++) { // s1表示text1.slice(0, i + 1)的最后一个字符 let s1 = text1.slice(0, i); s1 = s1[s1.length - 1]; // s2 let s2 = text2.slice(0, j); s2 = s2[s2.length - 1] if(s1 === s2) { dp[i][j] = 1 + dp[i - 1][j - 1]; }else { dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]); } } } return dp[text1.length][text2.length]; }; ~~~ ## [78. 子集（中等）（回溯算法）](https://leetcode.cn/problems/subsets/) ~~~js /** * @param {number[]} nums * @return {number[][]} */ var subsets = function(nums) { let result = []; let path = []; const backTrack = (startIndex, ) => { result.push([...path]); // 每次path数组改变都是一个新的子集，直接构造答案即可（第一个调用backTrack(0)肯定先把[]放进去，所以直接构造答案） // 一层的递归逻辑 for(let i = startIndex; i < nums.length; i ++) { path.push(nums[i]); // 只再加一个元素 backTrack(i + 1); // 基于加上的元素再加元素就递归调用 path.pop(); // 复原之后加另一个元素 } } backTrack(0) return result; }; // 回溯思想，非回溯写法： var subsets = function(nums) { let result = []; // 递归函数定义：还未处理nums.slice(startIndex)这些元素，并把currSet放入result答案集合 const backTrack = (startIndex, currSet) => { // 在处理[startIndex, last]元素之前，已经形成的子集 result.push([...currSet]); for(let i = startIndex; i < nums.length; i ++) { backTrack(i + 1, [...currSet, nums[i]]); } } backTrack(0, []); return result; }; ~~~ ## [131. 分割回文串（中等）（回溯算法）](https://leetcode.cn/problems/palindrome-partitioning/) ~~~js /** * @param {string} s * @return {string[][]} */ var partition = function(s) { let result = []; let path = []; // 判断一个字符串是否为回文串 const isHuiWen = (str) => { for(let i = 0; i < Math.floor(str.length / 2); i ++) { if(str[i] !== str[str.length - 1 - i]) { return false; } } return true; } const backTrack = (startIndex) => { if(startIndex === s.length) { // 消耗完整个s字符串即可结束 result.push([...path]); } // 这里i照顾str.slice(start, i)，i保证能切割到最后一个字符，所以i = s.length for(let i = startIndex + 1; i <= s.length; i ++) { let subStr = s.slice(startIndex, i); if(isHuiWen(subStr)) { // 是回文就push path.push(subStr); backTrack(i); path.pop(); } } } backTrack(0); return result; }; ~~~ ## [93. 复原 IP 地址（中等）（回溯算法）](https://leetcode.cn/problems/restore-ip-addresses/) ~~~js /** * @param {string} s * @return {string[]} */ var restoreIpAddresses = function(s) { let result = [], path = []; const backTrack = (startIndex) => { if(startIndex === s.length && path.length === 4) { // 字符串用光的同时分割成了4个数字才算是一个合格的ip result.push(path.map(str => { return parseInt(str); }).join(".")); return; } else if(startIndex === s.length || path.length === 4) { // 只满足一个条件就是废了（没构造成），可以结束了 return; } // i照应str.slice(startIndex, i) for(let i = startIndex + 1; i <= s.length; i ++) { let subStr = s.slice(startIndex, i); // 一个合格的ip段（0-255）应该满足：1.三位数以内 2.转化为数字小于255 3.不能以0开头，除非就只有0 if(subStr.length <= 3 && +subStr <= 255 && (subStr.indexOf(0) !== 0 || subStr.length === 1)) { path.push(subStr); backTrack(i); path.pop(); } } } backTrack(0); return result; }; ~~~ ## [496. 下一个更大元素 I（简单）](https://leetcode.cn/problems/next-greater-element-i/) 按题意描述的步骤写就行，完全没难度 ~~~js /** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var nextGreaterElement = function(nums1, nums2) { let result = []; for(let i = 0; i < nums1.length; i ++) { let index = nums2.indexOf(nums1[i]); let isFound = false; for(let j = index + 1; j < nums2.length; j ++) { if(nums2[j] > nums1[i]) { result.push(nums2[j]); isFound = true; break; } } if(!isFound) result.push(-1); } return result; }; ~~~ ## [503. 下一个更大元素 II（中等）](https://leetcode.cn/problems/next-greater-element-ii/) 在上面的基础上修改为取余循环遍历就好了，简单题 ~~~js /** * @param {number[]} nums * @return {number[]} */ var nextGreaterElements = function(nums) { let result = []; for(let i = 0; i < nums.length; i ++) { let startIndex = (i + 1) % nums.length; let isFound = false; while(startIndex % nums.length !== i) { if(nums[startIndex % nums.length] > nums[i]) { result.push(nums[startIndex % nums.length]); isFound = true; break; } startIndex ++; } if(!isFound) { result.push(-1); } } return result; }; ~~~ ## [155. 最小栈](https://leetcode.cn/problems/min-stack/) 要求我们自己实现的栈的`getMin`方法可以在常数时间内获取栈内最小元素：思路就是借助一个辅助栈，同步push和pop，但是辅助栈只push当前最小的元素，所以push x的时候要比较栈顶和x的大小。 ~~~js var MinStack = function() { this.x_stack = []; this.min_stack = [Infinity]; }; MinStack.prototype.push = function(x) { this.x_stack.push(x); this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x)); }; MinStack.prototype.pop = function() { this.x_stack.pop(); this.min_stack.pop(); }; MinStack.prototype.top = function() { return this.x_stack[this.x_stack.length - 1]; }; MinStack.prototype.getMin = function() { return this.min_stack[this.min_stack.length - 1]; }; ~~~ ## [3. 无重复字符的最长子串（中等）（滑动窗口）](https://leetcode.cn/problems/longest-substring-without-repeating-characters/) ~~~js /** * @param {string} s * @return {number} */ var lengthOfLongestSubstring = function(str) { if (str.length <= 1) {return str.length} // 照应str.slice(left, right) // 初始化滑动窗口内就只有str[0]这一个字符 let left = 0 let right = 1 let max = 0 let temp // 总体思路就是针对每一个无重复子串，比如上面初始化的str.slice(0, 1)，我们不断扩展right，一旦新拓展进来的字符与前面的重复了 // 就说明当前这个子串已经拓展到极限了，可以更换为下一个子串了，所以就移动左指针，移动到下一个子串的起始位置即可 while(right < str.length){ temp = str.slice(left, right) if (temp.indexOf(str[right]) > -1) { // 如果当前字符重复，移动左指针（目标是到下一个子串的起始点） left++ continue } else { // 如果不重复，移动右指针（拓展当前无重复子串） right++ } // 每次移动都尝试更新答案 if (right - left > max) { max = right - left } } return max }; ~~~ ## [215. 数组中的第K个最大元素（堆排序）](https://leetcode.cn/problems/kth-largest-element-in-an-array/) ~~~js /** * @param {number[]} nums * @param {number} k * @return {number} */ var findKthLargest = function(nums, k) { const heapify = (arr, root, orderedNum) => { // 建立大根堆 let leftIndex = root * 2 + 1; let rightIndex = root * 2 + 2; let maxIndex = root; // 寻找根左右中最大结点 if(leftIndex < (arr.length - orderedNum)) { // 左孩子存在（在未排序的范围里） if(arr[leftIndex] > arr[root]) { maxIndex = leftIndex; } } if(rightIndex < (arr.length - orderedNum)) { // 右孩子存在 if(arr[rightIndex] > arr[maxIndex]) { maxIndex = rightIndex; } } // 交换根与最大节点并且整理堆结构 if(root !== maxIndex) { [arr[root], arr[maxIndex]] = [arr[maxIndex], arr[root]]; heapify(arr, maxIndex, orderedNum); } } // 建堆 for(let i = nums.length - 1; i >= 0; i --) { heapify(nums, i, 0); } // // 排序 for(let i = 0; i < k; i ++) { [nums[0], nums[nums.length - 1 - i]] = [nums[nums.length - 1 - i], [nums[0]]]; heapify(nums, 0, i + 1); } return nums[nums.length - k]; }; ~~~ ## [15. 三数之和](https://leetcode.cn/problems/3sum/) ~~~js /** * @param {number[]} nums * @return {number[][]} */ var threeSum = function(nums) { // 针对某个很长的全零特例 if(nums.every((item) => item === 0)) return [[0, 0, 0]]; let result = []; let tempNums = [...nums].sort((a, b) => a - b); for(let i = 0; i < tempNums.length - 2; i ++) { // left 与 right 照应数组下标 let left = i + 1; let right = tempNums.length - 1; while(left < right) { let target = 0 - tempNums[i]; let sum = tempNums[left] + tempNums[right]; if(sum === target) { result.push([tempNums[i], tempNums[left], tempNums[right]]); left ++; right --; } else if(sum > target) { right --; } else if(sum < target) { left ++; } } } return [...new Set(result.map((item) => { item.sort((a, b) => a - b); return JSON.stringify(item); }))].map((str) => { return JSON.parse(str); }); }; ~~~ ## [674. 最长连续递增序列（dp）](https://leetcode.cn/problems/longest-continuous-increasing-subsequence/) ~~~js /** * @param {number[]} nums * @return {number} */ var findLengthOfLCIS = function(nums) { let ans = 1; // dp数组含义: dp[i]表示以nums[i]结尾的最长连续子序列长度为dp[i] // dp数组初始化: dp[0] = 1，即以下标为0的元素结尾的最长递增子序列长度为1（本身长度就为1） const dp = new Array(nums.length).fill(1); for(let i = 1; i < nums.length; i ++) { // i表示正在计算dp[i] if(nums[i] > nums[i - 1]) { // nums[i] > nums[i - 1]说明以nums[i - 1]结尾的递增子序列加上第i个元素仍然满足递增子序列，所以dp[i] = dp[i - 1] + 1 dp[i] = dp[i - 1] + 1; if(dp[i] > ans) { ans = dp[i]; } } // 起始这里省略了，如果nums[i] <= nums[i - 1],即当前数字不满足递增，那么dp[i] = 1,因为初始化时已经做了 } return ans; }; ~~~ ## [11. 盛最多水的容器（依据木桶效应）](https://leetcode.cn/problems/container-with-most-water/) ~~~js /** * @param {number[]} height * @return {number} */ var maxArea = function(height) { let left = 0; let right = height.length - 1; let ans = 0; let currentContent; while(left < right) { currentContent = Math.min(height[left], height[right]) * (right - left); ans = currentContent > ans ? currentContent : ans; if(height[left] === height[right]) { left += 1; right -= 1; }else if(height[left] < height[right]) { left += 1; }else if(height[left] > height[right]) { right -= 1; } } return ans; }; ~~~ ## [42. 接雨水](https://leetcode.cn/problems/trapping-rain-water/) ~~~js /** * @param {number[]} height * @return {number} */ var trap = function(height) { let sum = 0; for(let i = 0;i < height.length;i ++) { let left = height.slice(0, i).find((value) => value > height[i]); let right = height.slice(i+1, height.length).find((value) => value > height[i]); if(left && right) { sum += Math.min(Math.max(...height.slice(0, i)), Math.max(...height.slice(i+1, height.length))) - height[i]; } } return sum; }; ~~~ ## [55. 跳跃游戏（贪心）](https://leetcode.cn/problems/jump-game/) 维护一个当前可以到达的最大位置即可，遍历每一个“弹跳点”，只有当前可以到达的最大位置大于当前位置，才有资格更新最大位置。最后根据最大位置返回即可 ~~~js /** * @param {number[]} nums * @return {boolean} */ var canJump = function(nums) { let maxPosition = 0; for(let i = 0; i < nums.length; i ++) { if(maxPosition >= i && i + nums[i] > maxPosition) { maxPosition = i + nums[i]; } } if(maxPosition >= nums.length - 1) return true; return false; }; ~~~ ## [45. 跳跃游戏 II（不懂）](https://leetcode.cn/problems/jump-game-ii/) 核心的贪心思想就是：比如我们站在一个位置，可以选择跳跃到后面n个位置，我们要选跳完之后覆盖范围最大的那个位置跳，而不是越远越好。 （代码暂时不理解，先不搞了） ~~~js /** * @param {number[]} nums * @return {number} */ var jump = function(nums) { let curIndex = 0 // 当前处于的位置 let nextIndex = 0 // 下一跳要跳到的位置 let steps = 0 // 记录跳的步数 for(let i = 0; i < nums.length - 1; i++) { nextIndex = Math.max(nums[i] + i, nextIndex) // if(i === curIndex) { curIndex = nextIndex steps++ } } return steps }; ~~~ ## 8.20字节笔试 题目场景是这样的，就是给一个手环（用数组表示），里面有三个红球，其余都是白球，我们会魔法，每次施法可以交换相邻的两个球的位置，然后给一个最小距离k，表示我们希望任意两个红球之间的最小距离不小于k。问基于上面的手环（我们知道红球的位置以及球的总数），还有k，最少施法多少次可以实现距离的要求 其实这个题就是转换，他题目里是给了三个红球，相当于这三个红球把手环分成了三段，其实我们施法不可能交换两个白球（交换是没有意义的），肯定都是交换白球与红球，所以说，我们的施法交换，可以理解为把其中一段里面的白球扔到另一段里；此时又发现凑巧的是，三段——>两两可交换，所以题目就可以转化为：把白球多的段里的白球扔到白球不足的段里，相当于把白球少的段给补全，而不用在意到底是哪个段里来的白球。 举个具体的例子就是：三个段分别包含的白球数量[1, 2, 3]，要求的每段最少包含2两个白球，所以我们只需要把1这一段多加上一个就完事了 ## 8.28京东笔试 就是有n道编程题，小明总时间为t，需要在有限时间内达到最高分。每道题可选择三种处理方式：①算法解需要消耗t1时间得到s1分数，②暴力解需要消耗t2时间得到s2分数，③放弃，不消耗时间没有分数 dp（i）（j）=max（dp（i-1）（j），dp（i-1）（j-算时（i））+算分（i），dp（i-1）（j-暴时（i）+暴分（i））），经典01背包，在MAX里多写一个可能就好了。 ## [394. 字符串解码](https://leetcode.cn/problems/decode-string/)（8.30美团面试） 给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: `k[encoded_string]`，表示其中方括号内部的 `encoded_string` 正好重复 `k` 次。注意 `k` 保证为正整数。 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 `k` ，例如不会出现像 `3a` 或 `2[4]` 的输入。 **示例 1：** ``` 输入：s = "3[a]2[bc]" 输出："aaabcbc" ``` **示例 2：** ``` 输入：s = "3[a2[c]]" 输出："accaccacc" ``` **示例 3：** ``` 输入：s = "2[abc]3[cd]ef" 输出："abcabccdcdcdef" ``` **示例 4：** ``` 输入：s = "abc3[cd]xyz" 输出："abccdcdcdxyz" ``` ~~~js /** * @param {string} s * @return {string} */ var decodeString = function(s) { const pattern = /(\d+)\[([^\[\]]*)\]/; let match = s.match(pattern); while(match !== null) { s = s.replace(match[0], match[2].repeat(parseInt(match[1]))); match = s.match(pattern); } return s; }; ~~~ 思路： 因为我们需要处理的结构非常明确：`<重复次数>[<重复内容>]`，其中重复内容里面可能嵌套结构本身。 所以一个最直观的思路就是把这种结构直接进行`replace`字符串替换，替换掉所有的结构之后就是我们需要的字符串。 所以我们的核心就是不断地调用`replace`方法对输入的字符串中的结构进行替换，所以我们需要写一个正则不断地去匹配字符串中的结构，非常轻松我们可以写出结构的大致正则模式： ~~~js const pattern = /(\d+)\[(.*)\]/; ~~~ 上面的正则非常明确表示：一开始是若干个数字，然后是一个`[]`，里面存在任意内容。 如果用这个正则去匹配`3[a]2[c]`这种多个方括号的结构的话，就会出问题。因为正则匹配时默认遵循一种“贪婪模式”，即它倾向于匹配更多的内容，所以`"3[a]2[c]".match(pattern)`的结果是： ~~~js ['3[a]2[c]', '3', 'a]2[c', index: 0, input: '3[a]2[c]', groups: undefined] ~~~ 其中`match`方法的第一项为匹配到的内容整体，第二项第三项分别为正则`()`中匹配到的内容，我们预期的是利用第二项作为重复次数，第三项作为重复内容，然后替换输入字符串的第一项，这里就出现了问题。 解决方法也很简单，我们修改正则表达式： ~~~js const pattern = /(\d+)\[([^\[\]]*)\]/; ~~~ 第二个`()`中我们写了：`[^\[\]]*`，`[]`搭配`^`表示不能出现`[]`中的字符，这个正则匹配的结果，只会是不存在嵌套的最简单的结构，比如：`3[a]`而不是`3[a2[c]]`或者如上的情况。 我们还要了解`match`方法在匹配不到合适内容时返回值为`null`，这也就是我们循环结束的条件，只要是匹配不到这种需要处理的结构，就说明字符串处理完毕了。经过循环处理，我们就把原始字符串中所有的需要处理的结构，从左到右，从内到外的替换完毕了。 至于`replace(a, b)`这个api，它的涵义是用`b`去替换`a`，也就是说第一个参数是我们字符串中存在的内容（想替换掉的内容）。 ## [2407. 最长递增子序列 II](https://leetcode.cn/problems/longest-increasing-subsequence-ii/) 给你一个整数数组 `nums` 和一个整数 `k` 。 找到 `nums` 中满足以下要求的最长子序列： - 子序列 **严格递增** - 子序列中相邻元素的差值 **不超过** `k` 。 请你返回满足上述要求的 **最长子序列** 的长度。 **子序列** 是从一个数组中删除部分元素后，剩余元素不改变顺序得到的数组。 就是基于最长递增子序列题目的基础上加一个条件：子序列相邻元素插值小于等于k： dp的解法时间复杂度为O(n2)，对于nums过大时超时，需要其它的算法，这里就不纠结了。 ~~~js /** * @param {number[]} nums * @param {number} k * @return {number} */ var lengthOfLIS = function(nums, k) { let dp = new Array(nums.length).fill(1); let result = 1; for(let i = 0; i < nums.length; i ++) { // 考察以nums[i]结尾的子序列 for(let j = 0; j < i; j ++) { if(nums[i] > nums[j] && nums[i] - nums[j] <= k) { dp[i] = Math.max(dp[j] + 1, dp[i]); if(dp[i] > result) { result = dp[i]; } } } } return result; }; ~~~ ## [876. 链表的中间结点](https://leetcode.cn/problems/middle-of-the-linked-list/)（快慢指针） 给你单链表的头结点 `head` ，请你找出并返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。 快慢指针的思想很容易想到，主要是链表存在单数或者双数的两种情况，究竟什么时候快指针停下，以及快指针停下时慢指针处于什么位置，这些细节问题更难把握。 **当前的一个方法论：一开始快慢指针都指向第一个真实结点，每次移动快走2，慢走1。允许快指针移动到最后一个真实结点或者真实节点的next，也就是null，这样的话，针对链表为单数时，慢指针正好处于中心，比如链表： 1 => 2 => 3，经过一次移动慢指2，快指3；针对链表结点数为双数，如：1 => 2 => 3 => 4，最终慢指3，快指4后面的null。**这样，也就有了如下的统一单双数的代码，但是，这个方法论如何来的呢？ 证明：先思考单数情况，比如有3个结点： 1 => 2 => 3，那么fast指针停止移动的条件就是`fast.next === null`，而且慢指针一定处于对称中心的那个结点，往后再加2个结点，相当于多移动一次，情况还是一样，所以单数情况就完成了逻辑统一。然后是双数情况，我们需要返回第二个中间结点，我们想要利用单数情况的规律，所以我们把链表最后一个null也算进来，补充成单数情况。这样，只要是fast指针指向了最后一个结点的next，也就是null，那么慢指针也就必然指向了第二个中间结点。所以`while`的结束条件将两者统一：`fast === null`是针对单数情况的；`fast.next === null`是针对双数情况的。 ~~~js /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var middleNode = function(head) { let fast = head; let slow = head; // slow指针寻找链表中点 while(fast !== null && fast.next !== null) { fast = fast.next.next; slow = slow.next; } return slow; }; ~~~ ## [143. 重排链表](https://leetcode.cn/problems/reorder-list/)（美团一面） 给定一个单链表 `L` 的头节点 `head` ，单链表 `L` 表示为： ``` L0 → L1 → … → Ln - 1 → Ln ``` 请将其重新排列后变为： ``` L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → … ``` 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。 ~~~js /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {void} Do not return anything, modify head in-place instead. */ var reorderList = function(head) { let fast = head; let slow = head; // slow指针寻找链表中点（找中点没啥好说的，就是876，上一题） while(fast !== null && fast.next !== null) { fast = fast.next.next; slow = slow.next; } // 反转链表（也是基本操作，但注意经过反转之后，中间结点的next指向null，也就相当于从后往前跟从前往后的两个链表断开了，但是它们公用了中间结点） // 而且在反转过程中，我们还需要记录反转链表的有值的头节点，为下面链表合并做准备 let before = null; let pointer = slow; let last; while(pointer !== null) { let nextPointer = pointer.next; pointer.next = before; before = pointer; if(nextPointer === null) { last = pointer; } pointer = nextPointer; } // 合并链表 let firstP = head; let secondP = last; let virtualHead = new ListNode(); pointer = virtualHead; let flag = true; // true 对应当前追加first链表，false 对应追加second链表（反转链表） while(firstP !== null && secondP !== null) { // 一次循环体追加一个结点，循环退出的条件就是被公用的那个中间结点也被追加上去了，所以也就等价于firstP或者secondP某一个指针指向了null（因为追加完后会移动） if(flag) { pointer.next = firstP; pointer = pointer.next; firstP = firstP.next; } else { pointer.next = secondP; pointer = pointer.next; secondP = secondP.next; } flag = !flag; } return virtualHead.next; }; ~~~ ## [141. 环形链表](https://leetcode.cn/problems/linked-list-cycle/)（快慢指针） 给你一个链表的头节点 `head` ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 `next` 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。**注意：`pos` 不作为参数进行传递** 。仅仅是为了标识链表的实际情况。 *如果链表中存在环* ，则返回 `true` 。 否则，返回 `false` 。 思路： 快指针每次走两步，慢指针每次走一步，如果有环，那么两个指针进入环里后，每次距离缩小一，总会遇上，判断为有环；如果没环，快指针就会遇到null，判断为没环： ~~~js var hasCycle = function(head) { let fast = head; let slow = head; while(fast !== null && fast.next !== null) { // 保证fast可以向下移动，即fast.next.next的正确访问 fast = fast.next.next; slow = slow.next; if(fast === slow) { return true; } } return false; }; ~~~ ## [LCR 074. 合并区间](https://leetcode.cn/problems/SsGoHC/) 以数组 `intervals` 表示若干个区间的集合，其中单个区间为 `intervals[i] = [starti, endi]` 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。 **示例 1：** ``` 输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. ``` **示例 2：** ``` 输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。 ``` ~~~js /** * @param {number[][]} intervals * @return {number[][]} */ var merge = function(intervals) { // 目标，将合并完成的集合放入result数组中 let result = []; // 合并两个集合(这里把集合写成时间了)的方法：但需要time1的起始时间小于time2的起始时间——这样就可以根据time1的结束时间落入的区间进行集合合并 function merge2(time1, time2) { let oneBegin = time1[0]; let oneEnd = time1[1]; let twoBegin = time2[0]; let twoEnd = time2[1]; if(oneEnd < twoBegin) { return [time1, time2]; } else if(oneEnd >= twoBegin && oneEnd < twoEnd) { return [[oneBegin, twoEnd]]; } else if(oneEnd >= twoEnd) { return [time1]; } } // 根据起始时间进行排序 intervals.sort((a, b) => a[0] - b[0]); // 只有两个及以上元素，才能调用merge2函数 while(intervals.length >= 2) { let time1 = intervals.shift(); let time2 = intervals.shift(); let mergeTime = merge2(time1, time2); if(mergeTime.length === 2) { // 如果两个时间无法合并，那么第一个时间就可以放入result数组中，第二个时间还需要继续进行合并（可能与后面的时间合并） result.push(mergeTime[0]); intervals.unshift(mergeTime[1]); } else if(mergeTime.length === 1){ // 如果两个时间发生了合并，那么这个合并得到的时间也不能放入result，因为可能与后面的时间合并成更大的时间 intervals.unshift(mergeTime[0]); } } return result.concat(intervals); // 最后intervals里面可能剩余一个时间（或者不剩），这个时间肯定是无法合并的，直接放入result即可 }; ~~~ ## [237. 删除链表中的节点](https://leetcode.cn/problems/delete-node-in-a-linked-list/) 有一个单链表的 `head`，我们想删除它其中的一个节点 `node`。 给你一个需要删除的节点 `node` 。你将 **无法访问** 第一个节点 `head`。 链表的所有值都是 **唯一的**，并且保证给定的节点 `node` 不是链表中的最后一个节点。 删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是： - 给定节点的值不应该存在于链表中。 - 链表中的节点数应该减少 1。 - `node` 前面的所有值顺序相同。 - `node` 后面的所有值顺序相同。 （目标也就是经过处理之后，整个链表代表的值等价于去掉了node那个结点，而不是真正需要把结点引用给删除） **思路：首先我们可以通过`node.next=node.next.next;`的方式让链表跳过一个结点，这样就能保证链表少了一个元素，但是我们跳过的是`node.next`这个结点，所以我们需要把`node.next`的值移动到当前`node`上，从值的角度来审视这个链表，也就等价于把当前`node`删除了。** ~~~js var deleteNode = function(node) { node.val=node.next.val; node.next=node.next.next; }; ~~~ ## [64. 最小路径和](https://leetcode.cn/problems/minimum-path-sum/) 给定一个包含非负整数的 `*m* x *n*` 网格 `grid` ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。 **说明：**每次只能向下或者向右移动一步。 **思路：没啥好说的，初始化第一行和第一列之后，经典dp[i][j]表示来到(i, j)的最小和，它的来源就是上面或者左面，所以递推公式非常简单，上边或者左边哪个小取哪个就好了。** ~~~js /** * @param {number[][]} grid * @return {number} */ var minPathSum = function(grid) { let dp = new Array(grid.length).fill().map(() => new Array(grid[0].length).fill(0)); // dp初始化 dp[0][0] = grid[0][0]; for(let i = 1; i < dp[0].length; i ++) { dp[0][i] = dp[0][i - 1] + grid[0][i]; } for(let i = 1; i < dp.length; i ++) { dp[i][0] = dp[i - 1][0] + grid[i][0]; } for(let i = 1; i < dp.length; i ++) { for(let j = 1; j < dp[0].length; j ++) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; } } return dp[dp.length - 1][dp[0].length - 1]; }; ~~~ ## [128. 最长连续序列](https://leetcode.cn/problems/longest-consecutive-sequence/) 给定一个未排序的整数数组 `nums` ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 `O(n)` 的算法解决此问题。 **示例 1：** ``` 输入：nums = [100,4,200,1,3,2] 输出：4 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。 ``` **示例 2：** ``` 输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9 ``` **思路：Set也是基于哈希算法实现的，其api的时间复杂度是O(1)，所以我们先把数组转为Set，我们遍历一遍Set来更新最大长度即可。更新规则：当前遍历的数字为n，如果Set里面没有n - 1，那么可以理解为 n 这个数是一个连续序列的起点，所以我们用一个while计算这个序列的长度并尝试更新最大长度即可。** ~~~js /** * @param {number[]} nums * @return {number} */ var longestConsecutive = function(nums) { let maxLen = 0; let set = new Set(nums); for(let num of set) { if(!set.has(num - 1)) { let len = 1; while(set.has(num + 1)) { len++; num++; } if(len > maxLen) { maxLen = len; } } } return maxLen; }; ~~~ ## [148. 排序链表](https://leetcode.cn/problems/sort-list/) 给你链表的头结点 `head` ，请将其按 **升序** 排列并返回 **排序后的链表** 。 **示例 1：** ![img](image/链表排序.jpg) ``` 输入：head = [4,2,1,3] 输出：[1,2,3,4] ``` **总的排序思路是归并排序，也就是先把链表断开成两个链表（快慢指针），然后分别对这两个子链表进行排序，最终用merge函数合并两个有序链表。为什么不能用冒泡排序（双重for，内层j循环length - i次）实现链表排序，因为我们没办法控制链表遍历的停止位置，所以我们必须使用把一整个链表遍历完成的这种排序方式。归并排序中链表断开还有链表合并，这都是针对链表整体（不是操作局部链表）进行的操作。** ~~~js /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var sortList = function(head) { // 递归的退出条件：传入的head为null或者就是单独的一个结点（head.next === null） if(head === null || head.next === null) { return head; } let slow = head; let fast = head; while(fast.next !== null && fast.next.next !== null) { // 保证fast可以往后跳就可以了 slow = slow.next; fast = fast.next.next; } let second = slow.next; // second即为链表的后半段，即一个新的子链表 slow.next = null; // 链表的前半段与second链表断开 return merge(sortList(head), sortList(second)); // 对两个链表递归排序后进行合并 }; // 链表合并函数 function merge(l1, l2) { let head = new ListNode(); // 我们新建一个空头节点，这个结点不存放信息,所以构造head也是一直构造headP.next（headP即为head的指针）最终返回head.next let p1 = l1, p2 = l2, h = head; // p1链表1指针，p2链表2指针,h答案链表指针 while(p1 !== null && p2 !== null) { // l1、l2是有序的，不断选择较小结点拼接到答案链表上即可（耗空一个链表） if(p1.val < p2.val) { h.next = p1; p1 = p1.next; } else { h.next = p2; p2 = p2.next; } h = h.next; } // 拼接上没耗空的另一个即可 if(p1 === null) { h.next = p2; } else if(p2 === null) { h.next = p1; } return head.next; } ~~~ ## [236. 二叉树的最近公共祖先](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/) 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 [百度百科](https://baike.baidu.com/item/最近公共祖先/8918834?fr=aladdin)中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（**一个节点也可以是它自己的祖先**）。” **示例 1：** ![img](image/binarytree.png) ``` 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。 ``` ### lowestCommonAncestor递归函数的功能定义 （递归函数定义功能的目的在于函数体中我们可以完全的信赖该函数，从而递归调用，解决问题，就像dp数组的定义一样，我们定义了其含义，就可以完全的信赖，可以参考上面[110. 平衡二叉树](https://leetcode.cn/problems/balanced-binary-tree/)代码实现中的getHeight函数——求二叉树高度，同理） 定义`lowestCommonAncestor(root, p, q)`为递归函数，其作用是寻找`root`结点为根的二叉树中`p`和`q`的最近公共祖先，当然这里有个前提是如果以`root`为根的二叉树中存在`p`和`q`（换言之，`p/q`可能只存在一个），如果两个结点都存在，那么保证`lowestCommonAncestor`返回的就是他俩的最近公共祖先。 ### 总体思路 如果root等于p或者q，那么root一定就是两者的最近公共祖先了，可以直接返回。root等于null，我们也直接返回null即可 然后如果root不是p也不是q，只是一个普通的结点，这时候我们借助`lowestCommonAncestor`尝试在root.left和root.right中寻找p和q的最近公共祖先，如果left和right都找到了，也就是说明左子树和右子树中各存在p或者q中的一个，所以root就是最近公共祖先。如果只有root.left找到了，那么直接返回root.left递归调用`lowestCommonAncestor`的结果即可。只有root.right找到同理。如果两者都没找到，那么说明root这个二叉树中找不到pq的公共祖先，返回null。 ~~~js /** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */ var lowestCommonAncestor = function(root, p, q) { // 如果root为根的二叉树存在中存在p和q，那么返回其最近公共祖先，找不到就返回null if(root === null || root === p || root === q) { return root; } let left = lowestCommonAncestor(root.left, p, q); let right = lowestCommonAncestor(root.right, p, q); if(left && right) { return root; } else if(left !== null) { return left; } else if(right !== null) { return right; } else { return null; } }; ~~~ # 社招刷题 ## 抢红包算法 **纯随机** ```js const getRadomNum = (min, max) => { // [min, max) return Math.random() * (max - min) + min; } const getArraySum = (arr) => { return arr.reduce((sum, cur) => sum + cur, 0); } // m人，n元 function moneyDistribute(peopleNum, totalMoney) { const result = []; const MIN_MONET = 0.01; for(let i = 0; i < peopleNum - 1; i ++) { const leftMoney = getArraySum(result); const maxMoney = totalMoney - leftMoney - (MIN_MONET * (peopleNum - 1)); const distributeMoney = getRadomNum(MIN_MONET, maxMoney); result.push(distributeMoney); } result.push(totalMoney - result.reduce((sum, cur) => sum + cur, 0)); return result; } ``` ![CleanShot 2025-07-16 at 00.07.37@2x](./image/抢红包期望.png) ![CleanShot 2025-07-16 at 00.05.27@2x](./image/抢红包算法.png) ## 283.移动0 给定一个数组 `nums`，编写一个函数将所有 `0` 移动到数组的末尾，同时保持非零元素的相对顺序。 **请注意** ，必须在不复制数组的情况下原地对数组进行操作。 ```ts /** Do not return anything, modify nums in-place instead. */ function moveZeroes(nums: number[]): void { const numsLength = nums.length; /** * 移动index处的0至数组末尾 */ const moveZeroToArrayLast = (index: number) => { nums.splice(index, 1); nums.push(0); } /** * 遍历一遍数组(遍历numsLength次即可)，遇到0就移动至数组最后 * 需要以对比次数决定是否结束，因为数组时时在变，不能以index为准 */ let operateCount = 0; let currentIndex = 0; while(operateCount < numsLength) { operateCount++; const currValue = nums[currentIndex]; // 非0，无需移动，指针移动至下一个元素 if(currValue) { currentIndex++; continue; } // 为0，需要删除当前的0并且在队尾补充一个0，指针无需移动 moveZeroToArrayLast(currentIndex); } }; ``` ## 46.全排列（递归/回溯） ```ts /** * 返回排除下标为index的元素的新数组 */ const getArrayExceptIndex = (array: Array, index: number) => { if(index === array.length) return array.slice(0, index); return [...array.slice(0, index), ...array.slice(index + 1, array.length)]; } function permute(nums: number[]): number[][] { const result: Array> = []; const core = (currentArrange: Array, leftNumbers: Array) => { if(!leftNumbers.length) { result.push(currentArrange); return; } leftNumbers.forEach((val, index) => { core([...currentArrange, val], getArrayExceptIndex(leftNumbers, index)); }) } core([], nums); return result; }; ``` ## 739.每日温度（栈） 给定一个整数数组 `temperatures` ，表示每天的温度，返回一个数组 `answer` ，其中 `answer[i]` 是指对于第 `i` 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 `0` 来代替。 **示例 1:** ``` 输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0] ``` **示例 2:** ``` 输入: temperatures = [30,40,50,60] 输出: [1,1,1,0] ``` **示例 3:** ``` 输入: temperatures = [30,60,90] 输出: [1,1,0] ``` 最笨的方法，O(n**2)复杂度没什么难度，考虑用栈进行算法优化，复杂度为O(n) **思考方向** 我们动态的考虑日期一天天增加，我们得知第二天的温度后，如果比第一天温度高，就可以记录第一天的结果了，如果比第一天温度低，相当于第一天的结果还没找到，并且第二天的结果也没找到，需要继续看第三天 从上面的三天就可以感知出来，对于找不到答案的日期，我们需要先暂存下来，对于找到答案的，我们立马记录答案即可，如果我们用一个**数组**记录当下未找到答案的日期，遍历时对于每个新日期都尝试为数组里的日期寻找答案，这样就是O(n**2)，本质上还是双重for循环；如何存储未找到答案的日期，就非常巧妙了，如果每天温度都递增，那就不存在找不到答案的日期，只有当天日期不如上一天温度高，才说明没找到上一天的答案，需要把上一天记录下来，以及当天也未找到答案，所以昨天的温度与当天的温度是递减的，如果明天温度小于今天的，那么连续三天温度都是递减的。 所以当来了一个高温，高于当前无答案的天，这时候就可以从最小的温度的天开始更新，依次更新温度更高的天。 例如，当前未记录温度的某三天，温度分别是8、6、5，然后来了一个7，相当于倒数第一个和倒数第二个温度对应的日期都找到答案了 **记录未找到答案的日期的容器，就是栈，并且这个栈存储的日期对应的温度是递减的，这样当新来一个更低的温度时，如果比栈顶还低，就没必要遍历栈中更靠底的日期了，这就是所谓的“单调栈”** ```ts function dailyTemperatures(temperatures: number[]): number[] { if(temperatures.length === 1) return [0]; const result = new Array(temperatures.length).fill(0); const stack: Array = [0]; for(let dayNumber = 1; dayNumber < temperatures.length; dayNumber++) { const todayTemperature = temperatures[dayNumber]; for(let i = stack.length - 1; i >= 0; i--) { const temperature = temperatures[stack[i]]; if(todayTemperature <= temperature) { break; } const lastDayNumber = stack.pop(); result[lastDayNumber] = dayNumber - lastDayNumber; } stack.push(dayNumber); } return result; }; ``` ## [142. 环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/) 给定一个链表的头节点 `head` ，返回链表开始入环的第一个节点。 *如果链表无环，则返回 `null`。* 如果链表中有某个节点，可以通过连续跟踪 `next` 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 `pos` 来表示链表尾连接到链表中的位置（**索引从 0 开始**）。如果 `pos` 是 `-1`，则在该链表中没有环。**注意：`pos` 不作为参数进行传递**，仅仅是为了标识链表的实际情况。 **不允许修改** 链表。 **示例 1：** ``` 输入：head = [3,2,0,-4], pos = 1（第四个节点重新连到了第二个节点上，构成环） 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。 ``` **对于链表来说，我们可以在遍历时，用map、array等数据结构把他构造成打平的数据结构。目的就是能直接借助map/array等数据结构及其api直接get/set/判断任意节点** ```ts /** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ /** * 对于链表来说，我们可以在遍历时，用map、array等数据结构把他构造成打平的数据结构 * 目的就是能直接借助map/array等数据结构及其api直接get/set/判断任意节点 */ function detectCycle(head: ListNode | null): ListNode | null { // 已经遍历过的所有节点 const allNodes: Array = []; let pointer = new ListNode(undefined, head); while(pointer.next !== null) { const currentNode = pointer = pointer.next; if(allNodes.includes(currentNode)) return pointer; else allNodes.push(currentNode); } return null }; ``` ## [437. 路径总和 III](https://leetcode.cn/problems/path-sum-iii/)（二叉树遍历） 给定一个二叉树的根节点 `root` ，和一个整数 `targetSum` ，求该二叉树里节点值之和等于 `targetSum` 的 **路径** 的数目。 **路径** 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 ```ts function pathSum(root: TreeNode | null, targetSum: number): number { if (!root) return 0; // 返回从当前节点开始的所有符合条件的路径数量 const dfs = (node: TreeNode | null, sum: number): number => { if (!node) return 0; let count = 0; sum += node.val; if (sum === targetSum) count++; count += dfs(node.left, sum); count += dfs(node.right, sum); return count; }; // 遍历二叉树，对每个节点都作为起点进行dfs计算 const traverse = (node: TreeNode | null): number => { if (!node) return 0; return dfs(node, 0) + traverse(node.left) + traverse(node.right); }; return traverse(root); } ``` 如果看上面的traverse不顺眼，看下面的遍历代码 ```js // 遍历二叉树求和 let sum = 0; const traverse = (node) => { if(node === null) return; // 处理当前节点 console.log(node) sum += node.val; // 处理左右树 traverse(node.left); traverse(node.right); }; ``` 在题解中本质也是求和，但dfs函数具备返回值，所以`return dfs(node, 0) + traverse(node.left) + traverse(node.right);`的操作本质上就是`sum += node.val; traverse(node.left); traverse(node.right);` 而且，**上面的dfs函数写的很好，因为是一个纯函数，而非借助闭包实现求和。** ## [560. 和为 K 的子数组](https://leetcode.cn/problems/subarray-sum-equals-k/) 给你一个整数数组 `nums` 和一个整数 `k` ，请你统计并返回 *该数组中和为 `k` 的子数组的个数* 。 子数组是数组中元素的连续非空序列。 **示例 1：** ``` 输入：nums = [1,1,1], k = 2 输出：2 ``` **示例 2：** ``` 输入：nums = [1,2,3], k = 3 输出：2 ``` ### TODO：优化 **前缀和 - 前面的某个前缀和 = 这段区间的和** ### 暴力方法 因为题目定义了子数组为连续的，直接把所有子数组的情况枚举出来，双重for两个循环变量，一个代表数组起点，一个代表数组终点 ```ts function subarraySum(nums: number[], k: number): number { let resultCount = 0; // i表示以nums[i]为首个元素的子数组 for(let i = 0; i < nums.length; i++) { let sum = 0; // j表示子数组以nums[j]这个元素为最后一个元素 for(let j = i; j < nums.length; j++) { sum += nums[j]; if(sum === k) resultCount++; } } return resultCount; }; ``` ## [17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)（回溯+for） 给定一个仅包含数字 `2-9` 的字符串，返回所有它能表示的字母组合。答案可以按 **任意顺序** 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 ![CleanShot 2025-07-27 at 18.09.52@2x](./image/电话号码映射.png) **示例 1：** ``` 输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] ``` **示例 2：** ``` 输入：digits = "" 输出：[] ``` **示例 3：** ``` 输入：digits = "2" 输出：["a","b","c"] ``` **题目本质上可以抽象为n个数组，每个数组抽取一个数字，所有可能的排列** ### 暴力 ``` // 暴力法："234" => [[a, b, c], [d, e, f], [g, h, i]]，依次组合最前面的两个子数组，最终只剩一个子数组时返回 // 本质上等价于n个数组，n层嵌套for循环进行组合 ``` ### 回溯法 首先题目获取结果的过程可以抽象为如下树形结构，有多少个数字不确定，有多少个数字，树就对应多深，这也就对应了**回溯函数的终止条件——深度**，至于每个集合选择的字母不同，有对应了不同的结果，所以回溯函数中需要**在for循中针对不同选择递归调用回溯函数** ![CleanShot 2025-07-27 at 18.14.24@2x](./image/回溯法抽象.png) ```ts function letterCombinations(digits: string): string[] { if(!digits.length) return []; // Map<(2-9), str> const map = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]; const result: Array = []; const core = (curStr: string, leftNumberStr: string) => { if(curStr.length === digits.length) { result.push(curStr); return; } // 消耗掉剩余数字中的第一个 const currentNumberMapStrs = map[leftNumberStr[0]]; for(let i = 0; i < currentNumberMapStrs.length; i++) { core(curStr + currentNumberMapStrs[i], leftNumberStr.slice(1, leftNumberStr.length)); } } core('', digits); return result; }; ```