# algorithm **Repository Path**: zhengdashun/algorithm ## Basic Information - **Project Name**: algorithm - **Description**: 个人算法仓库总结 - **Primary Language**: Unknown - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2023-04-25 - **Last Updated**: 2025-06-19 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # 代码随想录 ## 数组 ### 704.二分查找 二分查找的前提就是`数组有序`。难点在于二分查找的边界条件 - while(left<=right) --- right=middle-1 这种情况下 target 存在于[left,right] ，**left==right 是有意义的**。 if(num[middle]>target) 那么**right=middle-1** ```js var search = function (nums, target) { //数组有序，用二分 let left = 0 let right = nums.length - 1 while (left <= right) { let middle = parseInt((left + right) / 2) if (nums[middle] < target) { left = middle + 1 } else if (nums[middle] > target) { right = middle - 1 } else { return middle } } } console.log(search([-1, 0, 3, 5, 9, 12], 9)) ``` - while(lefttarget) 那么**right=middle**，这是因为 right 是开区间，nums[middle]不能是 right。 ```js var search = function (nums, target) { //数组有序，用二分 let left = 0 let right = nums.length //因为right不能选中，必须从最后一位的下一位开始 while (left < right) { let middle = parseInt((left + right) / 2) if (nums[middle] < target) { left = middle + 1 } else if (nums[middle] > target) { right = middle } else { return middle } } } console.log(search([-1, 0, 3, 5, 9, 12], 9)) ``` ### 35.搜索插入位置 > 结论：如果在有序表中二分查找(即[left,right]中)没有查找到目标元素，那么对应的 left 就会在最贴近 target 元素的偏大的那个，right 就会在最贴近 target 的偏小的一个 [1,3,5] 找 4 最后 left==5 right==3 ```js var searchInsert = function (nums, target) { //最简单的方式肯定是直接遍历 //用二分的方式 let left = 0 let right = nums.length - 1 while (left <= right) { let middle = parseInt((left + right) / 2) if (nums[middle] == target) { //因为没有重复元素，如果找到相同的，那么它的下标就是要插入的下标 return middle } else if (nums[middle] < target) { left = middle + 1 } else { right = middle - 1 } } //因为left==right是成立的 /* 第一次left=0 right=5 middle=2 5>4 所以right=1 第二次left=0 right=1 middle=0 1<4 所以left=middle+1=1 第三次left=1 right=1 middle=1 3<4 所以left=middle+1=2 此后while循环不成立。 因此，如果查找不到的话，while(left<=right) 最后的结果就是left在右侧5 right在左侧3 最后return 可以是left也可以是right+1 */ return left } searchInsert([1, 3, 5, 6, 8, 10], 4) ``` **左闭右开** > 结论：如果在有序列表([left,right))中查找不到指定元素，那么最后 left 和 right 都是偏大的那个元素，因为 right 实际取不到那一个 ```js var searchInsert = function (nums, target) { //最简单的方式肯定是直接遍历 //用二分的方式 let left = 0 let right = nums.length while (left <= right) { let middle = parseInt((left + right) / 2) if (nums[middle] == target) { //因为没有重复元素，如果找到相同的，那么它的下标就是要插入的下标 return middle } else if (nums[middle] < target) { left = middle + 1 } else { right = middle } } //因为left==right是成立的 /* 第一次left=0 right=6 middle=3 6>4 所以right=3 第二次left=0 right=3 middle=1 3<4 所以left=middle+1=1 第三次left=1 right=3 middle=2 5>4 所以right=middle=2 第四次left=1 right=2 middle=1 3<4 所以left=middle+1=2 此后退出while循环 left==right 所以可以选择返回left也可以选择返回right */ return left } searchInsert([1, 3, 5, 6, 8, 10], 4) ``` ### 209.长度最小的子数组 思路 1：暴力法，找出所有的子数组。可惜超时 ```js var minSubArrayLen = function (target, nums) { let res = [] for (let i = 0; i < nums.length; i++) { for (let j = i; j < nums.length; j++) { let temp = nums.slice(i, j + 1) let sum = temp.reduce((pre, item) => (pre += item)) if (sum >= target) { res.push(temp) } } } let min = Infinity res.forEach(arr => { min = Math.min(min, arr.length) }) return min == Infinity ? 0 : min } console.log(minSubArrayLen(11, [1, 2, 3, 4, 5])) ``` 方法二：滑动窗口 一般来说，`子数组问题`，都可以用`滑动窗口`来解决 定义窗口左边界 left=0； 遍历 nums 数组，如果窗口内的和小于 target，i++ 如果大于或等于，那么先进行比较，sum-nums[left],然后 left 边界向右侧移动一位 ```js var minSubArrayLen = function (target, nums) { let left = 0 let sum = 0 let min = Infinity for (let i = 0; i < nums.length; i++) { sum += nums[i] while (sum >= target) { let tempLength = i - left + 1 min = Math.min(tempLength, min) sum -= nums[left] left++ } } return min == Infinity ? 0 : min } minSubArrayLen(4, [1, 2, 3, 4, 5]) ``` ### 59.螺旋矩阵 Ⅱ ```js /* 这题的重点在于不变量，每次循环的时候都要确定是左闭右开。循环结束一次后，就往里面缩一格重新开始遍历 如果n%2==0 那么只需要从外到内循环即可 如果n%2!=0 那么需要给中间额外赋值 */ var generateMatrix = function (n) { //创建数组 let res = new Array(n) for (let i = 0; i < res.length; i++) { res[i] = new Array(n).fill(0) } //loop 循环次数 如果n是奇数，需要中间额外添加 let loop = parseInt(n / 2) let startX = 0 let startY = 0 //定义中间值 let mid = parseInt(n / 2) //count 赋值 let count = 1 //定义的边界缩小值 let offset = 1 let i = startX let j = startY while (loop--) { //每次循环开始的时候，都必须重新定义起点，不然i，j会有问题 i = startX j = startY //从左往右 for (; j < n - offset; j++) { res[i][j] = count++ } //从上往下 for (; i < n - offset; i++) { res[i][j] = count++ } //从右往左 记住 左闭右开 你需要倒过来看 for (; j > startY; j--) { res[i][j] = count++ } for (; i > startX; i--) { res[i][j] = count++ } //一圈结束 startX++ startY++ offset += 1 } if (n % 2 == 1) { res[mid][mid] = count } return res } console.log(generateMatrix(4)) ``` ### 54.螺旋矩阵 这题其实跟螺旋矩阵 Ⅱ 一样，只不过它不在是正方形，所以遍历次数需要先找出最短的那条边，然后/2。根据左开右开进行推入。 难点在于：当最后遍历结束后，如果中间还有，需要判断剩余一行或者一列，这取决于最短那条边。如果宽短，那么剩余的是一行，如果长短，那么剩余一列。然后**将剩余的值推入！推入的时候是左闭右闭！** ```js /* 因为它不一定是正方形，所以循环遍历次数需要找到最小的那条边/2 */ var spiralOrder = function (matrix) { let m = matrix.length let n = matrix[0].length let mini = Math.min(m, n) let loop = parseInt(mini / 2) let startX = 0 let startY = 0 let res = [] let offset = 1 let i = startX let j = startY while (loop--) { i = startX j = startY for (; j < n - offset; j++) { res.push(matrix[i][j]) } for (; i < m - offset; i++) { res.push(matrix[i][j]) } for (; j > startY; j--) { res.push(matrix[i][j]) } for (; i > startX; i--) { res.push(matrix[i][j]) } startX++ startY++ offset++ } //如果mini%2!=0 说明中间会留下一行或者一列 if (mini % 2 != 0) { //这时候必须重新赋值 i = startX j = startY //判断是行还是列 if (mini == m) { //说明是行,这时候把一整行都填进去，注意，这里是左闭右闭了 for (; j < n - offset + 1; j++) { res.push(matrix[i][j]) } } else { //说明是列 for (; i < m - offset + 1; i++) { res.push(matrix[i][j]) } } } return res } console.log(spiralOrder([[3], [2]])) ``` ### 27.移除数组元素 原地移除数组元素，用的是双指针法 slow 代表完成修改的数组末尾，fast 对数组遍历，如果符合条件就放到 slow 下标对应的位置 ```js var removeElement = function (nums, val) { let slow = 0 for (let i = 0; i < nums.length; i++) { if (nums[i] != val) { nums[slow] = nums[i] slow++ } } return slow } ``` ## 链表 **链表为什么要有虚拟头节点？** 因为如果没有虚拟头节点，那么对 head 操作的话，就需要单独写出来。如果有了，那么所有节点就一样的处理了 ### 203.删除链表的指定元素 > 定义 cur 用来循环链表，pre 是前一个节点，如果 cur.val==val，就删除 cur 节点，即让 cur 后移动，如果不相等，那么就指向下一个 类似于反转链表的操作 ```js function ListNode(val, next) { this.val = val === undefined ? 0 : val this.next = next === undefined ? null : next } var removeElements = function (head, val) { let dummy = new ListNode(0, head) let cur = dummy.next let pre = dummy while (cur) { if (cur.val == val) { let next = cur.next pre.next = next cur = next } else { pre = cur cur = cur.next } } return dummy.next } ``` ### [206. 反转链表](https://leetcode.cn/problems/UHnkqh/) **关键：需要断掉最后创造出来的虚拟头节点，最后返回 pre** > 1 -> 2 -> 3 -> 4 -> 5 > > 1 <- 2 <- 3 <- 4 <-5 ```js function ListNode(val, next) { this.val = val === undefined ? 0 : val this.next = next === undefined ? null : next } var reverseList = function (head) { if (!head) return head //因为反转 需要最后一个是null，即代表开头pre要为null。所以需要虚拟头节点 let dummy = new ListNode(null) let pre = dummy let cur = head while (cur) { let next = cur.next cur.next = pre pre = cur cur = next } //最后会多出一个值为null的空节点，需要去除。head就是尾节点 head.next = null return pre } ``` ### [24. 两两交换链表中的节点](https://leetcode.cn/problems/swap-nodes-in-pairs/) 思路： 1--2--3--4 转换 2--1--3--4 再变成 2--1--4--3 需要定义一个 dummy 节点保存整个链表，最后返回 定义 pre 指针 cur=1 next=2 cur.next=next.next //保留 3--4 后面这个链表 然后断开 2 next.next=cur 保存链表 pre.next=next **重点：你需要把转换后的添加到虚拟头节点之后,链接成一个链表** ```js function ListNode(val, next) { this.val = val === undefined ? 0 : val this.next = next === undefined ? null : next } /* 1--2--3--4 2--1--4--3 */ var swapPairs = function (head) { let dummy = new ListNode(0, head) let pre = dummy let cur = head //每次交换两个即跳两步 while (cur && cur.next) { let next = cur.next let next2 = cur.next.next cur.next = next2 next.next = cur pre.next = next pre = cur cur = next2 } return dummy.next } ``` ### 03.链表相交 判断两个链表相交的起始节点 1 2 3 4 5 7 8 9 3 4 5 在 3 这个节点相交 定义两个指针 curA 和 curB，让他们从一定的位置同时开始遍历，遍历到相同点说明相交。 `一定的位置如何获取`？ 计算出两个链表的长度差值，然后让长的那个链表先移动 ```js var getIntersectionNode = function (headA, headB) { let curA = headA let curB = headB //计算出两个链表的长度差值 let lenA = 0 let lenB = 0 while (curA) { lenA++ curA = curA.next } while (curB) { lenB++ curB = curB.next } if (lenA < lenB) { ;[headA, headB] = [headB, headA] ;[lenA, lenB] = [lenB, lenA] } let length = lenA - lenB while (length--) { headA = headA.next } while (headA && headB) { if (headA == headB) { return headA } headA = headA.next headB = headB.next } return headA } ``` ### [141. 环形链表](https://leetcode.cn/problems/linked-list-cycle/) > 环形链表一定用快慢指针来做。而且循环条件一定是while(fast&&fast.next) ```js /* 判断链表中是否有环，使用快慢指针即可 */ var hasCycle = function (head) { let fast = head let slow = head while (fast && fast.next) { //如果有环，那么一定会无限循环下去，fast一定会再次追上slow fast = fast.next.next slow = slow.next if (slow == fast) return true } return false } ``` ### [142. 环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/) ![image-20230507140140052](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20230507140140052.png) 首先需要判断链表中是否有环。这个很简单，用快慢指针，如果有环，快指针等于每次以 1 的速度追慢指针，一定能追上。 难点在于，入环口是哪个节点？ 定义 x 会头节点到入环口距离 定义 y 为 fast 指针与 slow 指针相遇节点 z 为剩余距离 2(x+y)=x+y+n(y+z) //进去以后跑了 n 圈 因此 x=(n-1)(y+z)+z 如果让 n==1 即只跑一圈，那么 x==z 即相遇节点到入口节点等于头节点到入口节点 所以只需要让 fast 重回 head 每次走一步，他和 slow 相遇的时候就是入口 ```js var detectCycle = function (head) { let fast = head let slow = head while (fast && fast.next) { //因为fast需要.next.next 所以必须fast.next存在。 fast = fast.next.next slow = slow.next if (fast == slow) { fast = head while (fast != slow) { fast = fast.next slow = slow.next } return slow } } return null } ``` ### [19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/SLwz0R/) 思路：双指针。定义两个指针 fast 和 head，让 fast 先走 n 步。然后同时走，等到 fast 走到末尾 这时候就是删除链表的某个元素 即删除 slow.next 让 slow.next=slow.next.next 需要定义一个虚拟头节点，因为可能要删除的就是首节点 ```js var removeNthFromEnd = function (head, n) { let dummy = new ListNode(null, head) let fast = head let slow = head while (n--) { fast = fast.next } if (!fast) { return slow.next } /* 为什么需要fast.next存在 因为fast.next最后是fast到了链表最后一个节点 如果没有的话，最后fast会变为了null 1 2 3 4 5 删除 倒数第二个 如果没有fast.next slow指针会变成4 fast会变成null这就不合理了 有的话 slow变成3 fast变成5就退出了循环了，正好删除4 */ while (fast && fast.next) { fast = fast.next slow = slow.next } let next = slow.next.next slow.next = next return dummy.next } ``` ## 哈希表 ### 242.有效的字母异位词 思路：利用数字的方式，存储 26 个字母出现的次数，然后遍历 t 再-- ，如果最后数组中有大于 1 的，就 return false ```js var isAnagram = function (s, t) { let arr = new Array(26).fill(0) for (let i = 0; i < s.length; i++) { let index = s[i].charCodeAt() - 97 arr[index] = arr[index] + 1 } for (let i = 0; i < t.length; i++) { let index = t[i].charCodeAt() - 97 arr[index] = arr[index] - 1 } return arr.every(item => { return item === 0 }) } ``` ### 349.两个数组的交集 ```js /* 思路：先对两个数组进行去重，然后遍历其中一个，判断另外一个数组中是否存在，存在存入res */ var intersection = function (nums1, nums2) { let set1 = new Set(nums1) let set2 = new Set(nums2) let res = [] for (let i of set1) { if (set2.has(i)) { res.push(i) } } return res } ``` ### 202.快乐数 **重点：你每循环一次，res 需要是最新的值，所以最后 res=fn(res)** ```js /* 思路：定义一个函数，计算每个位的平方和。定义一个map存放每一次的值，如果有重复的，那么就说明陷入无限循环了 */ var isHappy = function (n) { let map = new Map() function fn(n) { let result = 0 while (n) { result += (n % 10) ** 2 n = parseInt(n / 10) } return result } //这是第一次的结果 let res = fn(n) //后面进行递归 while (true) { if (map.has(res)) { return false } if (res == 1) { return true } map.set(res, 1) res = fn(res) } } ``` ### 1.两数之和 **重点：这一题的细节在于`首先每个值不能被重复使用`，所以判断是否存在的时候还需要多添加一条下标不能相同。map.get(v)!=i** **2.如果 nums 里是重复的如[1,1] target=2 map 里存放的其实就是{1=>1} 结果也不是重复的 因为 i 是 0，v=1** ```js var twoSum = function (nums, target) { let map = new Map() for (let i = 0; i < nums.length; i++) { map.set(nums[i], i) } for (let i = 0; i < nums.length; i++) { let v = target - nums[i] if (map.has(v) && map.get(v) != i) { return [i, map.get(v)] } } } ``` ### 454.四数相加 **思路：因为可以任取数组中的元素，所以就转化成两数相加。先算两个数组的结果，然后存放到 map 中，最后再计算对应的 target 值。那为什么不需要判断是否是同一元素了呢？傻瓜！本来就是计算的所有元素的两两之和，咋可能元素相同** --- ``` /* 思路：因为可以任取数组中的元素，所以就转化成两数相加。先算两个数组的结果 */ var fourSumCount = function (nums1, nums2, nums3, nums4) { let map = new Map() for (let i = 0; i < nums1.length; i++) { for (let j = 0; j < nums2.length; j++) { let sum = nums1[i] + nums2[j] if (map.has(sum)) { map.set(sum, map.get(sum) + 1) } else { map.set(sum, 1) } } } let res = 0 //再算nums3和nums4的和 for (let i = 0; i < nums3.length; i++) { for (let j = 0; j < nums4.length; j++) { let target = -(nums3[i] + nums4[j]) if (map.has(target)) { res += map.get(target) } } } return res } ``` ### 383.赎金信 **重点！！ `if(undefined<1) 是不会进入条件判断的` ??的作用，如果左边是 undefined 或者是 null，就直接返回右边。否则都是返回左边** ``` var canConstruct = function (ransomNote, magazine) { let mapA = new Map() for (let i = 0; i < ransomNote.length; i++) { if (mapA.get(ransomNote[i])) { mapA.set(ransomNote[i], mapA.get(ransomNote[i]) + 1) } else { mapA.set(ransomNote[i], 1) } } let mapB = new Map() for (let i = 0; i < magazine.length; i++) { if (mapB.get(magazine[i])) { mapB.set(magazine[i], mapB.get(magazine[i]) + 1) } else { mapB.set(magazine[i], 1) } } for (let i of mapA) { let key = i[0] let value = i[1] if ((mapB.get(key) ?? 0) < value) { return false } } return true } ``` ### 15.三数之和 思路：找出数组中的三个元素，需要满足和为 0，所以三指针法。-1 -1 1 1 3 5。 这题的重点在于去重: 为什么是 nums[i]==nums[i-1]呢，因为 j 是 i+1 如果改成 nums[i]==nums[i+1]那么就代表了 i 与 j 也不能不同，但实际是可以相同的 ```js var threeSum = function (nums) { let result = [] nums.sort((a, b) => a - b) for (let i = 0; i < nums.length; i++) { if (nums[i] == nums[i - 1]) continue let left = i + 1 let right = nums.length - 1 while (left < right) { let sum = nums[i] + nums[left] + nums[right] if (sum == 0) { while (nums[left] == nums[left + 1]) { left++ } while (nums[right] == nums[right - 1]) { right-- } result.push([nums[i], nums[left], nums[right]]) left++ right-- } else if (sum < 0) { left++ } else { right-- } } } return result } ``` ### 18.四数之和 四数之和其实和三数之和很相似，就是四指针而已。 重点：第二个指针 j 跳过的时候，必须额外携带一个条件 j>i+1。因为 1 1 1 4 5 i==0 j=i+1 nums[j]也是 1 这种情况 nums[j]==nums[j-1]，但是 nums[j-1]是 nums[i],是满足的，无需跳 而当 j==2 的时候，这时候 nums[j]==nums[j-1]&&j>i+1 可以跳了。 ```js var fourSum = function (nums, target) { let result = [] nums.sort((a, b) => a - b) for (let i = 0; i < nums.length; i++) { if (nums[i] == nums[i - 1]) continue for (let j = i + 1; j < nums.length; j++) { if (nums[j] == nums[j - 1] && j > i + 1) continue let left = j + 1 let right = nums.length - 1 while (left < right) { let sum = nums[i] + nums[j] + nums[left] + nums[right] if (sum < target) { left++ } else if (sum > target) { right-- } else { while (nums[left] == nums[left + 1]) { left++ } while (nums[right] == nums[right - 1]) { right-- } result.push([nums[i], nums[j], nums[left], nums[right]]) left++ right-- } } } } return result } ``` ## 字符串 ### 344.反转字符串 反转字符串主要两种方法 - 首先通过 split()将字符串分割为数组，然后通过 reverse()再拼接。 - 通过双指针法，进行交换 ```js 双指针法: 注意，left++ right--别写在交换里面 var reverseString = function (s) { s = s.split('') let left = 0 let right = s.length - 1 while (left < right) { ;[s[left], s[right]] = [s[right], s[left]] left++ right-- } console.log(s) } reverseString('abecd') ``` ### 541.反转字符串 Ⅱ ```js /* 每次计数2k 所以 i+=2k。 只需要判断剩余长度是否小于k，如果小于k就全部反转，如果>=k 就反转到k个的 */ var reverseStr = function (s, k) { s = s.split('') for (let i = 0; i < s.length; i += 2 * k) { //需要反转的字符串区域 let left = i //大于代表剩余的字符数量小于k。只需要把字符串剩余的全部反转即可。如果大于，反转k个即可 //注意下标 i==0 k==2 需要反转的是前两个 下标为0，1 let right = i + k >= s.length ? s.length - 1 : i + k - 1 while (left <= right) { ;[s[left], s[right]] = [s[right], s[left]] left++ right-- } } return s.join('') } ``` ### 3.无重复字符的最长子串 重点： map.get(s[i]>=left)只是为了保证边界不回退而已。 每次还是需要依赖当前 left 重新计算长度 ```js var lengthOfLongestSubstring = function (s) { let resLength = 0 let map = new Map() let left = 0 for (let i = 0; i < s.length; i++) { if (!map.has(s[i])) { map.set(s[i], i) //这是为了避免没有重复字符的 resLength = Math.max(resLength, i - left + 1) } else { //这里有个细节在于 map.get(s[i])必须大于之前的left，不然会导致回退 if (map.get(s[i]) >= left) { left = map.get(s[i]) + 1 //这个只是为了确保边界不会回退 } resLength = Math.max(resLength, i - left + 1) map.set(s[i], i) } } return resLength } lengthOfLongestSubstring('abcadcbb') ``` ### 151.反转字符串中的单词 ```js 方法一、通过split方法，拆分字符串，然后遍历去除掉所有空格，最后反转拼接' ' let arr = s.split(" "); let newRes = []; //通过一个新数组存放。 for (let i = 0; i < arr.length; i++) { if (arr[i].length) { newRes.push(arr[i]); } } return newRes.reverse().join(" "); ``` ## 二叉树 ### 理论基础 二叉树的遍历方式总体就分为两种：深度优先遍历 dfs，广度优先遍历 bfs 深度优先遍历分两种：① `递归法`(前序遍历、中序遍历、后序遍历)② 迭代法(用栈的方式) 广度优先遍历(即层序遍历)：① 只有`迭代法`(队列) 前序、中序、后序的递归法很简单，这里就不介绍了，主要演示迭代法的前序(中序后序需要用指针，递归就够了) #### **迭代法实现前序遍历：** **重点：`必须判断左右子节点存在才推入栈中`。** > 假如没有判断，node 的左右子节点不存在直接推入栈，stack 会推入 undefined。length 也为 1，undefined.xx 也自然会报错 ```js function preOrderByStack(root) { if (!root) return [] let res = [] let stack = [root] while (stack.length) { let node = stack.pop() res.push(node.val) if (node.right) { stack.push(node.right) } if (node.left) { stack.push(node.left) } } return res } preOrderByStack(tree) ``` **层序遍历：如果用一个数组来存放层序遍历的结果，那么加入父节点的数组下标是 i，左孩子节点是 `i*2+1`、右孩子是 `i*2+2` ** ![image-20230727095946995](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20230727095946995.png) ![image-20230727101856023](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20230727101856023.png) ![image-20230727101917251](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20230727101917251.png) ### 层序遍历 即广度优先遍历，需要借助队列来实现 bfs所有路径 **不含有 null 节点：** 如果是直接弹出的，那么`左右子节点需要判断是否存在`才推入队列 如果不判断，`node.left不存在` ，队列：[undefined]，弹出 undefined，undefined.val 报错 所以判断以后，那么`保证每次弹出的node就必定存在` ![image-20240709150004877](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20240709150004877.png) ```js function bfs(root) { if (!root) return let result = [] let queue = [root] while (queue.length) { let len = queue.length result.push([]) //每一次的for循环代表一层的结束 for (let i = 0; i < len; i++) { let node = queue.shift() result[result.length - 1].push(node.val) if (node.left) { queue.push(node.left) } if (node.right) { queue.push(node.right) } } } console.log(result) } ``` **含有 null** 因为最后结果要含有 null 或者 undefined 节点，所以需要对弹出来的 node 进行判断 如果`当前节点不存在`了即 undefined，就 push(null)，如果当前节点 node 存在，就把`左右子节点推入队列`。 ![image-20240709145938441](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20240709145938441.png) ```js function bfs(root) { if (!root) return [] let res = [] let queue = [root] while (queue.length) { res.push([]) let len = queue.length for (let i = 0; i < len; i++) { let node = queue.shift() if (node) { res[res.length - 1].push(node.val) queue.push(node.left) queue.push(node.right) } else { res[res.length - 1].push(null) } } } console.log(res) } bfs(tree) ``` **总结：不含 null：它是对`左右子节点判断是否存在`，从而推入队列当中，这样可以保证`队列中的永远存在`。含有 null：它是对弹出来的 node 判断，如果存在，就将左右子节点推入队列，(左右子节点可能不存在)，如`果不存在就用null来填充`** #### 107.二叉树的层序遍历 Ⅱ > 返回自底向上的层序遍历。思路：只需要正常层序遍历，获取每一层，然后反转数组即可 **重点：如果不存在的话，需要直接返回空数组，不能直接返回 root，算例题的一个小 bug 吧** ```js var levelOrderBottom = function (root) { //因为最后是需要反转，所以不存在也是返回一个空数组 if (!root) return [] function bfs(root) { let res = [] let queue = [root] while (queue.length) { res.push([]) let len = queue.length for (let i = 0; i < len; i++) { let node = queue.shift() /* 无需含有null */ res[res.length - 1].push(node.val) if (node.left) { queue.push(node.left) } if (node.right) { queue.push(node.right) } } } return res } let arr = bfs(root) return arr.reverse() } ``` #### [LCR 046. 二叉树的右视图](https://leetcode.cn/problems/WNC0Lk/) > 思路：层序遍历获取每一层，然后把数组尾部元素取出即可,无需含有 null ```js var rightSideView = function (root) { if (!root) return [] function levelOrder(root) { let res = [] let queue = [root] while (queue.length) { let len = queue.length res.push([]) for (let i = 0; i < len; i++) { let node = queue.shift() res[res.length - 1].push(node.val) if (node.left) { queue.push(node.left) } if (node.right) { queue.push(node.right) } } } return res } let arr = levelOrder(root).map(item => { return item[item.length - 1] }) return arr } ``` #### 637.二叉树的层平均值 > 思路很简单，依然是层序遍历获取每一层，然后计算出平均值即可 ```js var averageOfLevels = function (root) { let result = [] function levelOrder(root) { let res = [] let queue = [root] while (queue.length) { res.push([]) let len = queue.length for (let i = 0; i < len; i++) { let node = queue.shift() res[res.length - 1].push(node.val) if (node.left) { queue.push(node.left) } if (node.right) { queue.push(node.right) } } } return res } let res = levelOrder(root) result = res.map(arr => { return ( arr.reduce((pre, item) => { return (pre += item) }, 0) / arr.length ) }) return result } ``` #### 429.N 叉树的层序遍历 > N 叉树的层序遍历其实和二叉树的层序遍历原理是一致的，都是用队列迭代法，二叉树是判断左右子节点是否存在，如果存在就将左右子节点推入队列当中。N 叉树也是，判断其 children 数组是否存在，如果存在就依次推入队列中。可以把二叉树理解为 children.length==2 的 N 叉树 ```js var levelOrder = function (root) { if (!root) return [] function bfs(root) { let res = [] let queue = [root] while (queue.length) { let len = queue.length res.push([]) for (let i = 0; i < len; i++) { let node = queue.shift() res[res.length - 1].push(node.val) let children = node.children || [] for (let i = 0; i < children.length; i++) { queue.push(children[i]) } } } return res } return bfs(root) } ``` #### **[116. 填充每个节点的下一个右侧节点指针](https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/)** > 思路 ①：层序遍历出每一层，然后通过 createTree 方式将每一层得到的数组转化为树形结构，最后拼接。但是这种方式不行，因为需要在原来的树上进行操作 ```js var connect = function (root) { function levelOrder(root) { if (!root) return [] let queue = [root] let res = [] while (queue.length) { let len = queue.length res.push([]) for (let i = 0; i < len; i++) { let node = queue.shift() res[res.length - 1].push(node) if (node.left) { queue.push(node.left) } if (node.right) { queue.push(node.right) } } } return res } let res = levelOrder(root) /* 这种思路不行：因为你这是创建了一个新的树，要求是从原来的树中进行改造 */ function createTree(arr) { let root = { val: arr[arr.length - 1], next: null } for (let i = arr.length - 2; i >= 0; i--) { root = { val: arr[i], next: root } } return root } } ``` > 思路 ② 依然是层序遍历获取每一层值，但是遍历到每一层的时候，判断它是否是第一个，如果是第一个，就临时记录，如果有第二个，就让它指向第二个。最后每一层遍历结束后，再让结尾那个节点指向 null ```js var connect = function (root) { function levelOrder(root) { if (!root) return root let queue = [root] let pre = null while (queue.length) { let len = queue.length let pre = null for (let i = 0; i < len; i++) { let node = queue.shift() if (i == 0) { pre = node } else { pre.next = node pre = node } if (node.left) { queue.push(node.left) } if (node.right) { queue.push(node.right) } } pre.next = null } return root } return levelOrder(root) } ``` #### [104. 二叉树的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/) > 返回根节点到最远叶子节点的深度，放在层序遍历里，很简单，只需要层序遍历获取最后 res.length 即可，但是还有另外一种方式 **即 `二叉树的深度getDepth`** ```js /** * @description 传入某一节点，返回当前节点的最大深度 * @param */ var maxDepth = function (root) { if (!root) return 0 return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 } ``` #### [111. 二叉树的最小深度](https://leetcode.cn/problems/minimum-depth-of-binary-tree/) > 这题稍微比二叉树的最大深度复杂一点，也是层序遍历每一层的节点，遍历每一层 depLength++，如果`当前节点没有了左右子节点`，那么就说明它是最小深度的那一层，直接返回 ```js var minDepth = function (root) { function levelOrder(root) { if (!root) return 0 let queue = [root] let depLength = 0 while (queue.length) { let len = queue.length depLength++ for (let i = 0; i < len; i++) { let node = queue.shift() if (!node.left && !node.right) { return depLength } if (node.left) { queue.push(node.left) } if (node.right) { queue.push(node.right) } } } } return levelOrder(root) } ``` #### 226.翻转二叉树 > 这题的思路很简单，只需要先序遍历每一个节点，然后交换其左右子节点即可。 ```js var invertTree = function (root) { function preOrder(root) { if (!root) return let temp = root.left root.left = root.right root.right = temp preOrder(root.left) preOrder(root.right) } preOrder(root) return root } ``` #### 637.二叉树的层平均值 > 也是层序遍历出每一层结果，然后对每一层结果进行操作即可 ```js var averageOfLevels = function (root) { let result = [] function levelOrder(root) { let res = [] let queue = [root] while (queue.length) { res.push([]) let len = queue.length for (let i = 0; o < len; i++) { let node = queue.shift() res[res.length - 1].push(node.val) if (node.left) { queue.push(node.left) } if (node.right) { queue.push(node.right) } } } return res } let res = levelOrder(root) result = res.map(item => { return item.reduce((pre, i) => (pre += item), 0) / item.length }) console.log(result) } ``` #### 110.平衡二叉树 > 平衡二叉树：左右子树的高度差小于等于 1。 > > 思路：遍历每个节点，通过 getDepth 获取其左右子树的高度，然后判断差值 ```ts var isBalanced = function (root) { if (!root) return true let flag = true function preOrder(root) { if (!root) return let left = getDepth(root.left) let right = getDepth(root.right) if (Math.abs(left - right) > 1) { return (flag = false) } preOrder(root.left) preOrder(root.right) } preOrder(root) return flag function getDepth(root) { if (!root) return 0 return Math.max(getDepth(root.left), getDepth(root.right)) + 1 } } ``` #### 513.找树左下角的值 > 这题很简单，只需要层序遍历，获取最后一层的第一个元素即可 ```ts var findBottomLeftValue = function (root) { if (!root) return 0 function levelOrder(root) { let res = [] let queue = [root] while (queue.length) { res.push([]) let len = queue.length for (let i = 0; i < len; i++) { let node = queue.shift() res[res.length - 1].push(node.val) if (node.left) { queue.push(node.left) } if (node.right) { queue.push(node.right) } } } return res } let res = levelOrder(root) return res[res.length - 1][0] } ``` ### [257. 二叉树的所有路径](https://leetcode.cn/problems/binary-tree-paths/) > - **dfs** 或者是层序遍历获取每一层的值 > `终止条件是当前节点cur不为空，且左右子节点为空` ```js if (!root.left && !root.right) ``` - preOrder写法：即`组合写法，初始值包含root`。(注意，**path里需要包含root.val**！！！因为`遍历是遍历第一层`) 因为是遍历所有路径，所以是遍历一棵树，就无需返回值。 **确定遍历范围，因为是二叉树，所以遍历范围只有左右子节点** ```js var binaryTreePaths = function (root) { const result = [] function preOrder(cur, path) { //终止条件 当前节点为子节点 if (!cur.left && !cur.right) { return result.push([...path]) } //确定集合范围。因为是二叉树，所以要保证递归的节点存在 if (cur.left) { path.push(cur.left.val) preOrder(cur.left, path) path.pop() } if (cur.right) { path.push(cur.right.val) preOrder(cur.right, path) path.pop() } } preOrder(root, [root.val]) return result } ``` 因此后面进入递归的条件就是`保证cur节点不为空`，所以`需要if判断保证进入dfs的cur节点不为空` - [bfs](#bfs所有路径) bfs层序遍历分两种，一种是不含null的，一种是含有null的。含有null是判断当前节点是否存在，不存在推入null。不含null的是判断要推入队列的左右子节点是否存在，`保证推入queue队列的节点都是存在的`。(类似于dfs) ​ ### [404. 左叶子之和](https://leetcode.cn/problems/sum-of-left-leaves/) > 这题求的是左叶子节点的和，不是二叉树的左侧节点，所以不能直接用层序遍历。 ```js /* 注意： 左叶子节点：根节点的左孩子不为空，左孩子节点的左右子节点为空 所以需要先找出所有的左孩子，然后判断其是否为叶子节点即可 */ var sumOfLeftLeaves = function (root) { let sum = 0 function preOrder(root, isLeft) { if (!root) return if (!root.left && !root.right) { if (isLeft) { sum += root.val } } preOrder(root.left, true) preOrder(root.right, false) } preOrder(root, false) return sum } ``` ### 递归一条边||一棵树 **当需要递归一棵树的时候，递归函数就不需要返回值。它可以保存所有的递归结果。** **递归`一条边`本质上是对`递归一棵树的剪枝`，只需要找到一个对应结果，就直接返回，一般返回boolean值** #### 112.路径总和 **找出所有路径，然后判断是否有路径的sum值成为target，因此只需要有一条边满足条件即可，** [遍历一条边](#遍历一条边) 当然，也可以遍历一棵树，找出所有路径，然后遍历路径，判断是否满足条件。 > 路径总和Ⅱ：说白了就是找出所有路径判断值是否为target。**** > > ​ 思路：dfs找出所有路径。 > > ```js > var hasPathSum = function (root, targetSum) { > let result = [] > if (!root) return [] > function preOrder(cur, path) { > if (!cur.left && !cur.right) { > return result.push([...path]) > } > if (cur.left) { > path.push(cur.left.val) > preOrder(cur.left, path) > path.pop() > } > if (cur.right) { > path.push(cur.right.val) > preOrder(cur.right, path) > path.pop() > } > } > preOrder(root, [root.val]) > console.log(result) > } > ``` > > ​ 终止条件 即叶子节点。需要当前节点存在且左右子节点不存在 > > ​ 如何让当前节点存在，很简单，每次进入dfs前都判断，只有存在才能dfs ```js /* 思路1：找出二叉树的所有路径，然后求和判断是否等于targetSum */ var hasPathSum = function (root, targetSum) { let flag = false if(!root) return false function preOrder(root, path) { if (!root.left && !root.right) { let sum = path.reduce((pre, item) => (pre += item)) if (sum == targetSum) { return (flag = true) } } if (root.left) { path.push(root.left.val) preOrder(root.left, path) path.pop() } if (root.right) { path.push(root.right.val) preOrder(root.right, path) path.pop() } } preOrder(root, [root.val]) return flag } ``` **思路②：`遍历一条边，即有返回值`** > 其实遍历一条边的本质上，是遍历一棵树的剪枝操作 > 即只要搜索到一条符合条件的路径，就直接返回。**不需要找到所有路径**，那么就`需要返回值` 一般来说，找一条符合条件的路径，返回值用boolean值即可，这样只需要遍历到一条边满足条件了，就直接return。 ![image-20230914112341737](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20230914112341737.png) - 终止条件：左右子节点不存在，且sum==targetSum return true 。`遍历一条边会多一种终止条件`，即该边不符合，那么当遍历到叶子节点时，return false。即进行`剪枝操作` - 确定单层节点遍历逻辑，即集合范围。**注意：因为是二叉树的递归，所以我们可以保证每次递归的节点都存在。即if(cur.left){preOrder()}。** **因为`递归函数有返回值`，如果其返回true，说明找到了合适的路径，一直往上回溯即可** **只要有一条边的叶子节点满足条件，return true，那么它上一层的递归函数就会直接`return true`** **注意一个细节：sum必须要有默认值，`即root根节点`。因为它每次遍历都是从左右子节点开始的** ```js var hasPathSum = function (root, targetSum) { function backTracking(root, sum) { //找到那条边 if (!root.left && !root.right && sum == targetSum) { return true } if (root.left) { if (backTracking(root.left, sum + root.left.val)) return true } if (root.right) { if (backTracking(root.right, sum + root.right.val)) return true } //遍历完所有边，不满足条件 return false,如果不return false最后是undefined //遍历完所有边，如果没有一条边满足条件进入不了无法return true ，会return undefined因此最后添加一个return false return false } console.log(backTracking(root, root.val)) return backTracking(root, root.val) } ``` #### **113.路径总和Ⅱ ** **一般来说，遍历一棵树，都是有多种结果** `写法Ⅱ：类似于组合的写法了`，先写终止条件，**即当前节点为叶子节点**，再遍历其左右子节点。`但也因此会跳过root节点` ，必须把**初始值root.val**放进去。 > `求和问题完全可以通过path.reduce来求，没必要放在递归里，这样可以保证不会回溯错误` ```js var pathSum = function (root, targetSum) { if (!root) return [] let result = [] function preOrder(root, path) { if (!root.left && !root.right) { let sum = path.reduce((pre, item) => (pre += item)) if (sum == targetSum) { return result.push([...path]) } } if (root.left) { path.push(root.left.val) preOrder(root.left, path) path.pop() } if (root.right) { path.push(root.right.val) preOrder(root.right, path) path.pop() } } preOrder(root, [root.val]) return result } ``` #### [437. 路径总和 III](https://leetcode.cn/problems/path-sum-iii/) > 注意：不是从根节点开始，是任意一个节点和等于目标和。 > > 思路：先序遍历每个节点，每个节点深度遍历，只要和==targetSum，就直接推入res > > **重点：不能用res推入路径， 因为有的路径1 -2 满足 但还有 1 -2 1 -2这种完整的路径** ```js let tree = { val: 1, left: { val: -2, left: { val: 1, left: { val: -1 } }, right: { val: 3 } }, right: { val: -3, left: { val: -2 } } } var pathSum = function (root, targetSum) { if (!root) return 0 let count = 0 function preOrder(root) { if (!root) return backTracking(root, [root.val], root.val) preOrder(root.left) preOrder(root.right) } preOrder(root) console.log(count) //[1,-2] [-2,1] [-1] 因为找到路径就return了,所以还有一个 1 -2 -2 1路径没找到 function backTracking(root, path, sum) { if(!root) return if (sum == targetSum) { count++ } if (root.left) { path.push(root.left.val) backTracking(root.left, path, sum + root.left.val) path.pop() } if (root.right) { path.push(root.right.val) backTracking(root.right, path, sum + root.right.val) path.pop() } } } //简单写法 var pathSum = function (root, targetSum) { let count = 0 function preOrder(root) { if (!root) return null backTracking(root, root.val) preOrder(root.left) preOrder(root.right) } preOrder(root) return count //每个节点作为根节点计算路径和 function backTracking(root, sum) { if (!root) return if (sum == targetSum) { //注意，不是到叶子节点的路径和，是中途所有的短路径 count++ } if (root.left) { backTracking(root.left, sum + root.left.val) } if (root.right) { backTracking(root.right, sum + root.right.val) } } } ``` #### [236. 二叉树的最近公共祖先](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/) > 这道题最重要也是能想到的，如果能`自底向上`查找就好了(即回溯)，而后序遍历则是天然的回溯，可以根据左右节点的返回值，来处理中节点的逻辑。 **遍历一条边** > 遍历一条边最重要的是要有返回值。常用于 `后序遍历`这样就能保存当前节点的左右子节点 **首先，理解下后序遍历的返回值** ```js let tree = { val: 1, left: { val: 2, left: { val: 4 }, right: { val: 5 } }, right: { val: 3, right: { val: 7 } } } /* 后序遍历处理中节点逻辑 */ function postOrder(root) { //root遍历到的节点 if (!root) return null //保存的左右子节点 let left = postOrder(root.left) let right = postOrder(root.right) //这个left是保存的是当前root节点的左子树的返回值！！！ if (root.val == 2) { console.log(left) //即节点4 } return root } postOrder(tree) ``` ![image-20230821163304434](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20230821163304434.png) **这样，后序遍历就有一个极大的作用，可以保存节点的左右子节点,并且c'n `前提是你每次递归的时候，最后都得把当前节点返回`** ```ts var lowestCommonAncestor = function (root, p, q) { function postOrder(root) { //如果当前节点遍历到了p，q直接返回 if (root == p || root == q || !root) return root let left = postOrder(root.left) let right = postOrder(root.right) //后序遍历想要left、right有值，必须return 一个节点 if (left && right) { return root } if (left) { return left } if (right) { return right } //当前节点没有满足的的子树没有满足条件的 直接return null return null } return postOrder(root) } ``` **这样，后序遍历就有一个极大的作用，可以保存该节点的左右子节点 `前提是你每次递归的时候，都得把当前节点返回`** #### [124. 二叉树中的最大路径和](https://leetcode.cn/problems/binary-tree-maximum-path-sum/) ```js /* 思路：因为路径和=左子树的最大路径和+右子树的最大路径和+root.val 因此，我们需要知道左右子树的最大路径和，这就跟二叉树的最近公共祖先一样，我们需要从下往上遍历 因此，用后序遍历 */ var maxPathSum = function (root) { let maxSum = root.val function postOrder(root) { //如果节点不存在 return 0 if (!root) return 0 //返回的是左右子节点的经过计算的最大路径和 let leftSum = postOrder(root.left) let rightSum = postOrder(root.right) //找出当前节点的最大路径和 左+根+右 maxSum = Math.max(maxSum, leftSum + rightSum + root.val) //返回当前节点的左或者右的最大路径和，以父节点使用 或者都不取 let returnMaxSum = Math.max(leftSum, rightSum) + root.val return returnMaxSum > 0 ? returnMaxSum : 0 } } ``` ### 构建二叉树 #### [106. 从中序与后序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/) (0,mid) 构建思路：从后序或者前序遍历，找出`根节点`，然后到中序遍历中找出左右子树 > ```ts > inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] > ``` > > 从后序遍历中，得出根节点[3] 再从中序遍历得出根节点的左子树[9] 右子树[15,20,7] > > 右子树三个节点放入后序遍历得出，根节点是[20] 再放入中序得出左右子节点[15] [7] ```js var buildTree = function (inorder, postorder) { //递归是为了找出每一个根节点 if (!inorder.length) return null let root = { val: postorder[postorder.length - 1], left: null, right: null, } //找出根节点位置，从而找出左右子树进入下一次递归 //中序[9] [15,20,7] 后序是[9] [15,7,20] let mid = inorder.indexOf(root.val) root.left = buildTree(inorder.slice(0, mid), postorder.slice(0, mid)) root.right = buildTree(inorder.slice(mid + 1), postorder.slice(mid, postorder.length - 1)) return root } ``` #### [105. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/) (1,mid+1) > ```ts > preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] > ``` > > 找出根节点[3] 从中序得出左子树[9] 右子树[15,20,7] 右子树放入前序遍历中查看，得出根节点[20] 左右子节点[15],[7] > > 从preOrder中可以得出，3是根节点，那么9一定是左子节点，所以`左子树只需要把下一个包含进去就可以了`，因此preOrder从1开始 ```ts var buildTree = function (preorder, inorder) { if (!inorder.length) return null //定义根节点 let root = { val: preorder[0], left: null, right: null } let mid = inorder.indexOf(root.val) //根节点3，mid=1 先序遍历的左子树为9即(1,mid+1) 中序遍历左右子树为9为(0,mid) root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid)) root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1)) return root } ``` #### [654. 最大二叉树](https://leetcode.cn/problems/maximum-binary-tree/) > 思路：这题也是构建二叉树，所以思路类似于前中序构建二叉树，而且还更简单，只需要通过一个nums数组就能确定左右序列 > > 首先每次找出数组中的最大值，构建出根节点，左子树永远是0到maxIndex，右子树也永远是maxIndex+1到子序列结尾 比如 [3,2,1,6,0,5]，最大值 `6` , `maxIndex=3` 左子树(0,3)序列[3,2,1] 右子树(4到结尾)[0,5] 然后左子树再次进入buildTree,最大值 `3`,maxIndex=0，它的右子树序列就是[2,1]，也依然是maxIndex+1到子序列结尾 **注意**：这种构建树的题目，`终止条件一定要return null`，直接`return undefined会报错.`.. ```js var constructMaximumBinaryTree = function (nums) { const buildTree = (arr) => { if (!arr.length) return null let maxIndex = -1 let maxValue = -1 for (let i = 0; i < arr.length; i++) { if (arr[i] > maxValue) { maxValue = arr[i] maxIndex = i } } let root = new TreeNode(maxValue) root.left = buildTree(arr.slice(0, maxIndex)) root.right = buildTree(arr.slice(maxIndex + 1)) return root } return buildTree(nums) } ``` ```js 思路二：不用裁剪数组，每次都找出left和right也可以。其实和裁剪数组一样，只不过没裁剪数组方便 var constructMaximumBinaryTree = function (nums) { function buildTree(nums, left, right) { //注意 终止条件必须是return null undefined貌似会报错 if (left > right) return null let maxValue = -1 let maxIndex = -1 //基于left和right找出数组中的最大值 for (let i = left; i <= right; i++) { if (nums[i] > maxValue) { maxValue = nums[i] maxIndex = i } } let root = new TreeNode(maxValue) root.left = buildTree(nums, left, maxIndex - 1) root.right = buildTree(nums, maxIndex + 1, right) return root } return buildTree(nums, 0, nums.length - 1) } ``` #### [617. 合并二叉树](https://leetcode.cn/problems/merge-two-binary-trees/) > 思路：这题其实也是构建二叉树。还更简单点，只需要递归树1，然后同时递归树2对应节点即可，并且根节点值只需要相加。 > > 终止条件：如果树1节点不存在，可以直接返回树2。如果树2节点不存在，直接返回树1，因为它要知道递归的那个节点嘛 ```js var mergeTrees = function (root1, root2) { if (!root1 && !root2) return null //这个可写可不写，因为root1不存在了直接返回了root2了 if (!root1) return root2 if (!root2) return root1 root1.val = root1.val + root2.val root1.left = mergeTrees(root1.left, root2.left) root1.right = mergeTrees(root1.right, root2.right) return root1 } ``` ### 二叉搜索树 **二叉搜索树的最大特性: `左子树的值永远小于根节点，右子树的值永远大于根节点，且中序遍历是一个递增序列`** #### [96. 不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees/) > - 定义dp数组和下标含义： dp[i] 表示以i个节点构成的不同二叉搜索树的个数 > > - 状态转移方程： > > 总节点个数i，根节点用了一个节点，那么左子树用0个，右子树用i-1-0 ,然后左右子树个数相乘。 > > 同理，左子树用1个，右子树用i-1-1个 > > dp[i]=dp[0]*dp[i-0-1]+dp[1] * dp[i-1-1] + .. +dp[i-1] *dp[i-1-(i-1)] > > dp[i] +=dp[j]*dp[i-j-1] > > - 初始化dp数组 > > dp[0]=dp[1]=1 ```js var numTrees = function (n) { let dp = new Array(n + 1).fill(0) dp[0] = dp[1] = 1 for (let i = 2; i <= n; i++) { for (let j = 0; j < i; j++) { dp[i] += dp[j] * dp[i - j - 1] } } return dp[dp.length - 1] } ``` #### 700.二叉搜索树中的搜索 **注意：如果不用res保存root，那么每次preOrder都必须return，不然是没有返回值的** ```js var searchBST = function (root, val) { let res = null function preOrder(root, val) { if (!root) return null if (root.val == val) return (res = root) if (root.val < val) { preOrder(root.right, val) } if (root.val > val) { preOrder(root.left, val) } } preOrder(root, val) return res } ``` #### 98.验证二叉搜索树 这题有个陷阱，不能只通过左节点小于根节点，右节点大于根节点。会有这种情况 ![image-20230821155805669](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20230821155805669.png) 正确解法：中序遍历，判断是否是递增子序列 ```js var isValidBST = function (root) { let res = [] let flag = true function inOrder(root) { if (!root) return null inOrder(root.left) res.push(root.val) inOrder(root.right) } inOrder(root) for (let i = 1; i < res.length; i++) { if (res[i] <= res[i - 1]) { return (flag = false) } } return flag } ``` #### 530.二叉搜索树的最小绝对差 **这题也很简单，只需要中序遍历得出递增数组，然后相邻的值计算出最小即可** ```js var getMinimumDifference = function (root) { let res = [] function inOrder(root) { if (!root) return null inOrder(root.left) res.push(root.val) inOrder(root.right) } inOrder(root) let min = Infinity for (let i = 1; i < res.length; i++) { let cha = Math.abs(res[i] - res[i - 1]) if (min >= cha) { min = cha } } return min } ``` #### [501. 二叉搜索树中的众数](https://leetcode.cn/problems/find-mode-in-binary-search-tree/) > 这题只需要记住一个细节，如果有相同的需要返回一个数组，这需要一定的操作 ```js var findMode = function (root) { let inArray = [] function inOrder(root) { if (!root) return null inOrder(root.left) inArray.push(root.val) inOrder(root.right) } inOrder(root) let map = new Map() for (let i = 0; i < inArray.length; i++) { if (map.has(inArray[i])) { map.set(inArray[i], map.get(inArray[i]) + 1) } else { map.set(inArray[i], 1) } } //判断是否有重复的，最后返回一个数组 let res = [] let maxCount = 0 for (let [key, value] of map) { if (value > maxCount) { res = [] maxCount = value res.push(key) } else if (value == maxCount) { res.push(key) } } return res } ``` #### [701. 二叉搜索树中的插入操作](https://leetcode.cn/problems/insert-into-a-binary-search-tree/) > 思路：这题其实没那么可怕，和二叉搜索树查找val值一样。(右子树只需要大于当前节点的根节点，并不是树节点的根节点) > > 利用二叉搜索树的性质，找到空值时，根据记录的父节点的值，进行判断插入 ```ts var insertIntoBST = function (root, val) { if (!root) return new TreeNode(val) let parentNode = new TreeNode(0) function preOrder(root) { //前序遍历 根左右 if (!root) { //找到了空位 let node = new TreeNode(val) if (parentNode.val < node.val) { parentNode.right = node } else { parentNode.left = node } return null } //注意啊，这个parentNode必须写在if(root==null)后面，不然没法记录了... //其次，插入完成后，必须直接return掉，不然null.val会报错 parentNode = root if (root.val < val) { preOrder(root.right) } if (root.val > val) { preOrder(root.left) } } preOrder(root) return root } ``` ## 回溯 **回溯是递归的产物，只要`有递归就会有回溯`(一般来说，回溯函数指的就是递归函数)** **回溯的本质 `是穷举`，穷举所有可能，如果想让回溯高效，那就添加剪枝操作,即if(){return }** > 回溯法可解决的问题（因为本质是穷举，所以对字符串组合排序问题很好用,即`找出所有的组合`。而一般求个数求满足用的是动态规划） > > - 组合问题：N个数按照一定规则找k个数的集合 > - 切割问题：一个字符串按照一定规则有几种切割方式 > - 子集问题：一个N个数的集合里有多少种符合条件的子集 > - 排列问题：N个数按照一定规则全排列，有几种方式 > - 棋盘问题：N皇后等等 **注意：组合无序，排列有序** **回溯法解决的问题都可以`抽象为树形结构`，因此，回溯法解决方法都是在集合中递归查找子集，集合的大小构成了树的宽度，递归的深度构成树的深度。** **回溯法模板** - 回溯函数终止条件 ```js if(终止条件){ 存放结果; return } ``` - 确定本层元素。递归下一层元素。回溯 ``` for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } ``` ### 组合问题 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。 第一时间，如果k=2，那么很简单只需要双重for循环即可。k=3就三重for循环但如果k=100...那就g > 思路：组合问题用回溯，回溯就需要抽象成`树形结构`。 **注意：数是不能重复的，所以每次递归的子集必须是从下一个元素开始。因此需要记录start** ![image-20230822102526635](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20230822102526635.png) - 终止条件 存放结果的path数组.length==k即终止 - for循环条件 每次从start开始，循环集合，用path存放循环到的节点 ```js var combine = function (n, k) { let path = [] let res = [] let startIndex = 1 function backTracking(path, startIndex) { if (path.length == k) { return res.push([...path]) } for (let i = startIndex; i <= n; i++) { path.push(i) backTracking(path, i + 1) path.pop() } } backTracking(path, startIndex) return res } //写法② var combine = function (n, k) { let res = [] let path = [] function backTacking(path, startIndex) { if (path.length == k) { return res.push([...path]) } for (let i = startIndex + 1; i <= n; i++) { path.push(i) backTacking(path, i) path.pop() } } backTacking(path, 0) return res } ``` **注意区分这个和二叉树所有路径的区别** > 二叉树dfs找寻所有路径 : > > 它的终止条件：当前节点不为空，且`左右子节点都要为空`(当前节点为空就可以通过左右子节点是否存在来满足)。 > > 为了让path中含有根节点，所以backTacking(root,[root.val])。因为它一进来就是遍历的左右子节点 ```js function allPath(root) { if (!root) return [] let res = [] function backTacking(root, path) { if (!root.left && !root.right) { return res.push([...path]) } //因为二叉树只有左右子节点，所以只需要循环条件就是左右子节点存在 if (root.left) { path.push(root.left.val) backTacking(root.left, path) path.pop() } if (root.right) { path.push(root.right.val) backTacking(root.right, path) path.pop() } } backTacking(root, [root.val]) console.log(res) } ``` ​ #### [216. 组合总和 III](https://leetcode.cn/problems/combination-sum-iii/) > ​ 思路：使用k个数，满足和为n。因为集合范围是[1,9]默认有序，且无重复数字，所以无需去重 ```js /* 这题和组合一样，只不过不需要<=n，每次都是<=9 */ var combinationSum3 = function (k, n) { let res = [] function backTracking(path, sum, startIndex) { //剪枝 if (sum > n) return if (path.length == k && sum == n) { return res.push([...path]) } for (let i = startIndex; i <= 9; i++) { path.push(i) backTracking(path, sum + i, i + 1) path.pop() } } backTracking([], 0, 1) return res } ``` #### [组合总和 II](https://leetcode.cn/problems/4sjJUc/) > 其实也是排序去重，但是有个案例太大了，我们需要进行剪枝，类似于三数之和的剪枝操作 ```js var combinationSum2 = function (candidates, target) { candidates.sort((a, b) => a - b) let map = new Map() let res = [] function backTacking(path, sum, start) { if (sum > target) return if (sum == target) { let pathStr = path.join("") if (map.has(pathStr)) return map.set(pathStr, 1) return res.push([...path]) } for (let i = start; i < candidates.length; i++) { //目前这么写，它会超时，所以我们需要进行剪枝 //如 [1,1,1,2] target==3 我们必须保证这一层的i都是从start开始 因此i-1>=start if (i - 1 >= start && candidates[i] == candidates[i - 1]) continue path.push(candidates[i]) backTacking(path, sum + candidates[i], i + 1) path.pop() } } backTacking([], 0, 0) return res } ``` #### [17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/) > 如果:digits=='23' > > 第一层 a b c > > 第二层 def def def > > 终止条件: if(path.length==digits.length) > > for循环层级：它传入的是index，所以先要通过digits[index]获取到字母，然后到map中获取到对应字符串，从而确定遍历的集合 **难点在于：你需要确定每一次for循环遍历的集合，startIndex用来防止重复，每一次选择下一个字母，然后还需要到map中找到对应字符** ```js var letterCombinations = function (digits) { const map = { 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz' } if (!digits.length) return [] let res = [] function backTracking(path, startIndex) { if (path.length == digits.length) { return res.push([...path].join('')) } //确定遍历的字符串集合 let str = map[digits[startIndex]] for (let i = 0; i < str.length; i++) { path.push(str[i]) backTracking(path, startIndex + 1) path.pop() } } backTracking([], 0) return res } ``` #### [39. 组合总和](https://leetcode.cn/problems/combination-sum/) > 思路：集合范围内无重复元素，所以对candidates进行排序后，虽然每个元素可以调用多次，但是也无需去重了 **注意，同一个数字是可以被选任意次的，所以每次backTracking时无需从下一个开始，从自身再来一次即可** ```js var combinationSum = function (candidates, target) { candidates.sort((a, b) => a - b) let res = [] function backTacking(path, sum, start) { if (sum > target) return if (sum == target) { return res.push([...path]) } for (let i = start; i < candidates.length; i++) { path.push(candidates[i]) //可以重复选用 backTacking(path, sum + candidates[i], i) path.pop() } } backTacking([], 0, 0) return res } ``` #### 二叉树的所有路径 ```js function travelTree(root) { let res = [] function backTracking(path, root) { if (!root.left && !root.right) { return res.push([...path]) } if (root.left) { path.push(root.left.val) backTracking(path, root.left) path.pop() } if (root.right) { path.push(root.right.val) backTracking(path, root.right) path.pop() } } backTracking([root.val], root) return res } ``` ### 切割问题 > 给定一个字符串s，将**s分割成`子串`，这就是切割类问题**类似于组合，也是需要回溯 > > 从abcde 先选取a，然后第二层从bcde中选，因此需要 `startIndex，确定遍历集合` > > 等同于从abcde先切割a，然后第二层从bcde中切割 - 确定终止条件。当s被切割完了即终止，每次需要**确定一个startIndex，来判断从哪里开始切**，因此终止条件可以为 if(startIndex==s.length) return - for循环遍历条件。首先需要确定集合，从startIndex开始，逐个裁剪到字符串结束，裁剪出来如果是回文，才推入path ​ 进入下一层递归，如果不是，就continue。 问题在于，没有剪枝，第一层 a|bcde ab|cde abc|de abcd|e abcde ​ 第二层 b|cde bc|de bcd|e bcde ​ 但貌似也不需要剪枝 ![image-20230829105915712](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20230829105915712.png) #### [分割回文串](https://leetcode.cn/problems/M99OJA/) > 思路：从aab中依次切割，先切a a b 分别判断是否回文。比如先切了a 是回文，那么剩下ab继续切，切a和ab a是回文，继续切b，ab不是回文，直接结束。终止条件是，切割到末尾，即startIndex==s.length ```js var partition = function (s) { function isPali(str) { let left = 0 let right = str.length - 1 while (left <= right) { if (str[left] != str[right]) { return false } left++ right-- } return true } let res = [] function backTracking(path, startIndex) { if (startIndex == s.length) { return res.push([...path]) } for (let i = startIndex; i < s.length; i++) { let str = s.slice(startIndex, i + 1) if (isPali(str)) { path.push(str) backTracking(path, i + 1) path.pop() } } } backTracking([], 0) return res } ``` #### [93. 复原 IP 地址](https://leetcode.cn/problems/restore-ip-addresses/) > 这题的思路其实跟分割回文串一样。也是通过startIndex来依次切割集合，然后判断切出来的是否符合条件。但是， > > 1. `这里需要注意剪枝问题`。如果path.length>4了，那么就要直接return，不然会超时 > 2. 终止条件path.length==4的时候才能推入 ```js /* s = "25525511135" 切割s成为子串，然后判断是否符合IP地址即可 切割类问题用回溯 ①确定终止条件，当start==s.length且path.length==4的时候终止 return ②确定循环遍历范围：每次需要从start开始，然后切割范围最大为start+3，判断是否满足ip，满足的话进入递归 */ var restoreIpAddresses = function (s) { let res = [] function backTracking(path, start) { //剪枝操作 if (path.length > 4) return if (start == s.length && path.length == 4) { return res.push([...path].join('.')) } for (let i = start; i < s.length; i++) { let temp = s.slice(start, i + 1) if (Number(temp) < 0 || Number(temp) > 255) break //01 这种也不满足 ,后面011 都不满足，直接退出for循环即可 if (temp.length > 1 && temp[0] == '0') break path.push(temp) backTracking(path, i + 1) path.pop() } } backTracking([], 0) return res } ``` ### 子集问题(直接推入) **子集问题：一个N个数的集合里有多少种符合条件的子集** 子集本质上是无序的，遇到一个推入一个，所以我们需要用start来确定遍历到了哪一个 ![image-20240827103540929](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20240827103540929.png) #### [78. 子集](https://leetcode.cn/problems/subsets/) > 这题其实比组合还要简单点，什么是子集？a属于b且a有且只有一个，所以需要去重。只需要每次push到path数组中，判断是否有重复的，没重复的直接推到res中即可 **因为该题无重复元素，所以连去重都不需要。子集类问题有点类似于组合，但是不同的是它剪枝条件为`start>nums.length`否则是会漏掉最后一层， ==情况下也需要推入的。它的`推入条件不在if判断中`，每一次遍历都需要推入。因此终止条件只能扩大一个范围** 但其实也可以不写，因为递归的时候每次都是start+1,迟早会大于nums.length，是会终止的 ```js var subsets = function (nums) { let res = [] function backTacking(path, start) { if (start > nums.length) return res.push([...path]) for (let i = start; i < nums.length; i++) { path.push(nums[i]) backTacking(path, i + 1) path.pop() } } backTacking([], 0) return res } ``` #### [90. 子集 II](https://leetcode.cn/problems/subsets-ii/) > 这题就是需要去除掉重复元素了。细节： `先给集合进行排序，这样去重的时候就无需排序，减少时间复杂度` ```js var subsetsWithDup = function (nums) { nums.sort((a, b) => a - b) let res = [] let map = new Map() function backTracking(path, start) { if (start > nums.length) return let str = path.join('') if (!map.has(str)) { map.set(str, 1) res.push([...path]) } for (let i = start; i < nums.length; i++) { path.push(nums[i]) backTracking(path, i + 1) path.pop() } } backTracking([], 0) return res } ``` #### [491. 递增子序列](https://leetcode.cn/problems/non-decreasing-subsequences/) > 思路：因为要找出所有递增子序列，因此用回溯(本质上是穷举)。这题的重点在于，给定的nums数组是无序的，所以我们也不能进行排序。而且可能用重复元素，还需要进行`去重处理`。 **如何判断递增？只需要每次递归的时候，判断`当前遍历的集合元素`和上一次推送到path数组中的元素哪个大即可，如果当前集合元素大，那么可以进入下一次递归。** 这题有两个细节： - 需要确保path数组里是递增，所以数组元素必须大于1 - 从path中取出末尾元素，可能是undefined也可能是0 所以需要判断下 ```js var findSubsequences = function (nums) { let res = [] let map = new Map() function backTracking(path, startIndex) { //需要确保递增，所以path.length>1 必须join(',')不然会有问题 if (path.length > 1) { let str = path.join("") if (!map.has(str)) { map.set(str, 1) res.push([...path]) } for (let i = startIndex; i < nums.length; i++) { //从path数组中取出元素 因为nums从-100到100 不可以这么写。因为有0。。。 if (path.length == 0 || nums[i] >= path[path.length - 1]) { path.push(nums[i]) backTracking(path, i + 1) path.pop() } } } backTracking([], 0) return res } ``` ### 排列(用use) **排列问题：N个数按照一定规则全排列，有几种方式，注意：`排列有序，[1,2,3],[2,1,3]是不同的排列`** 因此，排列问题并不是靠startIndex来确保元素是否使用过的，它的顺序是可以随机的，排成的排列是算不同。所以，`排列问题一般用use数组，确保元素是否使用过` #### [46. 全排列](https://leetcode.cn/problems/permutations/) > 思路：use数组。每次都是从0开始遍历nums集合，通过use数组判断是否使用过元素 ```js var permute = function (nums) { /* 终止条件，path.length==nums.length */ let res = [] function backTracking(path, use) { if (path.length == nums.length) { return res.push([...path]) } for (let i = 0; i < nums.length; i++) { if (!use[i]) { use[i] = true path.push(nums[i]) backTracking(path, use) path.pop() use[i] = false } } } backTracking([], []) return res } ``` #### 47.全排列Ⅱ > 思路：全排列Ⅱ和Ⅰ不同的地方在于，它有重复的元素，所以需要对结果进行去重 ```js var permuteUnique = function (nums) { let res = [] let map = new Map() function backTracking(path, use) { if (path.length == nums.length) { let str = path.join('') if (!map.has(str)) { map.set(str) res.push([...path]) }else{ //剪枝操作，因为path.length==nums.length后，必定结束此次递归 return } } for (let i = 0; i < nums.length; i++) { if (!use[i]) { use[i] = true path.push(nums[i]) backTracking(path, use) path.pop() use[i] = false } } } backTracking([], []) return res } ``` ### [332. 重新安排行程](https://leetcode.cn/problems/reconstruct-itinerary/) > 思路：首先必须注意 **起点都是从 `jfk`开始，每个机票都对应着起点和终点。** > > - **可以建立一个map，键名是对应的起点，键值是从该点可前往的地点，同时对键值进行排序** > - 递归回溯，因为所有机票都至少存在一种合理的行程，它只需要返回一种最小的行程即可。所以是`遍历一条边`，递归函数需要有返回值。 >- 终止条件：result.length==tickets.length+1 (需要包含一个开始位置“JFK”) > - **这题有点类似于二叉树的遍历一条边，只需要找到一条路径满足即可，所以需要返回值。** ```js var findItinerary = function (tickets) { let map = new Map() const result = ['JFK'] for (let item in tickets) { let [from, to] = tickets[item] if (!map.has(from)) { map.set(from, []) } map.get(from).push(to) } for (let [key, value] of map) { value.sort() } function backTracking() { //机票用完 if (result.length == tickets.length + 1) { return true } //机票还未用光,找出下一个要前往的城市列表 res中存放去往过的城市 let nextCities = map.get(result[result.length - 1]) if (!nextCities || !nextCities.length) { return false } for (let i = 0; i < nextCities.length; i++) { //去往下一个城市,删除已经去往过的城市 let city = nextCities[i] result.push(city) nextCities.splice(i, 1) //进行递归，如果结果返回true，那么自身返回true if (backTracking()) { return true } else { //回溯 result.pop() //注意，这里不能直接使用nextCities[i]，因为你前面已经修改过nextCities数组了 // map.get(result[result.length - 1]).splice(i, 0, nextCities[i]) nextCities.splice(i, 0, city) } } } backTracking() return result } ``` ### [51. N 皇后](https://leetcode.cn/problems/n-queens/) > 思路：N皇后要求的是行、列不能用并排元素，且对角线不能同时存在。因为它需要返回不同的组合。**每一行选一个各自置为Q，一行行选下去，一共有n种选择** > > - 终止条件。当遍历到叶子节点即`行数==n`的时候，即可以推入到res (因为递归遍历叶子节点前，会先判断是否符合N皇后条件)。但是如何判断已经遍历到叶子节点了呢？可以添加一个row层级参数，每次递归就++ > - 确定单层搜索逻辑，如果符合N皇后条件就递归进入下一层。所以难点在于判断是否符合N皇后条件。 **N皇后感觉比选择机票简单，逻辑就是正常的组合问题，只不过它的辅助函数比较多而已。而机票问题是遍历一条边** ```js var solveNQueens = function (n) { const res = [] //创建棋盘 const chessboard = new Array(n).fill([]).map(() => new Array(n).fill('.')) function transform(chessboard) { return chessboard.map(item => { return item.join('') }) } function backTracking(row, chessboard) { if (row == n) { return res.push(transform(chessboard)) } for (let col = 0; col < n; col++) { if (isValid(row, col, chessboard, n)) { chessboard[row][col] = 'Q' backTracking(row + 1, chessboard) chessboard[row][col] = '.' } } } function isValid(row, col, chessboard, n) { //检查是否同行是不需要的，因为你每次只会在一行中改变一个就进入下一个递归，即进入下一行，所以不可能同行 //判断是否同列 for (let i = 0; i < row; i++) { if (chessboard[i][col] == 'Q') { return false } } //检查135° for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (chessboard[i][j] == 'Q') { return false } } //检查45° for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (chessboard[i][j] == 'Q') { return false } } return true } backTracking(0, chessboard) return res } ``` ### [37. 解数独](https://leetcode.cn/problems/sudoku-solver/) > 思路：其实数独和**N皇后有点像**，但是N皇后是遍历每一层，然后在每一层中选一个位置放置。所以虽然是二维数组，但是可以把`row作为一个递归的参数`，每一层遍历的时候递增即可。`本质上还是一维递归`。 > > 但是数独却不能这样，它每一层可能需要改变多个元素，所以必须用上 `二维递归`。 > > - 因为只需要找到是否有符合条件的数独，所以只需要遍历一条边，递归函数有返回值。 > - 终止条件 本应该是遍历到最底层的最后元素就返回，但是本题不需要，可以用更简单的方式，即填棋子9个数字都不符合直接返回false > - ![image-20230923170147628](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20230923170147628.png) ```js var solveSudoku = function (board) { function backTracking(board) { //二维递归确定棋子位置 for (let i = 0; i < board.length; i++) { for (let j = 0; j < board[0].length; j++) { if (board[i][j] != '.') continue //9个元素判断是否符合条件,这也就是为什么不需要终止条件，因为9个元素都要试一遍，不成功直接return false即可 for (let k = 1; k <= 9; k++) { if (isValid(i, j, `${k}`, )) { board[i][j] = `${k}` //因为只需要判断有没有棋盘满足条件，所以遍历一条边 if (backTracking(board)) { return true } //回溯 board[i][j] = '.' } } //9个数都不满足，那么直接return false return false } } //如果中途没有return false，说明真的找到了那个棋盘 return true } function isValid(row, col, val) { //判断一列里是否有重复 for (let i = 0; i < 9; i++) { if (board[i][col] == val) { return false } } //判断一行里是否有重复 for (let j = 0; j < 9; j++) { if (board[row][j] == val) { return false } } //判断小方格里是否重复 //获取小方格左上角的起始坐标 let startRow = Math.floor(row / 3) * 3 let startCol = Math.floor(col / 3) * 3 for (let i = startRow; i < startRow + 3; i++) { for (let j = startCol; j < startCol + 3; j++) { if (board[i][j] == val) { return false } } } return true } backTracking(board) return board } ``` ## 贪心 **贪心的本质是 `选择每一阶段的局部最优，从而实现总体最优`** 例如有一堆钞票，拿走10张，选出最大的金额。那么每次都选最大的钞票。但是贪心和背包问题有不同，背包是满足容量为n的背包，选出最大的价值。这是有限制的。 **贪心有的时候就是常识的推导，也没有啥固定的套路** ### [455. 分发饼干](https://leetcode.cn/problems/assign-cookies/) > 思路：将饼干和小孩排序，先将小饼干喂给小胃口的孩子，然后逐个比较。 > > 注意一个细节部分：就是index必须小于g.length不能超出 ，虽然超出了也不会报错，因为任意值与undefined比较大小都是false ```js var findContentChildren = function (g, s) { g.sort((a, b) => a - b) s.sort((a, b) => a - b) let result = 0 let index = 0 for (let i = 0; i < s.length; i++) { if (s[i] >= g[index] && index < g.length) { index++ result++ } } return result } ``` ### 376.摆动序列 > 思路：何为摆动序列，即将递增或递减坡度上的数给删除了，剩下的就是摆动序列 > > 局部最优：删除单调坡上的节点，只需要考虑峰值。 > > prediff=nums[i]-nums[i-1] curdiff=nums[i+1]-nums[i] 只需要prediff<0&&curdiff>0||prediff>0&&curdiff<0即为摆动 > > 但是有三种特殊情况： - 上下坡中有平坡 ![image-20231015122535667](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20231015122535667.png) 这时候的摆动序列应该也为3，需要删除其中的三个2 ![image-20231015122758950](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20231015122758950.png) - ②需要考虑到数组首尾情况，所以遍历需要集合i 0) || (prediff >= 0 && curdiff < 0)) { result++ prediff = curdiff } } return result } ``` ### 55.跳跃游戏 ![image-20230926100622855](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20230926100622855.png) > 思路：每跳一步，就可以通过当前步数+下标计算出跳跃的范围。 > > ​ 遍历当前可跳跃范围，然后比较出最大范围，只要最大范围>=nums.length-1即返回true **注意：每次遍历的是cover，即可跳跃到的距离** ```js var canJump = function (nums) { if (nums.length == 1) { return true } let cover = nums[0] for (let i = 1; i <= cover; i++) { cover = Math.max(i + nums[i], cover) if (cover >= nums.length - 1) { return true } } return false } ``` *** ### 45.跳跃游戏Ⅱ > 思路：首先，需要明确的是**一定可以跳到数组的最后一个位置**。 > > 依然是转化思路，但是这次需要确定两个维度，一个是curDistance，即当前可以走过的范围，nextDistance从当前下标可到达的最大范围。如果i==curDistance，那么说明当前范围已经走完，需要加一步，进入nextDistance下一个最大范围。 ![image-20231018102257623](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20231018102257623.png) ```js /* 思路：用最少的跳跃次数跳到数组最后一个位置，而且必定能跳到 依然是将跳跃转化为范围，但是要考虑何时步数才加1呢 */ var jump = function (nums) { let step = 0 //当前可跳跃的边界 let curCover = 0 //可跳跃的最大范围 let nextCover = 0 for (let i = 0; i < nums.length; i++) { //计算以当前下标起跳 可跳跃的最大范围 nextCover = Math.max(nextCover, nums[i] + i) //当跳跃到之前的最大范围后，需要继续增加一次，进入nextCover的范围，这一步可任意到达nextCover中的下标 if (i == curCover) { step++ curCover = nextCover if (curCover >= nums.length - 1) break } } return step } ``` ### 53.最大子序和 - 思路①：因为是子数组，所以可以用暴力法，找出所有的子数组，然后判断其最大值 - 思路②：贪心。如果-2 1 排在一起，那么最大值一定是1。 局部最优：定义一个temp存储当前的 `连续和`，如果连续和为负数，那么就立刻丢弃，让其等于nums[i+1],从下一个元素开始重新计算连续和，如果当前temp>=0,那么下一个加上去可能大可能小，所以直接加上。 因此，每次需要记录连续和，通过判断连续和是否大于0，如果大于0，那么加上下一个元素`可能会更大`，可能`加上下下个会更大`，但是如果小于0，那么中间值肯定会变小，直接跳到下一个。 ```js var maxSubArray = function (nums) { let temp = 0 let res = -Infinity for (let i = 0; i < nums.length; i++) { if (temp >= 0) { temp += nums[i] } else { temp = nums[i] } //注意：res必须最后比较，因为可能是-1 -1 -2 5这种情况 res = Math.max(temp, res) } return res } ``` ### 122.买卖股票的最佳时机Ⅱ > 思路：注意，它可以每天都进行买入卖出，并不是只能进行一次。 > > ​ 所以需要降维考虑，把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑，我们只需要考虑每天有`正利润`即可。 > > ​ 如果昨天买了今天卖出去有正利润，就直接加上 > > ​ 例如：[1,2,3,4] 第0天买入，第三天卖出的最大利润。 > > ​ profit=prices[3]-prices[0] 等同于 prices[3]-prices[2]+prices[2]-prices[1]+prices[1]-prices[0]。 ```js var maxProfit = function (prices) { if (prices.length == 1) { return 0 } let profit = 0 for (let i = 1; i < prices.length; i++) { if (prices[i] - prices[i - 1] > 0) { profit += prices[i] - prices[i - 1] } } return profit } ``` ### 1005.K次取反的数组最大和 > 思路：先将nums数组从大到小排列，如果k>0&&nums[i]<0那么就将对应的负数取反。 > > 如果所有负数都转正了，k还>0,那么就重新排序，如果k是偶数，不用管，如果k是奇数，那么第一个元素取反即可 ```js var largestSumAfterKNegations = function (nums, k) { nums.sort((a, b) => a - b) for (let i = 0; i < nums.length; i++) { if (nums[i] <= 0 && k > 0) { //取反要注意条件k必须大于0 nums[i] = -nums[i] k-- } } /* 负数翻转完以后，k还存在且不为奇数,只需要让头部元素变为负数即可 偶数直接不用考虑了 */ if (k > 0 && k % 2 != 0) { nums.sort((a, b) => a - b) nums[0] = -nums[0] } return nums.reduce((a, b) => (a += b)) } ``` ### 134.加油站 **注意：环形遍历一般会用while** - `暴力法` > 思路：以每个加油站为起点，计算开往每个站的剩余油量。**细节： `环形遍历用while，且它的下一位一般是(index+1)%数组长度` ** ```js /* 暴力法，以每个加油站作为起点，计算开往每个站的剩余油量 */ var canCompleteCircuit = function (gas, cost) { for (let i = 0; i < gas.length; i++) { //开往每个站的剩余油量 let rest = gas[i] - cost[i] //下一个站点的下标，因为是环形的，所以最后一个的下一位就是第一位。即(i+1)%数组长度 let index = (i + 1) % gas.length while (rest > 0 && index != i) { //模拟以i为起点行驶一圈 rest += gas[index] - cost[index] index = (index + 1) % gas.length } //如果跑完一圈且rest>0&&当前跑完位置index==i 那么i就是起点 if (rest >= 0 && index == i) return i } return -1 } ``` - `贪心法` > 每个加油站的剩余油量 ： **gas[i]-cost[i]**。从0开始累加rest[i],记为 `curSum`，一旦curSum<0,说明(0，i)一定不能作为起点，因为他们剩余油量肯定不够回到起点。 ![image-20231020103035977](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20231020103035977.png) ```js var canCompleteCircuit = function (gas, cost) { let curSum = 0 let totalSum = 0 let start = 0 for (let i = 0; i < gas.length; i++) { let rest = gas[i] - cost[i] curSum += rest totalSum += rest if (curSum < 0) { start = i + 1 curSum = 0 } } //如果最后计算流量总和<0 那么无解 if (totalSum < 0) return -1 //如果总和>0 那么一定有解 return start } ``` *** ### 135.分发糖果 hard > 思路:这道题一定要先确定一边，再确定另外一边。不要左右同时考虑 > > ​ ①先确定右边孩子大于左边的情况，即从前向后遍历，初始化都是1颗糖，只要右边比左边大，那么就+1 > > ​ ②再确定左边孩子比右边大的情况，需要从后向前遍历。因为你需要确保，如果孩子分数高，必须大于左边同时大于右边 **难点就在于思路，需要分两次贪心** ```js var candy = function (ratings) { let candyVec = new Array(ratings.length).fill(1) //从前向后遍历 for (let i = 1; i < candyVec.length; i++) { if (ratings[i] > ratings[i - 1]) { candyVec[i] = candyVec[i - 1] + 1 } } //从后向前遍历 //注意，不能从左向右遍历， rating 1 2 2 5 4 3 2 // 从前向后遍历结果: 1 2 1 2 1 1 1 //如果从左向右的话，你咋判断5这个应该是最大的，还得回头 //从右向左遍历，左孩子如果比右孩子大，那么就找出之前的值和右孩子+1的最大值 for (let i = candyVec.length - 1; i >= 1; i--) { if (ratings[i - 1] > ratings[i]) { candyVec[i - 1] = Math.max(candyVec[i - 1], candyVec[i] + 1) } } console.log(candyVec) return candyVec.reduce((pre, item) => { return (pre += item) }, 0) } candy([1, 2, 2]) ``` *** ### 860.柠檬水找零 > 思路：首先要确定，顾客是按序来的，所以也必须按序收费进行找零。 > > 找10元的时候，判断是否有5元，有5元就可以收，不然就return false，20元的时候优先10元 ```js var lemonadeChange = function (bills) { let five = 0 let ten = 0 for (let i = 0; i < bills.length; i++) { switch (bills[i]) { case 5: five++ break case 10: if (five > 0) { ten++ five-- break } else { return false } case 20: if (ten > 0 && five > 0) { ten-- five-- break } else if (five >= 3) { five -= 3 } else { return false } break } } return true } ``` *** ### 406.根据身高重建队列 ![image-20231010103848980](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20231010103848980.png) > 思路：先按照身高进行降序排序，如果身高相同，按照前面多少人进行升序排序。 > > 定义一个空数组result，然后按照前面多少人进行插入 ```js var reconstructQueue = function (people) { people.sort((a, b) => { if (a[0] != b[0]) { return b[0] - a[0] } else { return a[1] - b[1] } }) let result = [] for (let i = 0; i < people.length; i++) { //往result对应下标添加people result.splice(people[i][1], 0, people[i]) } return result } console.log( reconstructQueue([ [7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2], ]), ) ``` *** ## 动态规划 ### 理论基础 > 动态规划：简称DP，`每一个状态一定是由上一个状态推导出来的`，而贪心则直接从局部最优得到全局最优 **解题步骤：** - 确定`dp数组`和`下标含义` - 确定`递推公式` - `初始化`dp数组 - 确定`遍历顺序` （从前往后，还是从后往前） - 举例验证dp数组 #### [509. 斐波那契数](https://leetcode.cn/problems/fibonacci-number/) 思路： ①确定dp数组和下标含义 - dp[i]表示第i个数的斐波那契数列和 ②状态转移方程 - 题目已经给出dp[i]=dp[i-1]+dp[i-2] ③初始化dp数组 - dp[0]=0 dp[1]=1 ④确定遍历顺序 - 当前状态依赖于前两个状态，所以从左往右遍历，且从2开始 ```js var fib = function (n) { let dp = new Array(n + 1).fill(0) dp[1] = 1 for (let i = 2; i < dp.length; i++) { dp[i] = dp[i - 1] + dp[i - 2] } return dp[n] } ``` #### [746. 使用最小花费爬楼梯](https://leetcode.cn/problems/min-cost-climbing-stairs/) 思路：题目描述比较模糊，可以从第0级楼梯或者第1级开始爬，爬上去的最小消耗 ①确定dp数组和下标含义 dp[i]表示爬到第i级台阶的最小消耗为dp[i] ②确定递推公式 每次可以爬一级或者两级，所以dp[i]可以由dp[i-1]+cost[i-1]得到 或者dp[i-2]+cost[i-2]得到 dp[i]=Math.min(dp[i-1]+coust[i-1],dp[i-2]+cost[i-2]) ③dp数组初始化 dp[0]=0 dp[1]=0 **因为可以从第一级开始** dp[2]=Math.min(cost[0],cost[1]) ④确定遍历顺序 从2开始，从小到大遍历 ```js var minCostClimbingStairs = function (cost) { let dp = new Array(cost.length + 1).fill(0) for (let i = 2; i < dp.length; i++) { dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]) } return dp[dp.length - 1] } ``` ### [62. 不同路径](https://leetcode.cn/problems/unique-paths/) 思路：这是很经典的动态规划路径题目，需要注意初始化的问题 ①确定dp数组和下标含义 dp[i] [j]表示从(0,0)到下标(i,j)有dp[i] [j]条不同路径 ②确定递推公式 因为只能向右或者向下 dp[i] [j]=dp[i-1] [j] (向右)+dp[i] [j-1] (向下) ③初始化dp数组 第一行和第一列一定是1 ④确定遍历顺序 从(1,1)开始，从小到大遍历 ```js var uniquePaths = function (m, n) { let dp = new Array(m + 1).fill().map(() => new Array(n + 1).fill(0)) for (let i = 0; i <= m; i++) { dp[i][0] = 1 } for (let j = 0; j <= n; j++) { dp[0][j] = 1 } for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] } } return dp[m - 1][n - 1] } ``` ### [63. 不同路径 II](https://leetcode.cn/problems/unique-paths-ii/) 思路：这题和不同路径Ⅰ其实差不多，就是需要判断遍历时遇到obstacleGrid[i] [j]=1的情况，那么dp[i ] [j]=0 ```js var uniquePathsWithObstacles = function (obstacleGrid) { let m = obstacleGrid.length let n = obstacleGrid[0].length let dp = new Array(m).fill().map(() => new Array(n).fill(0)) for (let i = 0; i < m; i++) { if (obstacleGrid[i][0] == 1) { dp[i][0] = 0 //如果前面有一个是0，那么后面也全是0 break } else { dp[i][0] = 1 } } for (let j = 0; j < n; j++) { if (obstacleGrid[0][j] == 1) { dp[0][j] = 0 break } else { dp[0][j] = 1 } } for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { if (obstacleGrid[i][j] == 1) { dp[i][j] = 0 } else { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] } } } return dp[m - 1][n - 1] } ``` ### [343. 整数拆分](https://leetcode.cn/problems/integer-break/) **思路：** ①确定dp数组和下标含义 dp[i]表示拆分数字i，得到的最大乘积为dp[i] ②推导状态转移方程 拆分i，可以从0开始，一直拆分到i/2。因此需要一个变量j 如果拆分为两个数dp[i]=j*(i-j)，如果拆分为三个数甚至更多，就需要拆分i-j，得到其最大乘积，由dp数组的含义可以转化为dp[i-j] ③初始化dp数组 dp[0]=0 dp[1]=0 dp[2]=1 ④确定遍历顺序 从左往右遍历 ```js var integerBreak = function (n) { let dp = new Array(n + 1).fill(0) dp[2] = 1 for (let i = 3; i <= n; i++) { for (let j = 1; j < i; j++) { //这里多个dp[i]，是为了同一个i的情况下，取最大值。因为有不同的j dp[i] = Math.max(j * (i - j), j * dp[i - j], dp[i]) } } return dp[n] } ``` ### [96. 不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees/) 思路： ①确定dp数组和下标含义 dp[i]表示用i个节点，可构成的不同的二叉搜索树有dp[i]种 ②推导状态转移方程 `dp[i]+=dp[j]*dp[i-j-1]` 以k为根节点，那么(1,k-1)用来构造左子树（用了k-1个节点），(k+1,i)用来构造右子树 用了i-k-1个节点 那么当前可构造的种类为 k-1* (i-k-1) 所以n个节点，假设左子树用了j个，那么右子树只能是i-j-1个 **dp[i]=dp[0] * dp[i-1]+dp[1] * dp[1] * dp[i-1-1] + dp[2] * d[i-2-1] + ... +dp [i-1] *d[0] ** *dp*[*i*]=∑*dp*[*j*]∗*dp*[*i*−*j*−1],0<=*j*<=*i*−1 ③初始化dp数组 dp[0]=1 空树 dp[1]=1单个节点 ```js var numTrees = function (n) { let dp = new Array(n + 1).fill(0); dp[0] = dp[1] = 1; for (let i = 2; i <= n; i++) { for (let j = 0; j < i; j++) { dp[i] += dp[j] * dp[i - j - 1]; } } return dp[n]; }; ``` ### 背包问题 #### **背包问题理论基础** `01背包：`: **外层物品，内层背包容量。从大到小遍历** - 装满背包最大价值 : dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]) - 装满背包有几种组合方式: dp[j]+=dp[j-weight[i]] 。**注意dp[0]=1 ** `完全背包`：组合或者价值 外层物品，内层背包,从小到大遍历。**排列：外层背包，内层物品，且j>=weight[i]** - 背包最大价值 : > 外层物品，内层背包容量，从小到大遍历。 > > dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]) - 装满背包有几种组合方式: > 注意是组合，`外层物品，内层背包，从小到大遍历`，且`j必须从weight[i]开始`。且 **dp[0]=1** > > ```js > dp[0]=1 > for (let i = 0; i < coins.length; i++) { > for (let j = coins[i]; j <= bagSize; j++) { > dp[j] += dp[j - coins[i]] > } > } > ``` - 装满背包有几种排列方式： > 排列需要注意：`外层背包，内层物品`。也因此需要多个判断条件，`if(j>=weight[i])。这是因为j没法从weight[i]开始了嘛`。**且dp[0]=1** > > ```js > dp[0]=1 > for (let j = 0; j <= bagSize; j++) { > for (let i = 0; i < nums.length; i++) { > if (j >= nums[i]) { > dp[j] += dp[j - nums[i]] > } > } > } > ``` - 装满背包的最少物品数： > 依然是外层物品，内层背包。 `注意：初始化时要为Infinity，dp[0]=0` > > ```js > let dp = new Array(bagSize + 1).fill(Infinity) > //当背包容量为0时，最少的物品个数自然是0。至于为什么初始化为Infinite，是因为Math.min要比较最小值 > //不能直接初始化-1，就是因为min要比较最小值，如果装不满或者溢出，那么结果就是Infinite。 > dp[0] = 0 > for (let i = 0; i < coins.length; i++) { > for (let j = coins[i]; j <= bagSize; j++) { > dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1) > } > } > return dp[bagSize] == Infinity ? -1 : dp[bagSize] > ``` > > ---- ##### 01背包 > 有`n件物品`和一个最多能背`重量为w 的背包`。第i件物品的重量是`weight[i]`，得到的`价值是value[i]` 。**每件物品`只能用一次`**，求解将哪些物品装入背包里物品价值总和最大。 ###### **dp二维数组解法** 1. 确定dp数组和下标含义 dp[i] [j]表示从`下标(0,i)`件物品里任取，放进`容量为j`的背包里，得到的`最大价值为dp[i] [j]` ![image-20231205100738140](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20231205100738140.png) 2. 确定递推公式 **因为dp[i] [j]表示从(0,i)件物品里任取，放进容量为j的背包，得到的最大价值为dp[i] [j]**。因此，可以分两种情况 - `不放物品i`，那么dp[i] [j]的最大价值就是dp[i-1] [j]，价值和之前的相同 - `放物品i` , 那么dp[i] [j]的最大价值就是 dp[i-1] [j-weight[i]] + values[i]。 **即容量j去除掉物品i的重量，然后加上values[i]** ​ **因此，综上，递推公式为** ```js dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+values[i]) ``` --- 3.dp数组初始化 **因为背包容量为j，当j为0的时候，背包价值一定为0，所以dp[i] [0]=0**。 状态转移方程 dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。 **当i==0的时候，只有当j>=weight[0]时，dp[i] [j]=values[0]** ![image-20231205101729400](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20231205101729400.png) **初始化代码** **注意：i==value.length j==bagSize+1** ```js let dp = new Array(value.length).fill().map(() => new Array(size + 1).fill(0)) for (let i = 0; i < value.length; i++) { //当背包容量为0时，最大价值自然为0 dp[i][0] = 0 } for (let j = 0; j <= size; j++) { if (j >= weight[0]) { dp[0][j] = value[0] } } ``` ---- 4. **确定遍历顺序** 有两个维度，但是01背包先遍历物品再遍历背包 ​ 由递推公式 **dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i])** 可以发现，当前状态由dp[i-1] [j]和 dp[i-1] [j-weight[i]]推导而出，所以当前状态是依赖于左上角 ![image-20231205103401837](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20231205103401837.png) ``` function testWeightBagProblem(weight, value, size) { let dp = new Array(value.length).fill().map(() => new Array(size + 1).fill(0)) for (let i = 0; i < value.length; i++) { //当背包容量为0时，最大价值自然为0 dp[i][0] = 0 } for (let j = 0; j <= size; j++) { if (j >= weight[0]) { dp[0][j] = value[0] } } for (let i = 1; i < value.length; 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.log(dp) } ``` ###### 滚动数组优化 > 二维dp数组dp[i] [j]的含义为：从(0,i)件物品里取，放到背包容量为j的背包里，得到的最大价值为dp[i] [j]。因此我们可以得到状态转移方程: dp[i] [j]=Math.max(dp[i-1] [j],dp[i-1] [j-weight[i]] + values[i])。可以看到当前状态是依赖于前一个状态的 `滚动数组的由来`： **将上一层的数据直接拷贝到当前数据，再把新的值覆盖到当前层，下一层计算再从当前层取。**相当于一个矩阵压缩成一行，然后行滚动 - 确定dp数组和下标含义 dp[j]表示背包容量为j时，所放的物品的最大价值为dp[j] - 推导状态转移方程 dp[j]可以由dp[j-weight[i]]推导出来，dp[j-weight[i]]表示背包容量为j-weight[i]所放物品的最大价值。dp[j]=dp[j-weight[i]]+values[i] **表示背包容量为j的背包的最大价值通过放了种类为 `weight[i]`的物品的价值 ** ```js dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]) ``` - 初始化dp数组 dp[j]表示背包容量为j的背包所能拿物品的最大价值 dp[0]=0 是自然的 - `遍历顺序` `一维dp遍历，背包容量是由大到小的遍历，这是为了确保01背包，每个物品只能拿取一次。且背包容量j>=weight[i]` ```js for(let i=0;i=weight[i];j--){ //遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); //找出装满当前背包j的最大价值即可。 } } ``` > 举一个例子：物品0的重量weight[0] = 1，价值value[0] = 15。 > > - 正序遍历：dp[1]=Math.max(dp[1],dp[1-1]+value[0]) //dp[1]为15 > > ​ dp[2]=Math.max(dp[2],dp[2-1]+value[0]) //dp[2]为30 可以发现物品0被取了多次 。 > > - 反向遍历：dp[2]=Math.max(dp[2],dp[2-1]+value[0]) //dp[2]为15 取了一次value[0] ```js function testWeightBagProblem(weight, value, bagSize) { let dp = new Array(bagSize + 1).fill(0) for (let i = 0; i < weight.length; i++) { for (let j = bagSize; j >= weight[i]; j--) { dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]) } } console.log(dp) } testWeightBagProblem([1, 3, 4], [15, 20, 30], 4) ``` ###### 416.分割等和子集 > 思路：将其分割成两个子集且和相等，可以转化下思路，转化为数组的总和的一半，其作为背包容量。 > > 同时将nums数组排序，每个数字只能取一次，就可以转化为01背包问题。 > > 从nums数组里任取(每个只能取一次)，他们的重量为nums[i],价值为nums[i]，放到背包容量bagSize中，判断是否能填满背包。如果能填满背包，且他们的价值dp[bageSize]==bagSize return true ```js var canPartition = function (nums) { nums.sort((a, b) => a - b) let sum = nums.reduce((pre, item) => (pre += item), 0) if (sum % 2 != 0) return false let bagSize = sum / 2 let dp = new Array(bagSize + 1).fill(0) for (let i = 0; i < nums.length; i++) { for (let j = bagSize; j >= nums[i]; j--) { dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]) } } if (dp[bagSize] == bagSize) return true return false } ``` ###### [1049. 最后一块石头的重量 II](https://leetcode.cn/problems/last-stone-weight-ii/) > 思路转化：将其求和分为一半作为背包容量bagSize，最后是填满这个背包有的最大价值为dp[bagSize], sum-2*dp[bagSize]即可。因为bagSize=parseInt(sum/2)。所以只能sum-2 * dp[bagSize]。不然会有误差 ```js var lastStoneWeightII = function (stones) { stones.sort((a, b) => a - b); let sum = stones.reduce((pre, item) => (pre += item)); let bagSize = parseInt(sum / 2); let dp = new Array(bagSize + 1).fill(0); for (let i = 0; i < stones.length; i++) { for (let j = bagSize; j >= stones[i]; j--) { dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]); } } return sum - 2 * dp[bagSize]; }; ``` ###### [494. 目标和](https://leetcode.cn/problems/target-sum/)（组合问题） > 正+负=target > > 正-负=sum > > 正=(target+sum)/2 > > 因此可以得到 x=(sum+target)/2 即背包容量为x，有几种方法可以填满背包，即求组合问题 - 确定dp数组和下标含义 dp[j]表示填满背包容量为j，有dp[j]种方法 - 推导状态转移方程 ``` dp[j]+=dp[j-nums[i]] ``` 只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。 例如：dp[j]，j 为5， - 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。 - 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。 - 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包 - 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包 - 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包 那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。 **有点类似于不同的二叉搜索树** - 初始化dp数组 **注意：组合问题dp[0]=1。因为不装满也是一种方法** - 遍历顺序是按照01背包 bagSize从大到小 ```js /* 正数和为 x 负数为target-x x-(target-x)=sum x=(sum+target)/2 */ var findTargetSumWays = function (nums, target) { nums.sort((a, b) => a - b) let sum = nums.reduce((a, b) => (a += b), 0) if (Math.abs(target) > sum) return 0 //防止特殊示例 if ((sum + target) % 2) { return 0 //因为正数和x 一定是整数 } let bagSize = (sum + target) / 2 let dp = new Array(bagSize + 1).fill(0) //初始化方法 dp[0]=1 dp[0] = 1 for (let i = 0; i < nums.length; i++) { for (let j = bagSize; j >= nums[i]; j--) { //装满背包有几种方法 //当背包容量为5 dp[5]+=dp[5-nums[0]] dp[j] += dp[j - nums[i]] } } return dp[bagSize] } ``` ###### [474. 一和零](https://leetcode.cn/problems/ones-and-zeroes/)(记忆） ```js var findMaxForm = function (strs, m, n) { let dp = new Array(m + 1).fill().map(() => new Array(n + 1).fill(0)) for (let str of strs) { let zeroNum = 0 let oneNum = 0 for (let s of str) { if (s == '0') { zeroNum++ } else { oneNum++ } } for (let i = m; i >= zeroNum; i--) { for (let j = n; j >= oneNum; j--) { dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1) } } } return dp[m][n] } ``` ##### 完全背包 **完全背包和01背包的区别就在于用滚动数组法的时候，完全背包遍历背包容量是从小到大遍历。因为每个物品可以选取多次** ```js for(let i=0;i 思路：从物品里任取，背包容量为amount，问装满背包有几种方式 ```js var change = function (amount, coins) { //物品 coins let bagSize = amount let dp = new Array(bagSize + 1).fill(0) dp[0] = 1 for (let i = 0; i < coins.length; i++) { for (let j = coins[i]; j <= bagSize; j++) { dp[j] += dp[j - coins[i]] } } return dp[bagSize] } change(2, [3]) //溢出 change(3,[2]) //装不满 /* dp[2]+=dp[2-2] dp[2]=1 dp[3]+=dp[3-2] dp[3]=dp[1]=0 */ ``` **因为初始化时，除了dp[0]=1 其他都为0，所以如果装不满背包或者溢出没法装，结果就是0** ###### [377. 组合总和 Ⅳ(排列)](https://leetcode.cn/problems/combination-sum-iv/) > 思路：转化思路，总和target为背包容量，从物品里任取(不限个数)，求装满背包的`排列个数` **注意：排列的话就是`先遍历背包`，再遍历物品，也因此需要多个判断条件即 `if(j>=weight[i])`dp[0]=1** ```js var combinationSum4 = function (nums, target) { let bagSize = target let dp = new Array(bagSize + 1).fill(0) dp[0] = 1 for (let j = 0; j <= bagSize; j++) { for (let i = 0; i < nums.length; i++) { if (j >= nums[i]) { dp[j] += dp[j - nums[i]] } } } return dp[bagSize] } ``` ###### 322.零钱兑换(最少物品数) > 思路：凑成总金额的**最少的硬币个数**，总金额：bagSize，最少硬币个数：dp[j]=Math.min(dp[j],dp[j-weight[i]+1]) ``` var coinChange = function (coins, amount) { let bagSize = amount let dp = new Array(bagSize + 1).fill(Infinity) //当背包容量为0时，最少的物品个数自然是0。至于为什么初始化为Infinite，是因为Math.min要比较最小值 //不能直接初始化-1，就是因为min要比较最小值，如果装不满或者溢出，那么结果就是Infinite。 dp[0] = 0 for (let i = 0; i < coins.length; i++) { for (let j = coins[i]; j <= bagSize; j++) { dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1) } } return dp[bagSize] == Infinity ? -1 : dp[bagSize] } ``` ###### [279. 完全平方数](https://leetcode.cn/problems/perfect-squares/)(最少物品数) > 思路：和为n，即背包容量bagSize=n，整数n 即物品(1,2,3...,n)。重量为(1,4,9.... n ^2) > > 可以理解为从物品(1,n)中任取，求装满背包n的最少物品数 ``` var numSquares = function (n) { let bagSize = n let dp = new Array(bagSize + 1).fill(Infinity) dp[0] = 0 for (let i = 1; i <= n; i++) { for (let j = i * i; j <= bagSize; j++) { dp[j] = Math.min(dp[j], dp[j - i * i] + 1) } } return dp[bagSize] } ``` ```js var numSquares = function (n) { let bagSize = n let dp = new Array(bagSize + 1).fill(Infinity) dp[0] = 0 for (let i = 1; i <= n; i++) { let weight = Math.pow(i, 2) for (let j = weight; j <= bagSize; j++) { dp[j] = Math.min(dp[j], dp[j - weight] + 1) } } return dp[bagSize] == Infinity ? -1 : dp[bagSize] } ``` ###### [139. 单词拆分（排列）](https://leetcode.cn/problems/word-break/) > 思路：背包容量bagSize==s.length > > - 确定dp数组和下标含义 > > dp[i]表示长度为i的字母，如果dp[i]=true 说明可以被拆分，反之不行 > > - 推导状态转移方程 > > 如果dp[j]为true，且字符(j,i)出现在字典里，那么dp[i]也为true > > **因此状态转移方程为** > > ``` > if(dp[j]&&s(j,i)出现在字典里){dp[i]=true} > ``` > > - 初始化dp数组 > > dp[i]依赖于dp[j]而j是前一个状态，所以一定得初始化dp[0] > > dp[0]表示如果字符串为空的话，说明出现在字典里,所以dp[0]=true > > - 确定遍历顺序 > > `注意：因为字符串有序，所以这是个排列问题，所以外层是背包，内层物品，需要多个判断条件j>wrod[i].length` ```js var wordBreak = function (s, wordDict) { let bagSize = s.length let dp = new Array(bagSize + 1).fill(false) dp[0] = true for (let j = 0; j <= bagSize; j++) { for (let i = 0; i < wordDict.length; i++) { //再次想一下dp[j]的定义，表示长度为j的字母是否可以拆分 if (j >= wordDict[i].length) { //去除掉已经在字典里的 wordDict[i]。 //j代表的是长度，所以下标为j-1 //temp是从wordDict[i].length的下一位开始 因此为 (j-wordDict[i].length-1)+1 //终止条件为到j-1 因为要包含最后一位需要+1 因此为j-1 + 1 let temp = s.slice(j - wordDict[i].length, j) if (wordDict.includes(temp) && dp[j - wordDict[i].length]) { dp[j] = true } } } } return dp[bagSize] } ``` **** ### [198. 打家劫舍](https://leetcode.cn/problems/house-robber/) > 当前房子偷不偷取决于上一间房子或者上上间房子，有一种依赖关系，所以用动态规划 > > - 确定dp数组和下标含义 > > dp[i]表示从0-i间房子(包括i)，偷窃到的最大金额为dp[i] > > - 状态转移方程 > > - 如果偷第i间房子，那么第i-1一定不能偷，因此dp[i]=dp[i-2]+nums[i] > - 如果不偷第i间房子，那么就是前i-1间房子的最大金额 dp[i]=dp[i-1] > > dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]) > > - 初始化dp数组 > > 当前状态依赖于前面状态，需要初始化dp[0],dp[1] > > dp[0]=nums[0] > > dp[1]=Math.max(nums[0],nums[1]) > > - 确定遍历顺序，从左往右，从i=2开始 ```js var rob = function (nums) { let dp = new Array(nums.length).fill(0) dp[0] = nums[0] if (nums.length <= 1) return dp[0] dp[1] = Math.max(dp[0], nums[1]) if (nums.length == 2) return dp[1] for (let i = 2; i < nums.length; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]) } return dp[dp.length - 1] } ``` ### 199.打家劫舍Ⅱ > 与1的区别在于，头和尾是相同的。因此我们可以定义两种情况，一种是没头，一种是没尾，最后比较获得的最大值即可。 ```js /* 状态转移方程： dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]) */ var rob = function (nums) { //避免无法裁剪的情况 if(nums.length<=1) return nums[0] let nums1 = nums.slice(0, nums.length - 1) let nums2 = nums.slice(1) return Math.max(getRob(nums1), getRob(nums2)) function getRob(num) { let dp = new Array(num.length).fill(0) dp[0] = num[0] if (num.length <= 1) return num[0] dp[1] = Math.max(dp[0], num[1]) if (nums.length == 2) return dp[1] for (let i = 2; i < dp.length; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + num[i]) } return dp[dp.length - 1] } } ``` ### 200.打家劫舍Ⅲ > 很明显需要用后序遍历，从叶子节点开始。注意点：它不是间隔一个节点就要偷，因为可能连续两个节点后有个极大的节点。 > > 而且左右子节点不是两个都要偷 ```js var rob = function (root) { function postOrder(root) { //[不偷当前节点，偷当前节点] if (!root) return [0, 0] let leftNode = postOrder(root.left) let rightNode = postOrder(root.right) //偷当前节点，就不能偷左右子节点 let withRoot = root.val + leftNode[0] + rightNode[0] //不偷当前节点，左右子节点可偷可不偷 let outRoot = Math.max(leftNode[0], leftNode[1]) + Math.max(rightNode[0], rightNode[1]) return [outRoot, withRoot] } return Math.max(...postOrder(root)) } ``` ### 121.买卖股票的最佳时机 - 总结：股票问题动态规划主要分为持有和不持有。如果分次的话就是持有且第一次买入卖出，或持有第二次买入卖出 **这是最简单的一题，只需要遍历prices，找出之前最低，然后计算最大差值即可** ```js var maxProfit = function (prices) { let minCost = prices[0] let profit = 0 for (let i = 0; i < prices.length; i++) { minCost = Math.min(minCost, prices[i]) profit = Math.max(profit, prices[i] - minCost) } return profit } ``` ### 122.买卖股票的最佳时机Ⅱ > 有两种解法： > > - 动态规划：因为可以在任意一天买入或者卖出。有两个状态 0表示不持有股票，1表示持有股票 > > - 确定dp数组和下标含义：dp[i] [0]表示第i天不持有股票的最大受益，dp[i] [1]表示持有股票的最大收益 > > - 状态转移方程：dp[i] [0]=Math.max(dp[i-1] [0],dp[i-1] [1]+prices[i]) > > dp[i] [1]=Math.max(dp[i-1] [1],dp[i-1] [0]-prices[i]) > > - 初始化dp数组 > > 因为dp[i]依赖于dp[i-1] 因此dp[0] [0]=0 dp[0] [1]=-prices[0] ```js var maxProfit = function (prices) { let dp = new Array(prices.length).fill().map(() => new Array(2).fill(0)) dp[0][0] = 0 dp[0][1] = -prices[0] for (let i = 1; i < prices.length; i++) { dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]) dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]) } return dp[dp.length - 1][0] } ``` > 解法2：因为你可以任意一天买入卖出，只需要当前价格大于昨天价格，那就进行买入即可 ```js var maxProfit = function (prices) { let profit = 0 for (let i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) { profit += prices[i] - prices[i - 1] } } return profit } ``` ### 123.买卖股票的最佳时机III (hard) > 只要是股票，肯定需要用dp。因为最多持有两次，只能买卖两次。 所以需要定义4个股票状态 > > - 确定dp数组和下标含义： > > 有5个状态，0表示什么操作都没有(**初始化为0即可**)，因为1必须从0得到 > > 1表示第一次持有股票。2表示第一次不持有股票。3表示第二次持有股票。4表示第二次持有股票 > > dp[i] [j]表示第i天状态j所持拥有的最大现金 > > **注意：dp[i] [1]表示的是第i天第一次`持有股票`的最大现金，不代表第i天买入。可能是i-1天买入的** > > - 确定状态转移方程 > > 达到dp[i] [1]有两种逻辑，一种是第i天买入股票 > > dp[i] [1]=dp[i-1] [0]-prices[i] > > 一种是延续第i-1天的状态 > > dp[i] [1]=dp[i-1] [1] > > 因此 **dp[i] [1]=Math.max(dp[i-1] [1],dp[i-1] [0]-prices[i])** > > **同理** > > **dp[i] [2]=Math.max(dp[i-1] [2],dp[i-1] [1]+prices[i])** > > **dp[i] [3] = Math.max(dp[i-1] [3],dp[i-1] [2]-prices[i])** **(注意，状态2是不持有第一次，3是持有第二次)** > > **dp[i] [4]=Math.max(dp[i-1] [4],dp[i-1] [3]+prices[i])** > > **** > > - 初始化dp数组 > > 因为当前状态依赖于前一天状态，所以需要初始化dp[0] [j] > > dp[0] [0]=0 dp[0] [1]=-prices[0] dp[0] [2]=0 dp[0] [3]=-prices[0] dp[0] [4]=0 > > - 确定遍历顺序，从左往右遍历 ```js var maxProfit = function (prices) { let dp = new Array(prices.length).fill().map(() => new Array(5).fill(0)) dp[0][1] = -prices[0] dp[0][3] = -prices[0] for (let i = 1; i < prices.length; i++) { dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]) dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]) dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]) dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]) } return dp[dp.length - 1][4] } ``` ### [188. 买卖股票的最佳时机 IV](https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iv/)(hard) > 其实4和3类似，3确定了只能买卖两次，而4可以进行k次。**注意：买卖2次一定会>=买卖一次，因为你买卖一次至少是可以拆分成买卖两次的，比如4 1 4 6 :1买入，4卖出，4买入，6卖出等同于1买入6卖出** > 思路：依然是确定有几个状态 > > - 0表示不处理 > > - 1表示第一次持有股票 > - 2第一次不持有股票 > - 3第二次持有股票 > - 4第二次不持有股票 > > 如果买卖k次，那么j的状态 一定是 [0,2k+1)。 > > **继续分析：dp[i] [1]表示第i天第一次持有股票的最大利润，dp[i] [1]=Math.max(dp[i-1] [1],dp[i-1] [0]-prices[i])**,j只要是奇数就是 > > 是买入，是偶数就卖出。因此`j要分奇偶` > > 1. 确定dp数组和下标含义：dp[i] [j]表示第i天状态为j的最大利润，j需要分 奇偶 > > 2. 状态转移方程： > > 当j为奇数，dp[i] [1]=Math.max(dp[i-1] [1],dp[i-1] [0]-prices[i]) > > 当j为偶数，dp[i] [2]=Math.max(dp[i-1] [2],dp[i-1] [1]+prices[i]) > > 3. 确定循环条件 > > 因为j要分奇偶，j的范围是小于2*k+1的,当前j依赖于前一个j的状态，所以j从1开始 > > 4. 初始化dp数组 > > **因为奇数都是卖出的，所以遍历dp[0] [奇数]=-prices[i]** ```js var maxProfit = function (k, prices) { let dp = new Array(prices.length + 1).fill().map(() => new Array(2 * k + 1).fill(0)) // 奇数次买入 for (let j = 1; j < 2 * k + 1; j += 2) { dp[0][j] = -prices[0] } for (let i = 1; i <= prices.length; i++) { for (let j = 1; j < 2 * k + 1; j++) { if (j % 2 != 0) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i - 1]) } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i - 1]) } } } console.log(dp) return dp[dp.length - 1][2 * k] } ``` ### 125.买卖股票的最佳时机含冷冻期 **注意：冷冻期是你卖出去股票后，下一天不能买入。不是你买股票，下一天不能卖出** > 思路：买卖股票的题目最重要的是确定状态，该题可以确定4个状态 > > ​ 当天买入持有股票、当天卖出不持有股票、当天未买入持有股票、当天未卖出不持有股票 > > *** > > - 确定dp数组和下标含义：dp[i][j]表示第i天状态为j的最大利润 > > - 状态转移方程： > > 因为冷冻期的存在，所以状态0只能从状态3得到，即**前一天没有卖出股票** > > dp[i] [0]=dp[i-1] [3]-prices[i] > > dp[i] [1]=Math.max(dp[i-1] [1],dp[i-1] [0]) > > dp[i] [2]=Math.max(dp[i-1] [0]+prices[i],dp[i-1] [1]+prices[i]) > > dp[i] [3]=Math.max(dp[i-1] [3],dp[i-1] [2]) > > - 初始化dp数组 > > dp[0] [0]=-prices[0] > > dp[0] [1]=-prices[0] > > dp[0] [2]=0 dp[0] [3]=0 > > ```js /* 0:初始化状态 1:当前持有股票，且是当天买入 2：当前持有股票，且不是当天买入 3：当前不持有股票，且是当天卖出 4：当前不持有股票，且是当天没卖出 dp[i][j]表示当前第i天状态为j的最大利润 dp[i][4]=Math.max(dp[i-1][4],dp[i-1][3]) 因为dp[i-1][3]是已经卖出去的最大价值！！！不能再卖 */ var maxProfit = function (prices) { let dp = new Array(prices.length).fill().map(() => new Array(5).fill(0)) dp[0][1] = -prices[0] dp[0][2] = -prices[0] for (let i = 1; i < prices.length; i++) { dp[i][1] = dp[i - 1][4] - prices[i] dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1]) dp[i][3] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2] + prices[i]) dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3]) } return Math.max(dp[dp.length - 1][3], dp[dp.length - 1][4]) } maxProfit([1, 2, 3, 0, 2]) ``` ```js 写法②： dp[i][1]表示第i天持有股票且当天买入的最大价值 dp[i][2]表示第i天不持有股票且当天卖出的最大价值 dp[i][3]表示第i天持有股票且非当天买入 dp[i][4]表示第i天不持有股票且非当天卖出 状态转移方程 dp[i][1]=dp[i-1][4]-prices[i-1] dp[i][2]=Math.max(dp[i-1][1],dp[i-1][3])+prices[i-1] dp[i][3]=Math.max(dp[i-1][3],dp[i-1][1]) dp[i][4]=Math.max(dp[i-1][4],dp[i-1][2]) var maxProfit = function (prices) { let dp = new Array(prices.length + 1).fill().map(() => new Array(5).fill(0)) dp[0][1] = dp[0][3] = -prices[0] for (let i = 1; i < dp.length; i++) { dp[i][1] = dp[i - 1][4] - prices[i - 1] dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][3]) + prices[i - 1] dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][1]) dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][2]) } return Math.max(dp[dp.length - 1][2], dp[dp.length - 1][4]) } console.log(maxProfit([1, 2, 3, 0, 2])) ``` ### 126.买卖股票的最佳时机含手续费 > 其实这跟买卖股票的最佳时机Ⅱ差不多，就是你卖股票的时候需要加个手续费而已 > > - 确定dp数组和下标含义：dp[i] [1]表示第i天持有股票的最大利润，dp[i] [2]表示第i天不持有股票的最大利润 > > - 状态转移方程： > > ```js > dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2] - prices[i - 1]) > dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i - 1] - fee) > ``` > > - 初始化dp数组 > > 因为dp[i]依赖于dp[i-1] 因此dp[0] [0]=0 dp[0] [1]=-prices[0] ```js var maxProfit = function (prices, fee) { let dp = new Array(prices.length + 1).fill().map(() => new Array(3).fill(0)) dp[0][1] = -prices[0] for (let i = 1; i <= prices.length; i++) { dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2] - prices[i - 1]) dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i - 1] - fee) } return dp[dp.length - 1][2] } ``` *** ### [300. 最长递增子序列](https://leetcode.cn/problems/longest-increasing-subsequence/) **dp解法：** > - 确定dp数组和下标含义。 > > dp[i]表示以nums[i-1]结尾的最长递增子序列的长度。 > > 为什么需要以nums[i]结尾，因为我们后面循环遍历比较都是比较最后末尾的那个数，所以`必须是以它为结尾，构成的递增子序列` > > - 状态转移方程 > > index 0 1 2 3 4 5 > > ​ 0 1 0 3 2 3 > > dp[i] 1 2 1 3 3 4 > > **注意，必须把当前给包含进去** > > ​ 当前依赖于前面状态，i每次变化，都需要从头开始比较，因此额外导入变量j > > ​ j > ​ 只需要判断尾部 nums[i]>nums[j] 那么dp[i]=Math.max(dp[i],dp[j]+1) ,Math是因为循环找出最大值 > > **最后，因为每次dp[i]都是以nums[i]为结尾的最长递增子序列，所以并不一定就是最大的，最后比较下最大即可** > > - 初始化dp数组 > > dp[i]=1 ```js var lengthOfLIS = function (nums) { let dp = new Array(nums.length + 1).fill(1) dp[0] = 0 for (let i = 2; i < dp.length; i++) { for (let j = 1; j < i; j++) { if (nums[i - 1] > nums[j - 1]) { dp[i] = Math.max(dp[i], dp[j] + 1) } } } console.log(dp) //注意dp的定义，dp是指长度为i的最长递增子序列的个数，dp[dp.length-1]就说明了是对应长度为nums.length的最长递增子序列的个数 //但有一种情况是 [1,2,1] 最长的是[1,2],所以最后需要比较最值返回 // return dp[dp.length - 1] return Math.max(...dp) } ``` **从后往前遍历法** ```js var lengthOfLIS = function (nums) { let result = [[nums[0]]] for (let i = 1; i < nums.length; i++) { for (let j = result.length - 1; j >= 0; j--) { //result的尾元素 let line = result[j] let tail = line[line.length - 1] if (nums[i] > tail) { result[j + 1] = [...line, nums[i]] break } else if (nums[i] < tail && j == 0) { result[j] = [nums[i]] } } } return result } ``` ### [673. 最长递增子序列的个数](https://leetcode.cn/problems/number-of-longest-increasing-subsequence/) ```js /* 最长递增子序列的个数。首先你需要找到最长递增子序列的长度，然后统一计算个数 */ var findNumberOfLIS = function (nums) { let dp = new Array(nums.length + 1).fill(1) let count = new Array(nums.length + 1).fill(1) dp[0] = count[0] = 0 for (let i = 1; i < dp.length; i++) { for (let j = 1; j < i; j++) { if (nums[i - 1] > nums[j - 1]) { //如果尾部大于，判断递增子序列的长度 //[1 2 3 2] i==2 j=1 dp[i]==1 dp[j]=1 dp[i]=2 if (dp[i] < dp[j] + 1) { //找出递增子序列的最大长度 dp[i] = dp[j] + 1 //判断个数，只是长度变了，个数没变 count[i] = count[j] } else if (dp[i] == dp[j] + 1) { count[i] += count[j] } } } } //找出最长的递增子序列 let maxLength = Math.max(...dp) let sum = 0 for (let i = 0; i < count.length; i++) { if (dp[i] == maxLength) { sum += count[i] } } return sum } ``` *** ### [674. 最长连续递增序列](https://leetcode.cn/problems/longest-continuous-increasing-subsequence/) **这题本质上就是求最长连续递增子数组** - 思路①：遍历每个节点，如果nums[i]>nums[i-1] count++ ,不然count等于1，然后比较最大值 - 思路②：dp ```js var findLengthOfLCIS = function (nums) { /* let count = 1 let result = 1 for (let i = 1; i < nums.length; i++) { if (nums[i] > nums[i - 1]) { count++ } else { count = 1 } result = Math.max(count, result) } return result */ let dp = new Array(nums.length).fill(1) for (let i = 1; i < nums.length; i++) { if (nums[i] > nums[i - 1]) { dp[i] = dp[i - 1] + 1 } } return Math.max(...dp[i]) } ``` ### [718. 最长重复子数组](https://leetcode.cn/problems/maximum-length-of-repeated-subarray/) > 注意，最长重复子数组和最长公共子序列的区别。**首先，还是比较两个数组中的重复部分，所以定义二维dp，且还是比较尾序列** > > - 确定dp数组下标含义：dp[i] [j]表示长度为i的子数组num1和长度为j的子数组nums2的最长公共子数组的长度 > > - 状态转移方程： > > if(nums1[i-1]==nums2[j-1])，那么最长公共子数组长度+1 dp[i] [j]=dp[i-1] [j-1]+1 > > 如果不同，`无法处理`(不能仅仅理解为dp[i] [j]=dp[i-1] [j-1]，因为**不一定是去除掉nums1里的字符哦**) > > ![image-20240311103355183](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20240311103355183.png) > > 但是注意，dp[i] [j]表示的是下标为(0,i-1)的子数组和下标为(0,j-1)的子数组的最长公共子数组的长度，如果不同，就无需处理，所以无法肯定最后一个元素就是最大值(`这个和公共子序列就不一样了`，公共子序列如果尾序列不同，那还可以继续比较前面的) > > 因此，你只能每次遍历时，确保dp[i] [j]的最值 ```js var findLength = function (nums1, nums2) { let max = 0 let dp = new Array(nums1.length + 1).fill().map(() => new Array(nums2.length + 1).fill(0)) for (let i = 1; i <= nums1.length; i++) { for (let j = 1; j <= nums2.length; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1 max = Math.max(max, dp[i][j]) } } } return max } ``` ### [ 303.最长公共子序列](https://leetcode.cn/problems/qJnOS7/) - 确定dp数组和下标含义： ​ 很明显，两个序列求公共部分需要用到二维数组 ​ dp[i][j]表示长度为i的text1和长度为j的text2的最长公共子序列长度为dp[i][j]，注意必须是以(0,text1[i-1]) - 状态转移方程 abcde ace | dp[i] [j] | | 1 | 2 | 3 | | --------- | ---- | ---- | ---- | ---- | | | 0 | a | c | e | | 0 | 0 | 0 | 0 | 0 | | a | 0 | 1 | 1 | 1 | | b | 0 | 1 | 1 | 1 | | c | 0 | 1 | 2 | 2 | | d | 0 | 1 | 2 | 2 | | e | 0 | 1 | 2 | 3 | **很明显，结果需要从右下角得出，且当前状态依赖于前面状态，每次比较尾元素，如果相同，那么就dp[i] [j]=dp[i-1] [j-1]** **如果尾元素不同，则判断text1[0,i-2]与text2[0,j-1]和text1[0,i-1]与text2[0,j-2]比较最大值** （如abcd 和ac ，d与c不同就判断abc与ac或者是abcd与a） - **if(nums1[i-1]==nums2[j-1]) ** dp[i] [j]=dp[i-1] [j-1]+1 **if(nums1[i-1]!=nums2[j-1])** 那么则分为两种情况，求最大值：即(0,i-1)和(0,j-2)或者(0,i-2)和(0,j-1) ```js var longestCommonSubsequence = function (text1, text2) { let dp = new Array(text1.length + 1).fill().map(() => new Array(text2.length + 1).fill(0)) for (let i = 1; i <= text1.length; i++) { for (let j = 1; j <= text2.length; j++) { if (text1[i - 1] == text2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1 } else { dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) } } } return dp[text1.length][text2.length] } ``` ### 304.不相交的线 > 转化下思路，就是求最长公共子序列 ```js var maxUncrossedLines = function (nums1, nums2) { let dp = new Array(nums1.length + 1).fill().map(() => new Array(nums2.length + 1).fill(0)) for (let i = 1; i <= nums1.length; i++) { for (let j = 1; j <= nums2.length; j++) { if (nums1[i - 1] == nums2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1 } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) } } } return dp[nums1.length][nums2.length] } ``` ### [53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/) > 找出`子数组`，返回其最大和。 > > 1. 初始化dp数组和下标含义 > > dp[i]表示以nums[i]结尾的最大子数组和 (优点类似于最长递增子序列) > > 2. 状态转移方程 > > 完全不需要比较尾序列，只需要判断加上去是否变大即可 > > dp[i]=Math.max(dp[i-1]+nums[i],nums[i]) > > 最后判断哪个结尾的和最大即可 > > 3. 初始化dp数组 > > dp[0]=nums[0] ```js var maxSubArray = function (nums) { let dp = new Array(nums.length).fill(0) let result = 0 dp[0] = nums[0] for (let i = 1; i < nums.length; i++) { dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]) result = Math.max(result, dp[i]) } return result } ``` > 思路② 定义一个sum存储，如果当前sum>0,说明加下一个可能变大，如果sum已经小于0了，那么加下一个一定小，直接替换 ``` var maxSubArray = function (nums) { let result = nums[0] let sum = 0 for (let i = 1; i < nums.length; i++) { if (sum > 0) { sum += nums[i] } else { sum = nums[i] } result = Math.max(result, sum) } console.log(result) } ``` *** ### [306.判断子序列](https://leetcode.cn/problems/is-subsequence/) > 给定字符串s和t判断s是否为t的子序列。注意，是子序列，所以t是可以进行删除操作的 > > - 定义dp数组和下标含义 > > dp[i] [j]表示下标为(0,i-1)和字符串s是下标为(0,j-1)的字符串t的子序列 > > - 状态转移方程 > > 如果`尾序列相同`，那么只需要判断前面即可 > > if(s[i-1]==t[j-1]) dp[i] [j]=dp[i-1] [j-1] > > 如果尾序列不同，那么可以删除t的尾元素，继续比较(0,i-1)和(0,j-2) > > dp[i] [j]=dp[i] [j-1] > > - 初始化dp数组 > > dp[0] [0]=true > > 当i==0的时候，dp[0] [j]=true | | a | h | b | g | d | c | | | ---- | ----- | ---- | ---- | ---- | ---- | ---- | ---- | | a | true | true | true | true | true | true | | | b | false | | true | true | | | | | c | false | | | | | | | ```js var isSubsequence = function (s, t) { let dp = new Array(s.length + 1).fill().map(() => new Array(t.length + 1).fill(false)) for (let j = 0; j <= t.length; j++) { dp[0][j] = true } for (let i = 1; i <= s.length; i++) { for (let j = 1; j <= t.length; j++) { if (s[i - 1] == t[j - 1]) { dp[i][j] = dp[i - 1][j - 1] } else { dp[i][j] = dp[i][j - 1] } } } return dp[s.length][t.length] } ``` ### 307.不同子序列的个数(hard) **这题难度在于思路，是可以删除s的** > s中可能出现多个t，返回s中t的个数。注意，可以删除字符串s中的元素 > > - 定义dp数组和下标含义 > > dp[i] [j]表示(0,i-1)的字符s中出现(0,j-1)字符t的个数 > > - 状态转移方程 > > 一般两个字符都是比较**尾序列** > > 如果尾元素相同：if(s[i-1] == t[j-1]) > > dp[i] [j]=dp[i-1] [j-1] **相同时，但还有一种情况** > > ![image-20240312110237521](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20240312110237521.png) > > s[i-1]=='g' t[j-1]=='g'，还需要继续比较字符baeg和字符bag > > 即dp[i] [j]=dp[i-1] [j] > > 因此，dp[i] [j]=dp[i-1] [j-1]+dp[i-1] [j] > > 当s[i-1]!=t[j-1]时，dp[i] [j]=dp[i-1] [j]，就删除一个，比较前面序列的 > > - 初始化dp数组 > > 当t为空串时，dp[i] [0]=1 ```js var numDistinct = function (s, t) { let dp = new Array(s.length + 1).fill().map(() => new Array(t.length + 1).fill(0)) for (let i = 0; i <= s.length; i++) { dp[i][0] = 1 } dp[0][0]=1 for (let i = 1; i <= s.length; i++) { for (let j = 1; j <= t.length; j++) { if (s[i - 1] == t[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] } else { dp[i][j] = dp[i - 1][j] } } } return dp[s.length][t.length] } ``` ### [583. 两个字符串的删除操作](https://leetcode.cn/problems/delete-operation-for-two-strings/) > 字符串word1和word2两个字符都可以进行删除。定义二维dp数组，进行尾序列比较 > > - dp[i] [j]表示(0,i-1)的字符串word1变成(0,j-1)的字符串word2所需要的最少步数 > > - 状态转移方程 > > - if(word1[i-1]==word2[j-1]) > > dp[i] [j]=dp[i-1] [j-1] > > - word1[i-1]!=word2[j-1] > > 那么可以分为三种情况，三种取最小值 > > 1. 删除word1的尾元素，继续比较 word1(0,i-2),word2(0,j-1) > 2. 删除wrod2的尾元素，继续比较 word1(0,i-1),word2(0,j-2) > 3. 删除word1和word2的尾元素，继续比较 word1(0,i-2),word2(0,j-2) > > dp[i] [j]=Math.min(dp[i-1] [j]+1,dp[i] [j-1]+1,dp[i-1] [j-1]+2) > > - 初始化dp数组 > > 当word1为空串 dp[0] [j]=j dp[i] [0]=i ```js var minDistance = function (word1, word2) { let dp = new Array(word1.length + 1).fill().map(() => new Array(word2.length + 1).fill(0)) for (let i = 0; i <= word1.length; i++) { dp[i][0] = i } for (let j = 0; j <= word2.length; j++) { dp[0][j] = j } for (let i = 1; i <= word1.length; i++) { for (let j = 1; j <= word2.length; j++) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] } else { dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 2) } } } return dp[word1.length][word2.length] } ``` ### [72. 编辑距离](https://leetcode.cn/problems/edit-distance/) > 对word1进行操作，添加删除替换让其变为word2。双字符串比较问题，需要用二维数组dp，尾序列进行比对 > - 定义dp数组和下标含义 > > dp[i] [j]表示字符串word1(0,i-1)转换成字符串(0,j-1)所需要的最少操作数 > > - 状态转移方程 > > - **if(word1[i-1]==word2[j-1])** > > 如果尾序列相同，那么就无需操作dp[i] [j]=dp[i-1] [j-1] > > - **if(word1[i-1]!=word2[j-1])** > > 尾序列不同，有三种操作方式，删除、替换、添加 > > - 删除 word1[i-1] 继续比较字符序列(0,i-2)和(0,j-1) > - 替换 继续比较(0,i-1)和(0,j-2) > - 添加，添加可以转化思路，变成删除word2[j-1] 继续比较(0,i-1)和(0,j-2) > > dp[i] [j]=Math.min(dp[i-1] [j]+1,dp[i-1] [j-1]+1,dp[i] [j-1]+1) > > - 初始化dp数组 > > 当word1为空，dp[0] [j]=j word2为空dp[i] [0]=i ```js var minDistance = function (word1, word2) { let dp = new Array(word1.length + 1).fill().map(() => new Array(word2.length + 1).fill(0)) for (let i = 0; i <= word1.length; i++) { dp[i][0] = i } for (let j = 0; j <= word2.length; j++) { dp[0][j] = j } for (let i = 1; i <= word1.length; i++) { for (let j = 1; j <= word2.length; j++) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] } else { dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1, dp[i][j - 1] + 1) } } } return dp[word1.length][word2.length] } ``` ## 单调栈 **单调栈的使用场景：一个一维数组，需要寻找左边或者右边，`第一个比自己大或小的元素的位置`就可以使用单调栈优化** 单调栈一定可以使用双重for循环暴力破解，它本质上就是用空间换时间，**用一个栈来记录遍历过的元素** 注意点： - 单调栈里存放下标即可，使用元素直接通过 nums[i]获取 - 单调栈里元素需要递增或者递减 ### 1.每日温度 > 双重for循环解法：会超出时间限制 ``` var dailyTemperatures = function (temperatures) { let result = new Array(temperatures.length).fill(0) for (let i = 0; i < temperatures.length; i++) { for (let j = i + 1; j < temperatures.length; j++) { if (temperatures[j] > temperatures[i]) { result[i] = j - i break } } } return result } ``` > 单调栈 ```js var dailyTemperatures = function (temperatures) { let result = new Array(temperatures.length).fill(0) let stack = [0] for (let i = 0; i < temperatures.length; i++) { let topIndex = stack[stack.length - 1] while (stack.length && temperatures[i] > temperatures[topIndex]) { //计算距离 result[topIndex] = i - topIndex stack.pop() topIndex = stack[stack.length - 1] } stack.push(i) } return result } ``` ### 496.下一个更大元素 > 双重for循环 ```js var nextGreaterElement = function (nums1, nums2) { let result = new Array(nums1.length).fill(-1) for (let i = 0; i < nums1.length; i++) { let index = nums2.findIndex((item) => item == nums1[i]) for (let j = index + 1; j < nums2.length; j++) { if (nums2[j] > nums1[i]) { result[i] = nums2[j] break } } } return result } ``` ### 497.下一个更大元素Ⅱ > 思路：它是在当前数组中循环遍历，找出最大，类似于打家劫舍，只需要拼接下数组即可 ```js var nextGreaterElements = function (nums) { let result = new Array(nums.length).fill(-1) nums = [...nums, ...nums] for (let i = 0; i < nums.length / 2; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[j] > nums[i]) { result[i] = nums[j] break } } } return result } ``` ### 42.接雨水 > 经典保留题目，计算出最高柱子，然后从左往右，从右往左分别计算 ```js var trap = function (height) { let maxHeight = Math.max(...height) let maxIndex = height.findIndex((item) => item == maxHeight) let result = 0 let leftHeight = height[0] let rightHeight = height[height.length - 1] for (let i = 0; i < maxIndex; i++) { leftHeight = Math.max(leftHeight, height[i]) result += leftHeight - height[i] } for (let i = height.length - 1; i > maxIndex; i--) { rightHeight = Math.max(rightHeight, height[i]) result += rightHeight - height[i] } return result } ``` ### 84.柱形图中最大的矩形 > - 思路1：暴力法。for循环遍历每一根柱子，然后双指针定义左右left、right，如果height[left]或者height[right]>=heigth[i]，那么继续放缩,然后计算矩形面积即可 > > ```js > var largestRectangleArea = function (heights) { > let result = 0 > for (let i = 0; i < heights.length; i++) { > let left = i - 1 > let right = i + 1 > while (heights[left] && heights[left] >= heights[i]) { > left-- > } > while (heights[right] && heights[right] >= heights[i]) { > right++ > } > //计算面积 > result = Math.max(result, heights[i] * (right - left - 1)) > } > return result > } > ``` > **单调栈解法：** > ​ 如果遇到更高的，那么面积一定是增大的。 > > ​ 如果遇到矮的，那么面积可能大可能小，所以需要维持一个单调递增栈。 > > ​ 当遇到比它小的，就出栈一个topIndex，计算以它为高的元素，宽度是当前i-stack[stack.length-1]-1 > > > > ​ 如果还是比栈顶元素小，继续出栈。计算以其出栈元素为高的大小，因为栈是单调递增栈的，所以之前出栈的绝对比它大 > > ​ 类似于5 6 4 ，6先出栈计算以6为高度，然后5出栈，计算以5为高度 > > > > ​ 边界处理：为了保证都能出栈都能入栈，前后加个0 > > > > ​ 宽度处理 0 5 6 4 0 先 5 6入栈，遇到4，6出栈，计算以6为高度，宽度为3-1-1 > > ​ 然后5出栈计算以5为高度，宽度为3-0-1=2 面积为10 > > ​ 然后4入栈，遇到0，4出栈，计算以高度为4，宽度为4-0-1 (这个-1就是为了最后这个0入栈，前面的全出栈，前面还多个0， 所以宽度-1) ```js var largestRectangleArea = function (heights) { let maxArea = 0 const stack = [] heights = [0, ...heights, 0] for (let i = 0; i < heights.length; i++) { while (heights[i] < heights[stack[stack.length - 1]]) { let topIndex = stack.pop() maxArea = Math.max(maxArea, heights[topIndex] * (i - stack[stack.length - 1] - 1)) } stack.push(i) } return maxArea } console.log(largestRectangleArea([5, 6, 4])) ``` ## 图论 > 图相关题目一般也是找出所有路径。分为深度优先搜索和广度优先搜索，即dfs和bfs ### dfs理论基础 - dfs：深度优先搜索，即一条路径走到头，走不下去了，回溯一步。**dfs用的是递归+回溯** ```js function dfs(){ 处理节点 dfs()递归 回溯 } ``` **回溯算法三步走** 1. 确定终止条件 2. 确定集合范围 3. 进行递归和回溯 **因此，回溯算法其实就是dfs带有撤销操作** ```js void dfs(参数) { if (终止条件) { 存放结果; return; } for (选择：本节点所连接的其他节点) { 处理节点; dfs(图，选择的节点); // 递归 回溯，撤销处理结果 } } ``` ### [110. 所有可能的路径](https://leetcode.cn/problems/bP4bmD/) > 1. 确定递归函数、参数 > > **dfs图和dfs树形结构类似，每次dfs的时候都需要是同一个图，还需要一个变量存放我们目前遍历到的节点** > > 2. 确定终止条件 > > 何时终止，当我们遍历到的节点为最后一个节点，即终止 > > 当x==graph.length-1 > > 3. 确定集合范围 > > 接下来走的是x可链接的下一个点位 > > for(let i=0;i > ​ path.push(graph[x] [i]) > > ​ //下一层递归 dfs() > > ​ path.pop() //回溯 > > } > > > 首先我们要理解题目意思，从0这个节点开始，访问它可以经过的节点。将它经过的节点推入到path中。接着dfs它经过的那个节点它可访问到哪一项 ```js var allPathsSourceTarget = function (graph) { let result = [] let path = [0] //start确定遍历到哪一项 function dfs(path, start) { //终止条件 if (start == graph.length - 1) { return result.push([...path]) } for (let i = 0; i < graph[start].length; i++) { path.push(graph[start][i]) //当前遍历到1，下一次从1周边找 dfs(path, graph[start][i]) //继续从当前节点查找 path.pop() } } dfs(path, 0) //从0开始，然后遍历第0项可访问的路径 } ``` ### bfs理论基础 > 二叉树中，bfs我们一般会使用队列。将每一层的节点推入队列中，然后依次出队列，而且出了以后，再将子节点入队列 > > ```js > function bfs(root) { > let result = [] > let queue = [root] > while (queue.length) { > let len = queue.length > result.push([]) > for (let i = 0; i < len; i++) { > let node = queue.shift() > result[result.length - 1].push(node.val) > if (node.left) { > queue.push(node.left) > } > if (node.right) { > queue.push(node.right) > } > } > } > console.log(result) > } > bfs(tree) > ``` > > **图论相关题目其实也是相同的，也可以用队列的方式** ### [463. 岛屿的周长](https://leetcode.cn/problems/island-perimeter/) > 岛屿类型题目，一版都是先找到满足条件的那个岛屿，然后通过 `dfs` 深搜岛屿四周。注意，`遍历过的需要置灰，防止重复遍历` > 思路：遍历到一个岛屿的时候，dfs岛屿四周，如果**遇到了水或者边界，那么周长就+1**。为了避免超时，需要去重 ```js var islandPerimeter = function (grid) { let m = grid.length let n = grid[0].length let sum = 0 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] == 1) { dfs(i, j) } } } return sum function dfs(i, j) { if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) { sum++ return } if (grid[i][j] == -1) return grid[i][j] = -1 dfs(i - 1, j) dfs(i + 1, j) dfs(i, j - 1) dfs(i, j + 1) } } ``` ### [200. 岛屿数量](https://leetcode.cn/problems/number-of-islands/) > 思路：首先遍历grid，找到对应的岛屿1，总数+1、然后dfs岛屿周围，如果是1就置0，然后继续dfs四周 ```js var numIslands = function (grid) { let m = grid.length let n = grid[0].length let result = 0 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] == "1") { result++ dfs(i, j) } } } function dfs(i, j) { if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == "0") { return } grid[i][j] = "0" dfs(i - 1, j) dfs(i + 1, j) dfs(i, j - 1) dfs(i, j + 1) } return result } ``` ### [105. 岛屿的最大面积](https://leetcode.cn/problems/ZL6zAn/) > 思路：这题和岛屿的数量区别在于，它需要知道每一块的面积，所以不能在外界定义sum，而是要在**dfs的时候增大面积进行比较**，每次找到岛屿的时候，就重置为0 ```js var maxAreaOfIsland = function (grid) { let m = grid.length let n = grid[0].length let count = 0 let result = 0 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] == "1") { count = 0 dfs(i, j) result = Math.max(count, result) } } } function dfs(i, j) { if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) { return } count++ grid[i][j] = "0" dfs(i - 1, j) dfs(i + 1, j) dfs(i, j - 1) dfs(i, j + 1) } return result } ``` ### [1020. 飞地的数量](https://leetcode.cn/problems/number-of-enclaves/) > 思路：首先遍历最外围，如果遇到岛屿，就dfs，让其接壤的都变成0。**然后就是岛屿的数量问题，外界定义一个sum即可** ```js var numEnclaves = function (grid) { let m = grid.length let n = grid[0].length let count = 0 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (i == 0 || j == 0 || i == m - 1 || j == n - 1) { if (grid[i][j] == 1) { dfs(i, j, true) } } } } function dfs(i, j, isReset) { if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) { return } if (!isReset) { count++ } grid[i][j] = 0 dfs(i - 1, j, isReset) dfs(i + 1, j, isReset) dfs(i, j - 1, isReset) dfs(i, j + 1, isReset) } for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (grid[i][j] == 1) { dfs(i, j, false) } } } return count } ``` ### [130. 被围绕的区域](https://leetcode.cn/problems/surrounded-regions/) > 思路：首先跟飞地一样，找出`边界上的所有O`即岛屿，但是用 `Z`填充（因为后面要复位为O），然后找出内部所有的O替换成X即可 ```js var solve = function (board) { let m = board.length let n = board[0].length for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (i == 0 || j == 0 || i == m - 1 || j == n - 1) { if (board[i][j] == "O") { dfs(i, j, true) } } } } function dfs(i, j, isReset) { if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == "X" || board[i][j] == "Z") { return } if (isReset) { board[i][j] = "Z" } else { board[i][j] = "X" } dfs(i - 1, j, isReset) dfs(i + 1, j, isReset) dfs(i, j - 1, isReset) dfs(i, j + 1, isReset) } //遍历，将内部无关联O 置为X for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (board[i][j] == "O") { dfs(i, j, false) } } } for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (board[i][j] == "Z") { board[i][j] = "O" } } } return board } ``` ### [79. 单词搜索](https://leetcode.cn/problems/word-search/) > 从0开始，遍历到最后一个字母，每次遍历(i,j)时，遍历四周只要有一个满足条件，就继续深度遍历即可 ```js var exist = function (board, word) { let m = board.length let n = board[0].length function backTracking(i, j, index) { if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == 0 || board[i][j] != word[index]) { return false } if (index == word.length - 1) return true let temp = board[i][j] board[i][j] = 0 let res = backTracking(i - 1, j, index + 1) || backTracking(i + 1, j, index + 1) || backTracking(i, j - 1, index + 1) || backTracking(i, j + 1, index + 1) board[i][j] = temp return res } for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (board[i][j] == word[0]) { let res = backTracking(i, j, 0) if (res) return true } } } return false } ``` # Leedcode hot100 ## 1.两数之和 > for循环双重遍历，返回index即可。第二种优化思路：空间换时间，用map存储所有的数组元素，然后用减法获取差值，再在map中确定index ```js var twoSum = function (nums, target) { for (let i = 0; i < nums.length; i++) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { return [i, j] } } } } ``` ## 2.两数相加 > 这题唯一要注意的时候，每次都需要l1=l1.next l2=l2.next然后还需要判断最后carry是否存在 ```js var addTwoNumbers = function (l1, l2) { let head = new ListNode(0) let p = head let sum = 0 let carry = 0 while (l1 && l2) { sum = (l1.val + l2.val + carry) % 10 carry = parseInt((l1.val + l2.val + carry) / 10) let node = new ListNode(sum) p.next = node p = p.next l1 = l1.next l2 = l2.next } while (l1) { sum = (carry + l1.val) % 10 carry = parseInt((carry + l1.val) / 10) let node = new ListNode(sum) p.next = node p = p.next l1 = l1.next } while (l2) { sum = (carry + l2.val) % 10 carry = parseInt((carry + l2.val) / 10) let node = new ListNode(sum) p.next = node p = p.next l2 = l2.next } if (carry > 0) { let node = new ListNode(carry) p.next = node } return head.next } ``` ## [3. 无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters/) > 思路： > > 1. 子串问题肯定可以双重for循环，找出所有的子串，然后判断无重复字符的最长子串即可。时间复杂度On^3 > 2. 定义一个map，存放所有字符出现的位置。定义一个left指针，指向无重复的子串的开始位置。遍历字符串s，如果有重复的，就跳到重复字符的下一个。 > 2. 为什么 `map.get(s[i])>=left`需要 **>=**，这是因为left初始值为0，获取到的第一个字符重复下标也一定是0。为什么不能定义负数，因为如果没有重复，left为-1，那么res就肯定会变大。为什么res不能放在if判断里面，因为如果遇到 abccdefgh，没有重复的呢？ ```js var lengthOfLongestSubstring = function (s) { let map = new Map() let left = 0 let res = 0 for (let i = 0; i < s.length; i++) { if (map.has(s[i]) && map.get(s[i]) >= left) { left = map.get(s[i]) + 1 } map.set(s[i], i) res = Math.max(res, i - left + 1) } return res } ``` ## [5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/) > 思路：双边放缩法 ```js var longestPalindrome = function (s) { let res = '' for (let i = 0; i < s.length; i++) { let temp = 1 let left = i - 1 let right = i + 1 while (s[left] && s[left] == s[i]) { left-- temp++ } while (s[right] && s[right] == s[i]) { right++ temp++ } while (s[left] && s[right] && s[left] == s[right]) { temp += 2 left-- right++ } if (res.length < temp) { //substr第二个参数是长度 res = s.substr(left + 1, temp) } } return res } ``` ## [10. 正则表达式匹配（hard）](https://leetcode.cn/problems/regular-expression-matching/) > 思路：很明显的动态规划题目 > > 1. 初始化dp数组和下标含义 > > 设dp[i] [j]表示`长度为i的字符s和长度为j的字符p是否匹配`。当字符s长度为i，它可用下表s(0,i-1)表示 > > 2. 推导状态转移方程 > > 因为*要考虑前一个字符，所以我们从后往前来推。 > > `长度为i的字符s的最后一个字符s[i-1]`与长度为j的字符串p的最后一个字符p[j-1]相同，即 > > - **情况1** `if(s[i-1]==p[j-1]||p[j-1]=='.')`，那么当前dp[i] [j]只需要考虑s(0,i-2)与p0(j-2)是否匹配 > > dp[i] [j]=dp[i-1] [j-1] > > - **情况2** 如果s[i-1]!=p[j-1]，也不要慌，还有两种情况 > > **情况2.1** 如果p[j-1]!='*',那就没结果,不可能匹配的 > > **情况2.2** 如果`p[j-1]=='*'`，那么我们就需要比较`s[i-1]和p[j-2]`了 > > - `if(s[i-1]==p[j-2]||p[j-2]=='.')`,这张情况下，*号可以让前面的字符出现0次，1次，多次 > > 1. **出现0次的情况，如 aab aacbb* **，我们需要去除p末尾的一个b，接着比较s(0,i-1)和p(0,j-3) > > dp[i] [j]=dp[i] [j-2] > > 3. **出现多次的情况，如 aabbbbb aacb***。**我们可以转化思路，不给p添加多个，每次先去掉s的一个末尾，继续比较剩余的，即继续比较s(0,i-2)和p(0,j-1)**。`注意：*号要带上比较，因为可能要去掉多次` > > dp[i] [j]=dp[i-1] [j] > > > 没有出现一次的情况，因为它是让前面那个重复，如果重复一次，还是多了，所以只能删除 > > - `if(s[i-1]!=p[j-2])`，也不要慌，因为p[j-1]=='*',它可以删除p[j-2],所以继续比较s(0,i-1)和p(0,j-3)即可 > > dp[i] [j]=dp[i] [j-2] > > 3. **初始化dp数组** > > dp数组初始化肯定是二维的，dp[0] [0]=true，长度为0时自然匹配成功 > > 重点：当s为空时，我们需要判断p[j-1]是否为*，如果p[j-1]= = ' *'的话，它可以删除p[j-2],只需要继续比较s和p(0,j-3)即可 > > 我们只需要判断dp[0] [j]=dp[0] [j-2] ```js var isMatch = function (s, p) { let dp = new Array(s.length + 1).fill().map(() => new Array(p.length + 1).fill(false)) dp[0][0] = true for (let j = 0; j <= p.length; j++) { if (p[j - 1] == '*') { dp[0][j] = dp[0][j - 2] } } for (let i = 1; i <= s.length; i++) { for (let j = 1; j <= p.length; j++) { if (s[i - 1] == p[j - 1] || p[j - 1] == '.') { dp[i][j] = dp[i - 1][j - 1] } else if (p[j - 1] == '*') { if (s[i - 1] == p[j - 2] || p[j - 2] == '.') { dp[i][j] = dp[i][j - 2] || dp[i - 1][j] } else { dp[i][j] = dp[i][j - 2] } } } } return dp[s.length][p.length] } ``` ## [11. 盛最多水的容器](https://leetcode.cn/problems/container-with-most-water/) > 思路：双指针，判断哪个小，就移动哪个 ```js var maxArea = function (height) { let left = 0 let right = height.length - 1 let maxSum = 0 while (left < right) { let h = Math.min(height[left], height[right]) maxSum = Math.max(maxSum, h * (right - left)) if (height[left] < height[right]) { left++ } else { right-- } } return maxSum } ``` ## [15. 三数之和](https://leetcode.cn/problems/3sum/) > 思路：双指针。 当sum为0的时候进行去重 还有nums去重 > > - 注意：双指针一定要用while(left a - b) let res = [] for (let i = 0; i < nums.length; i++) { if (nums[i] == nums[i - 1]) continue let left = i + 1 let right = nums.length - 1 while (left < right) { let sum = nums[i] + nums[left] + nums[right] if (sum == 0) { while (nums[left] == nums[left + 1]) { left++ } while (nums[right] == nums[right - 1]) { right-- } res.push([nums[i], nums[left], nums[right]]) left++ right-- } //注意：sum需要分为三种情况考虑 else if (sum < 0) { left++ } else { right-- } } } return res } ``` **** ## [17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/) > 这题是很经典的回溯题目，比如digits='23' ,首先需要确定终止条件，当path.length==digits.length就终止。②确定集合范围，因此需要自定义一个map ```js var letterCombinations = function (digits) { if (!digits.length) return [] const map = { 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz' } const res = [] function backTracking(path, start) { //确定终止条件 if (path.length == digits.length) { return res.push([...path].join('')) } //确定集合范围 let str = map[digits[start]] for (let i = 0; i < str.length; i++) { path.push(str[i]) backTracking(path, start + 1) path.pop() } } backTracking([], 0) return res } ``` ## [19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/) > 思路：一般链表问题都需要定义虚拟头节点。这样头节点就不需要单独考虑。删除节点一般会考虑快慢指针法 ```js var removeNthFromEnd = function (head, n) { let dummy = new ListNode(0, head) let fast = dummy let slow = dummy while (n--) { fast = fast.next } if (!fast) return dummy.next while (fast && fast.next) { slow = slow.next fast = fast.next } let next = slow.next.next slow.next = next return dummy.next } ``` ## 20.有效的括号 > 括号类题目一般都会通过栈的方式 ```js var isValid = function (s) { let stack = [] let leftStr = '([{' let rightStr = ')]}' function isPali(leftChar, rightChar) { if (leftChar == '(' && rightChar == ')') return true if (leftChar == '{' && rightChar == '}') return true if (leftChar == '[' && rightChar == ']') return true return false } for (let i = 0; i < s.length; i++) { if (leftStr.includes(s[i])) { stack.push(s[i]) } else { let char = stack.pop() if (!isPali(char, s[i])) { return false } } } if (stack.length) return false return true } ``` ## 21.合并两个有序链表 > 链表类题目一定要弄个虚拟头节点 ```js /* 合并两个链表有点类似于两个链表相加，一般双链表题目都是通过while(list1&&list2)然后再判断两个链表是否存在 */ var mergeTwoLists = function (list1, list2) { let dummy = new ListNode(0, null) let p = dummy while (list1 && list2) { if (list1.val <= list2.val) { // let node = new ListNode(list1.val) /* 其实不需要创建节点 */ p.next = list1 list1 = list1.next p = p.next } else { p.next = list2 list2 = list2.next p = p.next } } if (list1) { p.next = list1 } if (list2) { p.next = list2 } return dummy.next } ``` ## [22. 括号生成](https://leetcode.cn/problems/generate-parentheses/) > 思路：要求根据长度生成括号，很明显，是一道回溯类题目。 > > - 确定终止条件，当右括号个数大于左括号，肯定不匹配。当左括号个数大于n的时候，肯定也不匹配。只有当左右括号个数等于2*n才满足条件 > - 确定集合范围，每次递归的时候，path+'(',左右括号个数+1，回溯因为是字符串，所以自动就去掉了 ```js var generateParenthesis = function (n) { let res = [] function backTracking(path, left, right) { if (left > n) return if (right > left) return if (left + right == 2 * n) { return res.push(path) } backTracking(path + '(', left + 1, right) backTracking(path + ')', left, right + 1) } backTracking('', 0, 0) return res } ``` ## [31. 下一个排列](https://leetcode.cn/problems/next-permutation/) > 从后往前，找到第一个比后面小的数。 > > - 如果找不到，那么就说明数组是递减的，直接按照递增排序返回即可。 > > - 如果找到了，继续循环遍历[index+1,nums.length-1],找到第一个比它大的数，进行交换。这时候得到 1 2 4 6 5 3 3 2 1 > > 最后只需要把从6开始到1，进行一个排序即可 ```JS /* 1 2 3 6 5 4 3 2 1 思路：从后往前，找到第一个比后面一位小的数 1 2 4 6 5 3 3 2 1 */ var nextPermutation = function (nums) { let index = -1 for (let i = nums.length - 2; i >= 0; i--) { if (nums[i] < nums[i + 1]) { index = i break } } if (index == -1) { nums.sort((a, b) => a - b) return nums } //找到递减序列中第一个比nums[index]大的数，进行交换 剩下递减序列排序为升序即可 for (let i = nums.length - 1; i > index; i--) { if (nums[i] > nums[index]) { ;[nums[i], nums[index]] = [nums[index], nums[i]] break } } //接下来在排序,因为替换以后，可以确定右侧是递减序列 let left = index + 1 let right = nums.length - 1 while (left < right) { ;[nums[left], nums[right]] = [nums[right], nums[left]] left++ right-- } return nums } ``` ## [32. 最长有效括号（hard）](https://leetcode.cn/problems/longest-valid-parentheses/) > ​ 思路：一般来说，括号匹配问题会用栈来匹配，注意，栈一般都是用来存放下标的 > > ​ 定义一个栈，存放括号对应的下标，如果遇到 ( 就入栈，遇到 > > ​ )就出栈，同时长度为当前下标-栈顶元素下标 > > > > ​ 但是会遇到特殊情况: > > ​ ( ) (()) `)` > > ​ 当遇到下标为6的 ) ，这时候又应该出栈，但是栈顶元素已经空了 > > ​ 如何出栈呢？而且它应该计算的最长有效括号，目前只是4，但实际应该是6 > > ​ () (()),如果只是单纯的用右括号的下标-栈顶元素下标，那么前面的()已经出栈了，最长有效括号只能是4，所以有问题 > > > > ​ 问题：因为无法记录之前已经出栈过的匹配成功的下标，因此往栈里提前存放一个下标-1 > > ​ 遇到左括号还是进栈，遇到右括号还是先出栈,(`如果栈内还有元素`，**因为你比较长度是当前下标和栈顶元素，所以必须栈内还有元素**)，最长长度是`当前下标-栈顶元素下标`。如果这时候栈空了，那么就让右括号下标入栈，继续做个标志。 > > ​ -1 () `)` ()() ，遇到 `）`，让-1出栈，这时候栈空了，没法计算长度，因此让 `)`下标2入栈，再到最后，最长长度是下标6-2=4 ，完美！ ```js var longestValidParentheses = function (s) { let stack = [-1] let len = 0 for (let i = 0; i < s.length; i++) { if (s[i] == '(') { stack.push(i) } else { stack.pop() if (stack.length) { len = Math.max(len, i - stack[stack.length - 1]) } else { stack.push(i) } } } return len } ``` ## [39. 组合总和](https://leetcode.cn/problems/combination-sum/) > 思路：组合问题一定是用回溯法。因为是无重复数字，且数组元素可以重复选用，因此我们无需去重。每次回溯还是以当前元素开始。 > > - 确定终止条件 > > ①：**当前sum和大于target** > > ②：当前sum==target，进入result > > - 确定循环遍历条件。每次循环candidates数组，从当前元素开始。 ```js var combinationSum = function (candidates, target) { let result = [] function backTracking(path, start, sum) { if (sum > target) return if (sum == target) { return result.push([...path]) } for (let i = start; i < candidates.length; i++) { path.push(candidates[i]) /* 注意：sum+candidates[i]必须放在每次回溯，如果放在path.push后面，那么回溯结束必须把sum-回去 */ backTracking(path, i, sum + candidates[i]) path.pop() /* 写法二 path.push(candidates[i]) sum+=candidates[i] backTracking(path,sum, i) sum-=candidates[i] path.pop() */ } } backTracking([], 0, 0) return result } ``` ## [42. 接雨水](https://leetcode.cn/problems/trapping-rain-water/) > 思路：双指针。找出最高的那根柱子，然后从左往中，找出左边最高柱子。右边同理。 ```js var trap = function (height) { let maxHeight = 0 let maxIndex = 0 let result = 0 for (let i = 0; i < height.length; i++) { if (height[i] > maxHeight) { maxHeight = height[i] maxIndex = i } } let leftMaxHeight = 0 let rightMaxHeight = 0 for (let i = 0; i < maxIndex; i++) { leftMaxHeight = Math.max(leftMaxHeight, height[i]) result += leftMaxHeight - height[i] } for (let i = height.length - 1; i > maxIndex; i--) { rightMaxHeight = Math.max(rightMaxHeight, height[i]) result += rightMaxHeight - height[i] } return result } ``` ## [46. 全排列](https://leetcode.cn/problems/permutations/) > 排列问题：回溯法 > > - 确定终止条件 > > path.length==nums.length > > - 确定循环遍历条件 > > 因为是排列问题，所以顺序有效。每个元素都可以使用。定义一个use数组，判断每个元素是否被使用 > > for(let i=0;i 思路：先上下进行翻转，然后根据对称轴进行翻转。(对称轴翻转只需要让j=i即可，即上半部分) > > ![image-20240622132407722](https://gitee.com/zhengdashun/pic_bed/raw/master/img/image-20240622132407722.png) ```js var rotate = function (matrix) { let m = matrix.length let n = matrix[0].length let top = 0 let bottom = m - 1 while (top < bottom) { ;[matrix[top], matrix[bottom]] = [matrix[bottom], matrix[top]] top++ bottom-- } for (let i = 0; i < m; i++) { for (let j = i; j < n; j++) { ;[matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]] } } return matrix } ``` ## [49. 字母异位词分组](https://leetcode.cn/problems/group-anagrams/) > 思路：遍历strs数组，对每一项进行字母排序 **注意：字母排序从小到大只能直接sort()**。然后用map判断是否存在，存在推入，不存在重新创建再推入。 > > `注意：这题的问题先是字符串变成数组后再排序、其次就是map.get(str).push(strs[i])不能连着写` ```js var groupAnagrams = function (strs) { let map = new Map() let result = [] for (let i = 0; i < strs.length; i++) { let s = strs[i].split("").sort().join("") if (map.has(s)) { let list = map.get(s) map.set(s, [...list, strs[i]]) } else { map.set(s, [strs[i]]) } } for (let [key, value] of map) { result.push(value) } return result } ``` ## 51.N皇后(hard) > 思路：把它转换成一棵树，每次填一行，因此我们需要判断填该行中的哪一列符合条件。需要定义isValid函数 > > ①终止条件：row==n 推入res > > ②确定循环遍历范围，遍历该行中的每一列，只有符合条件的才转换棋盘中的 '.' ```js var solveNQueens = function (n) { const res = [] const chessboard = new Array(n).fill().map(() => new Array(n).fill(".")) function backTracking(row, chessboard) { if (row == n) return res.push(transform(chessboard)) for (let col = 0; col < n; col++) { if (isValid(row, col, chessboard, n)) { chessboard[row][col] = "Q" backTracking(row + 1, chessboard) chessboard[row][col] = "." } } } backTracking(0, chessboard) return res function transform(chessboard) { return chessboard.map((item) => item.join("")) } function isValid(row, col, chessboard, n) { //无需检查同行，因为每一行只会有一个Q //检查是否同列 for (let i = 0; i < row; i++) { if (chessboard[i][col] == "Q") return false } //检查45° for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (chessboard[i][j] == "Q") return false } //检查135 //注意必须用&& for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (chessboard[i][j] == "Q") return false } return true } } ``` ## 51.1重新安排行程(hard) > 这题类似于二叉树遍历一条边。只要有一个符合条件就直接return即可。 > > 思路：首先定义一个map确定from，to。然后对to进行排序。 > > ①终止条件：当机票用完且目的地全部达到 if(result.length==tickets.length+1) return true > > ​ 不然的话，找寻下一个可去往的城市数组， map.get(res[res.length-1]) > > ​ 剪枝操作：如果城市数组为空，且机票没用完 return false > > ②确定循环遍历返回 > > ​ 循环遍历可去往的下一个城市数组，同时对数组进行处理splice > > ​ 回溯时要对数组也进行还原 ```js var findItinerary = function (tickets) { const result = ["JFK"] let map = new Map() for (let i = 0; i < tickets.length; i++) { let [from, to] = tickets[i] if (!map.has(from)) { map.set(from, []) } map.get(from).push(to) } for (let [key, value] of map) { value.sort() } function backTracking() { //机票用完，找到了一条边 if (result.length == tickets.length + 1) { return true } //机票未用完,找到可去往城市 let nextCities = map.get(result[result.length - 1]) if (!nextCities || !nextCities.length) { return false } for (let i = 0; i < nextCities.length; i++) { //为了还原city，所以必须临时保存下 let city = nextCities[i] result.push(city) nextCities.splice(i, 1) //递归 if (backTracking()) return true //回溯 result.pop() nextCities.splice(i, 0, city) } } backTracking() return result } ``` ## [53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/) > 思路: > > - 暴力。子数组问题一定可以双重for循环找出所有子数组，然后判断最大值。时间复杂度On > - 指针法。定义一个sum作为临时变量，如果当前sum>=0，那么sum+=nums[i],如果sum<0那么sum=nums[i] ```js //题目说明了：数组中至少含有一个元素，所以无需判断了 var maxSubArray = function (nums) { let sum = nums[0] let result = nums[0] for (let i = 1; i < nums.length; i++) { if (sum >= 0) { sum += nums[i] } else { sum = nums[i] } result = Math.max(sum, result) } return result } ``` ## [55. 跳跃游戏](https://leetcode.cn/problems/jump-game/) > 思路：每个i+nums[i]即当前位置可跳过的范围。因此，每走一步就需要计算出当前位置可跳跃的最大范围cover:i+nums[i]。 > > `注意：我们遍历时，必须让i<=cover` **只能在可跳跃范围内进行跳跃** > > ```js var canJump = function (nums) { if (nums.length <= 1) return true let cover = nums[0] for (let i = 0; i <= cover; i++) { cover = Math.max(cover, i + nums[i]) if (cover >= nums.length - 1) return true } return false } ``` ## 55.1 跳跃游戏Ⅱ > 思路：首先，我们要确定一定能跳到最后一个位置，因此我们需要计算的是跳跃的最后一个位置时，所需要的最少步数step > > - 定义curCover默认为0，即当前所在第一个位置。 > - 定义nextCover ：Math.max(nextCover,i+nums[i]) 即跳跃的下一个区间 > > 遍历nums，计算出当前的nextCover,当i==curCover的时候，即当前已经跳到最大边界处，那么step++，需要跳到下一个边界,如果下一个边界大于nums.length，那么就结束 ```js var jump = function (nums) { let curCover = 0 let nextCover = 0 let step = 0 for (let i = 0; i < nums.length; i++) { nextCover = Math.max(nextCover, i + nums[i]) if (i == curCover) { step++ curCover = nextCover if (curCover >= nums.length - 1) return step } } } ``` ## [56. 合并区间](https://leetcode.cn/problems/merge-intervals/) > 思路：先对数组中每一项数组元素的第一项进行排序。temp=nums[0],判断temp[1]是否大于等于nums[i] [0],如果大于就要合并。 > > `注意：合并需要继续比较 temp[1]=Math.max(temp[1],nums[i][1])` 如果小于，那么就将temp推入，且temp=nums[i] > > **最后，还需要把最后一个temp推入** > > ​ 最后一定会多出一个num，及intervals最后一项。 > > ​ [[1,2],[3,4],[5,6]] 不能和最后一项合并，最后多一个[5,6] > > ​ [[1,2],[3,4],[4,5]] 可以和最后一项合并，但是并没有直接推入 多了[3,5] ```js var merge = function (intervals) { let result = [] intervals.sort((a, b) => a[0] - b[0]) let temp = intervals[0] for (let i = 0; i < intervals.length; i++) { if (temp[1] >= intervals[i][0]) { temp[1] = Math.max(temp[1], intervals[i][1]) } else { result.push(temp) temp = intervals[i] } } result.push(temp) return result } ``` ## [62. 不同路径](https://leetcode.cn/problems/unique-paths/) > 思路： > > - 定义dp数组和下标含义： dp[i] [j]表示从(0,0)到(i,j)所有的不同路径 > - 状态转移方程：dp[i] [j]=dp[i-1] [j]+dp[i] [j-1] > - 初始化dp数组 dp[i] [0]=1 dp[0] [j]=1 (注意：这是路径数，不是路径和) ```js var uniquePaths = function (m, n) { let dp = new Array(m).fill().map(() => new Array(n).fill(0)) for (let i = 0; i < m; i++) { dp[i][0] = 1 } for (let j = 0; j < n; j++) { dp[0][j] = 1 } for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] } } return dp[m - 1][n - 1] } ``` ## [64. 最小路径和](https://leetcode.cn/problems/minimum-path-sum/) > 思路：跟不同路径类似，区别在于求路径和 > > - 状态转移方程：dp[i] [j]=Math.min(dp[i-1] [j],dp[i] [j-1])+grid[i] [j] > - 初始化dp数组 dp[i] [0]=dp[i-1] [0]+grid[i] [0] ```js var minPathSum = function (grid) { let m = grid.length let n = grid[0].length let dp = new Array(m).fill().map(() => new Array(n).fill(0)) dp[0][0] = grid[0][0] for (let i = 1; i < m; i++) { dp[i][0] = dp[i - 1][0] + grid[i][0] } for (let j = 1; j < n; j++) { dp[0][j] = dp[0][j - 1] + grid[0][j] } for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] } } return dp[m - 1][n - 1] } ``` ## [72. 编辑距离](https://leetcode.cn/problems/edit-distance/)(hard) > 思路：字符串wod1：horse变换到字符串hor需要的最少操作次数 > > 字符串子序列问题，一般都是 `动态规划`，比较 `尾序列`是否相同 > > - 定义dp数组和下标含义：dp[i] [j]表示长度为i的字符串word1(0,i-1)变换到长度为j的字符串word2(0,j-1)所需要的最少操作次数 > > - 状态转移方程： > > **区分情况，如果尾序列相同即word1[i-1]==word2[j-1],那么只需要继续判断前面变化的最少操作次数** > > `dp[i][j]=dp[i-1][j-1]` > > **如果尾序列不同，有三种变化方式** > > - 删除： hors --hor 删除s,操作数+1，继续比较(0,i-2)和(0,j-1) > > `dp[i][j]=dp[i-1][j]+1` > > - 替换 hor --> hos 替换最后一个,操作数+1，继续比较(0,i-2)和(0,j-2) > > `dp[i][j]=dp[i-1][j-1]+1` > > - 添加 给word1添加其实等同于word2删除， 继续比较(0,i-1)和(0,j-2) > > `dp[i][j]=dp[i][j-1]+1` > > - **最后取最小的操作数** > > `dp[i][j]=Math.min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1` > > - 初始化dp数组 > > word1为空 dp[0] [j]=j word2为空 dp[i] [0]=i ```js var minDistance = function (word1, word2) { let m = word1.length let n = word2.length let dp = new Array(m + 1).fill().map(() => new Array(n + 1).fill(0)) for (let i = 1; i <= m; i++) { dp[i][0] = i } for (let j = 1; j <= n; j++) { dp[0][j] = j } for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] } else { dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1 } } } return dp[m][n] } ``` ## [75. 颜色分类](https://leetcode.cn/problems/sort-colors/) > 思路：这题其实正常思路就是排序，但是被取消了，只能用双指针。 > > 定义left指向0、right指向nums.length-1。循环nums数组，如果nums[i]==0，那么就与left指针交换，left++，i++ > > 如果遇到1，跳过，`如果遇到2，那么与right指针交换，right--，但是i不能++，因为你无法判断交换回来的是不是2` > > 为什么left不需要呢，因为left交换回来的一定是0或者1，2早就被放后面去了。left左边永远是0 > > `注意：还有个细节就是 while(i<=right) i不能超过right，因为right后面也是排好序的，不能弄乱` ```js var sortColors = function (nums) { let left = 0 let right = nums.length - 1 let i = 0 while (i <= right) { if (nums[i] == 0) { ;[nums[i], nums[left]] = [nums[left], nums[i]] i++ left++ } else if (nums[i] == 1) { i++ } else { ;[nums[i], nums[right]] = [nums[right], nums[i]] right-- } } return nums } ``` ## [78. 子集](https://leetcode.cn/problems/subsets/) > 思路：子集，子序列都是用回溯法 > > - 确定终止条件 当start>=nums.length终止 > > - 确定循环遍历范围 > > 从下一个开始，不能重复，path每推入一次都需要推入res数组中 ```js var subsets = function (nums) { let path = [] let res = [[]] function backTracking(path, start) { if (start >= nums.length) return for (let i = start; i < nums.length; i++) { path.push(nums[i]) res.push([...path]) backTracking(path, i + 1) path.pop() } } backTracking(path, 0) return res } ``` > 写法2：不推荐 > > ```js > var subsets = function (nums) { > let path = [] > let res = [[]] > function backTracking(path, start) { > //如果想要res.push()放在外面，那么start必须>nums.length，因为到了最后一个path.push(2)时，backTack([1,2,],3)i+1为3 > //导致[1,2,3]推入不进去 > > /* > 但是这种写法不好，不如path.push()之后，直接res.push()，本来就是为了存放每次的path路径 > */ > if (start > nums.length) { > return > } > res.push([...path]) > for (let i = start; i < nums.length; i++) { > path.push(nums[i]) > backTracking(path, i + 1) > path.pop() > } > } > backTracking(path, 0) > return res > } > ``` > > ## [76. 最小覆盖子串](https://leetcode.cn/problems/minimum-window-substring/)(hard) > 思路：定义一个map，遍历t中的所有字符，如果是不同类型的，就放入map中，相同类型，值+1。 > > - 遍历字符串s，如果当前字符s[i]存在于map中，就让map对应的值-1，如果值为0了，missingtype--。 > - while(missingtype==0)的情况下，找出最小的字串 ```js var minWindow = function (s, t) { let missingType = 0 let minLength = Infinity let result = '' const map = new Map() for (let i = 0; i < t.length; i++) { /* 不能添加这个map.get(s[right]!=0)的条件 当s=='bba' t='ba'时，第一次遍历b使得b:0,messingtype-- 但是如果添加了这个条件就会导致第二次遍历到b，依然missingtype-- */ if (!map.has(t[i])) { map.set(t[i], 1) missingType++ } else { map.set(t[i], map.get(t[i]) + 1) } } let left = 0 for (l; i < s.length; i++) { if (map.has(s[i])) { map.set(s[i], map.get(s[i]) - 1) } if (map.get(s[i]) == 0) { missingType-- } //缩放区间 while (missingType == 0) { if (minLength > i - left + 1) { minLength = i - left + 1 result = s.slice(left, i + 1) } if (map.has(s[left])) { map.set(s[left], map.get(s[left]) + 1) } if (map.get(s[left]) > 0) missingType++ left++ } } return result } ``` ## [79. 单词搜索](https://leetcode.cn/problems/word-search/) [相关类型--图论题目](#图论) > 思路：单词搜索其实跟岛屿题目一样，首先找出第一个字母，然后通过dfs深入遍历四个方向。 > > `重点：遍历一个字母，需要将当前字母置0，不能重复遍历` > > **dfs模板**： > > - 确定终止条件 > > 遇到边界或者重复或者没匹配上 return false > > 如果当前遍历到了最后一个字母(经过上面的if肯定匹配上了)，就return true > > - 确定集合范围 > > 四个边 ```js /* 单词搜索这种典型的岛屿深搜题目,搜索四周 */ var exist = function (board, word) { let m = board.length let n = board[0].length function dfs(i, j, index) { if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == 0 || board[i][j] != word[index]) { return false } if (index == word.length - 1) { return true } //当前点算遍历结束，置0，继续遍历四周 let temp = board[i][j] board[i][j] = 0 let res = dfs(i - 1, j, index + 1) || dfs(i + 1, j, index + 1) || dfs(i, j - 1, index + 1) || dfs(i, j + 1, index + 1) //当前搜索点位深度遍历四周 board[i][j] = temp return res } for (let i = 0; i < board.length; i++) { for (let j = 0; j < board[0].length; j++) { if (board[i][j] == word[0]) { let res = dfs(i, j, 0) if (res) return true } } } return false } ``` ## 84.柱形图中最大的矩形(hard) > 思路： 定义一个栈，如果每次进来的都更大，那么下一次进来只可能面积更大。如果进来一个比前面小的，那才可能变大或变小，因此我们需要维护一个单调递增栈，为了不考虑头尾， `heights=[0,...heights,0]` > > **0 5 6 4 0 ** `栈里存放的都是下标` > > - 遇到0，5，6都入栈。`遇到4`，这时候就需要考虑面积变大还是变小了。 > - 6先出栈，我们计算以6为高度，宽度为`当前下标i - 剩余栈顶元素的下标-1` (**为了统一头尾节点计算宽度**)，即6*3-1-1 > - 5循环出栈，计算5*3-0-1 > - 4入栈，再遇到了0，4出栈，计算4*(4-0-1) =12 ```js var largestRectangleArea = function (heights) { heights = [0, ...heights, 0] const stack = [] let maxArea = 0 for (let i = 0; i < heights.length; i++) { while (heights[i] < heights[stack[stack.length - 1]]) { let topIndex = stack.pop() maxArea = Math.max(maxArea, heights[topIndex] * (i - stack[stack.length - 1] - 1)) } stack.push(i) } return maxArea } ``` ## [96. 不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees/)(记忆题) > 以k为节点构造二叉树，那么1-k-1用于构建左子树，k+1-n构建右子树 > > 设左子树形态a种，右子树形态b种，那么总共有a*b种 > > - 定义dp数组和下标含义：dp[i]表示以i个节点构成的二叉搜索数之和 > > - 状态转移方程： > > i==2 扣除根节点1个，左子树一个，右子树为i-左子树用的-1 > > - j==0 dp[2]+=dp[0]*dp[2-0-1]=1 > > - j==1 dp[2]+=dp[1]*dp[1]=2 注意：我们需要计算的是i个节点构成的不同二叉搜索树总和，所以`dp[i]+=` > > 即以两个节点构成不同的二叉搜索树为2 > > i==3 扣除根节点，左子树可以0，或者1或者2，即dp[0],dp[1],dp[2]乘以相对应的右子树 > > dp[i]+=dp[j]*dp[j-i-1] > > - 初始化dp数组 > > dp=new Array(n+1).fill(0) > > dp[0]=dp[1]=1 > > - 确定循环条件 i=2; `i<=n` ```js var numTrees = function (n) { let dp = new Array(n + 1).fill(0) dp[0] = dp[1] = 1 for (let i = 2; i <= n; i++) { for (let j = 0; j < i; j++) { dp[i] += dp[j] * dp[i - j - 1] } } return dp[n] } ``` ## 98.验证二叉搜索树 > 二叉搜索树有个特性：中序遍历得到的结果一定是个递增数组。所以只需要判断中序遍历后的数组是否递增即可 ```js var isValidBST = function (root) { let res = [] function inOrder(root) { if (!root) return null inOrder(root.left) res.push(root.val) inOrder(root.right) } inOrder(root) for (let i = 1; i < res.length; i++) { if (res[i] <= res[i - 1]) return false } return true } ``` ## 101.对称二叉树 > 思路：层序遍历获取每一层，然后判断每一层是否对称即可。注意，不能用join()拼接字符串的方式，因为null进行拼接会消失 ```js var isSymmetric = function (root) { function levelOrder(root) { if (!root) return [] let queue = [root] let res = [] while (queue.length) { let len = queue.length res.push([]) for (let i = 0; i < len; i++) { let node = queue.shift() if (node) { res[res.length - 1].push(node.val) queue.push(node.left) queue.push(node.right) } else { res[res.length - 1].push(null) } } } return res } let res = levelOrder(root) return res.every(item => isPali(item)) function isPali(arr) { let left = 0 let right = arr.length - 1 while (left <= right) { if (arr[left++] != arr[right--]) return false } return true } } ``` ## [104. 二叉树的最大深度](https://leetcode.cn/problems/maximum-depth-of-binary-tree/)(记忆题) > 二叉树节点每个节点的最大深度都可以用这个方法获取 ```js var maxDepth = function (root) { if (!root) return 0 return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 } ``` ## [105. 从前序与中序遍历序列构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/) > 思路：前序(1,mid+1) (mid+1) (0,mid)(mid+1) ```js var buildTree = function (preorder, inorder) { if (!inorder.length) return null let root = { val: preorder[0], left: null, right: null } let mid = inorder.indexOf(root.val) root.left = buildTree(preorder.slice(1, mid + 1), inorder.slice(0, mid)) root.right = buildTree(preorder.slice(mid + 1), inorder.slice(mid + 1)) return root } ``` ## 106.从中序与后序遍历构建二叉树 > 思路：中序(0,mid) (mid+1) 后序 (0,mid)(mid,postorder.length-1) ```js var buildTree = function (inorder, postorder) { if (!inorder.length) return null let root = { val: postorder[postorder.length - 1], left: null, right: null } let mid = inorder.indexOf(root.val) root.left = buildTree(inorder.slice(0, mid), postorder.slice(0, mid)) root.right = buildTree(inorder.slice(mid + 1), postorder.slice(mid, postorder.length - 1)) return root } ``` ## 114.二叉树展开为链表 > 思路：前序遍历得到二叉树节点数组，然后根据数组构建链表即可。注意它这个链表是类似于二叉树的，不是通过next链接。left为null，通过right链接 ``` var flatten = function (root) { let result = [] function preOrder(root) { if (!root) return null result.push(root) preOrder(root.left) preOrder(root.right) } preOrder(root) let head = { val: 0, left: null, right: null } let p = head for (let i = 0; i < result.length; i++) { p.right = result[i] p.left = null p = p.right } return head.right } ``` ## [124. 二叉树中的最大路径和](https://leetcode.cn/problems/binary-tree-maximum-path-sum/)(hard) > 思路：路径和是左子树的和+根节点+右子树的和构成的。因此需要`从下向上遍历`，使用后序遍历。 > > 先获取左右子树的最大路径和，然后与根节点相加进行比较。最后返回当前节点的路径和可以加左右子树，也可以只返回根 > > **类似于二叉树的最近公共祖先** ```js var maxPathSum = function (root) { let maxSum = root.val function postOrder(root) { //如果节点不存在 return 0 if (!root) return 0 //返回的是左右子节点的经过计算的最大路径和 let leftSum = postOrder(root.left) let rightSum = postOrder(root.right) //找出当前节点的最大路径和 左+根+右 maxSum = Math.max(maxSum, leftSum + rightSum + root.val) //返回当前节点的左或者右的最大路径和，以父节点使用 let returnMaxSum = Math.max(0, leftSum, rightSum) + root.val return returnMaxSum > 0 ? returnMaxSum : 0 } } ``` ## [128. 最长连续序列](https://leetcode.cn/problems/longest-consecutive-sequence/) > 思路：这个跟子序列没关系，只需要找到连续序列就行了，所以无需使用回溯。 > > 定义一个set对重复元素去重。遍历nums，首先找出当前值的左边界。然后逐个+1，判断是否存在于set中 ```js var longestConsecutive = function (nums) { let set = new Set(nums) let res = 0 for (let i = 0; i < nums.length; i++) { if (set.has(nums[i] - 1)) { continue } else { //找到了左边界 let temp = 1 let count = nums[i] + 1 while (set.has(count)) { temp++ count++ } res = Math.max(temp, res) } } return res } ``` ## 141.环形链表 > 思路：判断一个链表是否有环，使用 `快慢指针`。如果快指针能追上慢指针就有环，不然无环 ```js var hasCycle = function (head) { let fast = head let slow = head while (fast && fast.next) { fast = fast.next.next slow = slow.next if (fast == slow) return true } return false } ``` ​ ## [142. 环形链表 II](https://leetcode.cn/problems/linked-list-cycle-ii/) > 思路：本质上也是先判断链表是否有环，因此还是需要使用快慢指针。但是当fast==slow的时候，需要让fast重回head位置，每次只走一步，这样再次和slow相遇时，即为环形入口节点。 ```js var detectCycle = function (head) { let fast = head let slow = head while (fast && fast.next) { fast = fast.next.next slow = slow.next if (fast == slow) { fast = head while (fast != slow) { fast = fast.next slow = slow.next } return slow } } //如果没环就返回null，不然会报错 return null } ``` ## [148. 排序链表](https://leetcode.cn/problems/sort-list/) > 思路：链表本身就有序，最好的方法就是遍历链表，排序，再重新创建 ```js var sortList = function (head) { let p = head let arr = [] while (p) { arr.push(p.val) p = p.next } arr.sort((a, b) => a - b) let dummy = new ListNode() let p2 = dummy for (let i = 0; i < arr.length; i++) { let node = new ListNode(arr[i]) p2.next = node p2 = p2.next } return dummy.next } ``` ## 206.反转链表 > 思路：反转链表三步走 (无需虚拟头节点) > > ①定义pre=null，cur=head，next=null > > ②while(cur) next=cur.next cur.next=pre pre=cur cur=next > > ③最后 return pre即可 ```js var reverseList = function (head) { let pre = null let cur = head let next = null while (cur) { next = cur.next cur.next = pre pre = cur cur = next } return pre } ```