[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6,"_7":8},"actionData","errors","root",{"_11":-5},"routes/user.$name.collections",{"_9":10,"_11":12,"_13":14,"_15":16,"_17":18,"_19":16},"topics",[34],"user",{"_20":21,"_13":14,"_22":23,"_24":14,"_25":26,"_27":28,"_29":30,"_31":16,"_32":33},"loginname","flynn-eye","page",1,"limit",20,"total","id","40879","avatar_url","https://avatars.githubusercontent.com/u/23251324?v=4","githubUsername","create_at","2021-02-20 01:56:20.939","score",5,"topic_count",0,"reply_count","is_star",false,{"_20":35,"_36":37,"_38":39,"_40":41,"_42":43,"_44":45,"_46":33,"_47":33,"_31":30,"_48":49,"_25":45,"_50":51},"44664","author_id","39211","tab","share","content","## 缘起\r\n\r\n现在大厂面试中，算法题几乎为必考项，且近几年频现 LeetCode 真题，此篇为拿到字节、腾讯、京东 Offer 的笔者本人在准备面试过程中亲自刷过以及遇到过高频算法题。文章内容会分模块整理，对于笔者在面试过程中遇到的真题，会给予着重【🔥】标出。\r\n\r\n同时，可以毫不客气的说，如果你准备时间有限，又想追求算法题准备效率最大化，那么你只需要按照大纲把下面的题目刷完，并把代码烂熟于心，就几乎可以应对 90% 的面试算法考题了。\r\n\r\n整理这篇内容的目的一个是笔者在之前准备面试时的一点积累，而它确实也帮助笔者在面试算法题中过关斩将，同时呢，也希望能够在金三银四给予拼搏的你，一点点帮助就好！💪\r\n\r\n文末有福利：）😈\r\n\r\n本篇内容包括如下模块：\r\n\r\n* 高频算法题系列：链表\r\n* 【🔥】【有真题】高频算法题系列：字符串\r\n* 【🔥】【有真题】高频算法题系列：数组问题\r\n* 高频算法题系列：二叉树\r\n* 【🔥】高频算法题系列：排序算法\r\n* 【🔥】高频算法题系列：二分查找\r\n* 【🔥】高频算法题系列：动态规划\r\n* 高频算法题系列：BFS\r\n* 【🔥】高频算法题系列：栈\r\n* 【🔥】高频算法题系列：DFS\r\n* 【🔥】高频算法题系列：回溯算法\r\n\r\n其中标🔥的部分代表非常高频的考题，其中不乏笔者遇到的原题。其中对于每一类，首先会列出包含的考题，然后针对每一道考题会给出难度、考察知识点、是否是面试真题，在每道题详细介绍时，还会给出每道题的 LeetCode 链接，帮助读者理解题意，以及能够进行实际的测验，还可以观看其他人的答案，更好的帮助准备。\r\n\r\n## 高频算法题系列：链表\r\n\r\n笔者遇到的高频链表题主要包含这几道：\r\n\r\n* 通过链表的后续遍历判断回文链表问题【简单】\r\n* 链表的反向输出【简单】\r\n* 合并 K 个升序链表【困难】\r\n* K个一组翻转链表【困难】\r\n* 环形链表【简单】\r\n* 排序链表【中等】\r\n* 相交链表【简单】\r\n\r\n### 前序遍历判断回文链表\r\n\r\n👉 [【LeetCode 直通车】：234 回文链表（简单）](https://leetcode-cn.com/problems/palindrome-linked-list/)\r\n\r\n#### 题解1\r\n\r\n利用链表的后续遍历，使用函数调用栈作为后序遍历栈，来判断是否回文\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n *\r\n */\r\nvar isPalindrome = function(head) {\r\n let left = head;\r\n function traverse(right) {\r\n if (right == null) return true;\r\n let res = traverse(right.next);\r\n res = res && (right.val === left.val);\r\n left = left.next;\r\n return res;\r\n }\r\n return traverse(head);\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n#### 题解2\r\n\r\n通过快、慢指针找链表中点，然后反转链表，比较两个链表两侧是否相等，来判断是否是回文链表\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n *\r\n */\r\nvar isPalindrome = function(head) {\r\n // 反转 slower 链表\r\n let right = reverse(findCenter(head));\r\n let left = head;\r\n // 开始比较\r\n while (right != null) {\r\n if (left.val !== right.val) {\r\n return false;\r\n }\r\n left = left.next;\r\n right = right.next;\r\n }\r\n return true;\r\n}\r\nfunction findCenter(head) {\r\n let slower = head, faster = head;\r\n while (faster && faster.next != null) {\r\n slower = slower.next;\r\n faster = faster.next.next;\r\n }\r\n // 如果 faster 不等于 null，说明是奇数个，slower 再移动一格\r\n if (faster != null) {\r\n slower = slower.next;\r\n }\r\n return slower;\r\n}\r\nfunction reverse(head) {\r\n let prev = null, cur = head, nxt = head;\r\n while (cur != null) {\r\n nxt = cur.next;\r\n cur.next = prev;\r\n prev = cur;\r\n cur = nxt;\r\n }\r\n return prev;\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 反转链表\r\n\r\n👉 [【LeetCode 直通车】：206 反转链表（简单）](https://leetcode-cn.com/problems/reverse-linked-list/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for singly-linked list.\r\n * function ListNode(val) {\r\n * this.val = val;\r\n * this.next = null;\r\n * }\r\n */\r\n/**\r\n * @param {ListNode} head\r\n * @return {ListNode}\r\n */\r\nvar reverseList = function(head) {\r\n if (head == null || head.next == null) return head;\r\n let last = reverseList(head.next);\r\n head.next.next = head;\r\n head.next = null;\r\n return last;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 合并K个升序链表\r\n\r\n👉 [【LeetCode 直通车】：23 合并K个升序链表（困难）](https://leetcode-cn.com/problems/merge-k-sorted-lists/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for singly-linked list.\r\n * function ListNode(val) {\r\n * this.val = val;\r\n * this.next = null;\r\n * }\r\n */\r\n/**\r\n * @param {ListNode[]} lists\r\n * @return {ListNode}\r\n */\r\nvar mergeKLists = function(lists) {\r\n if (lists.length === 0) return null;\r\n return mergeArr(lists);\r\n};\r\nfunction mergeArr(lists) {\r\n if (lists.length <= 1) return lists[0];\r\n let index = Math.floor(lists.length / 2);\r\n const left = mergeArr(lists.slice(0, index))\r\n const right = mergeArr(lists.slice(index));\r\n return merge(left, right);\r\n}\r\nfunction merge(l1, l2) {\r\n if (l1 == null && l2 == null) return null;\r\n if (l1 != null && l2 == null) return l1;\r\n if (l1 == null && l2 != null) return l2;\r\n let newHead = null, head = null;\r\n while (l1 != null && l2 != null) {\r\n if (l1.val < l2.val) {\r\n if (!head) {\r\n newHead = l1;\r\n head = l1;\r\n } else {\r\n newHead.next = l1;\r\n newHead = newHead.next;\r\n }\r\n l1 = l1.next;\r\n } else {\r\n if (!head) {\r\n newHead = l2;\r\n head = l2;\r\n } else {\r\n newHead.next = l2;\r\n newHead = newHead.next;\r\n }\r\n l2 = l2.next;\r\n }\r\n }\r\n newHead.next = l1 ? l1 : l2;\r\n return head;\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### K 个一组翻转链表\r\n\r\n👉 [【LeetCode 直通车】：25 K 个一组翻转链表（困难）](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for singly-linked list.\r\n * function ListNode(val) {\r\n * this.val = val;\r\n * this.next = null;\r\n * }\r\n */\r\n/**\r\n * @param {ListNode} head\r\n * @param {number} k\r\n * @return {ListNode}\r\n */\r\nvar reverseKGroup = function(head, k) {\r\n let a = head, b = head;\r\n for (let i = 0; i < k; i++) {\r\n if (b == null) return head;\r\n b = b.next;\r\n }\r\n const newHead = reverse(a, b);\r\n a.next = reverseKGroup(b, k);\r\n return newHead;\r\n};\r\nfunction reverse(a, b) {\r\n let prev = null, cur = a, nxt = a;\r\n while (cur != b) {\r\n nxt = cur.next;\r\n cur.next = prev;\r\n prev = cur;\r\n cur = nxt;\r\n }\r\n return prev;\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 环形链表\r\n\r\n👉 [【LeetCode 直通车】：141 环形链表（简单）](https://leetcode-cn.com/problems/linked-list-cycle/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for singly-linked list.\r\n * function ListNode(val) {\r\n * this.val = val;\r\n * this.next = null;\r\n * }\r\n */\r\n/**\r\n * @param {ListNode} head\r\n * @return {boolean}\r\n */\r\nvar hasCycle = function(head) {\r\n if (head == null || head.next == null) return false;\r\n let slower = head, faster = head;\r\n while (faster != null && faster.next != null) {\r\n slower = slower.next;\r\n faster = faster.next.next;\r\n if (slower === faster) return true;\r\n }\r\n return false;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 排序链表\r\n\r\n👉 [【LeetCode 直通车】：148 排序链表（中等）](https://leetcode-cn.com/problems/sort-list/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for singly-linked list.\r\n * function ListNode(val) {\r\n * this.val = val;\r\n * this.next = null;\r\n * }\r\n */\r\n/**\r\n * @param {ListNode} head\r\n * @return {ListNode}\r\n */\r\nvar sortList = function(head) {\r\n if (head == null) return null;\r\n let newHead = head;\r\n return mergeSort(head);\r\n};\r\nfunction mergeSort(head) {\r\n if (head.next != null) {\r\n let slower = getCenter(head);\r\n let nxt = slower.next;\r\n slower.next = null;\r\n console.log(head, slower, nxt);\r\n const left = mergeSort(head);\r\n const right = mergeSort(nxt);\r\n head = merge(left, right);\r\n }\r\n return head;\r\n}\r\nfunction merge(left, right) {\r\n let newHead = null, head = null;\r\n while (left != null && right != null) {\r\n if (left.val < right.val) {\r\n if (!head) {\r\n newHead = left;\r\n head = left;\r\n } else {\r\n newHead.next = left;\r\n newHead = newHead.next;\r\n }\r\n left = left.next;\r\n } else {\r\n if (!head) {\r\n newHead = right;\r\n head = right;\r\n } else {\r\n newHead.next = right;\r\n newHead = newHead.next;\r\n }\r\n right = right.next;\r\n }\r\n }\r\n newHead.next = left ? left : right;\r\n return head;\r\n}\r\nfunction getCenter(head) {\r\n let slower = head, faster = head.next;\r\n while (faster != null && faster.next != null) {\r\n slower = slower.next;\r\n faster = faster.next.next;\r\n }\r\n return slower;\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 相交链表\r\n\r\n👉 [【LeetCode 直通车】：160 相交链表（简单）](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for singly-linked list.\r\n * function ListNode(val) {\r\n * this.val = val;\r\n * this.next = null;\r\n * }\r\n */\r\n/**\r\n * @param {ListNode} headA\r\n * @param {ListNode} headB\r\n * @return {ListNode}\r\n */\r\nvar getIntersectionNode = function(headA, headB) {\r\n let lastHeadA = null;\r\n let lastHeadB = null;\r\n let originHeadA = headA;\r\n let originHeadB = headB;\r\n if (!headA || !headB) {\r\n return null;\r\n }\r\n while (true) {\r\n if (headB == headA) {\r\n return headB;\r\n }\r\n if (headA && headA.next == null) {\r\n lastHeadA = headA;\r\n headA = originHeadB;\r\n } else {\r\n headA = headA.next;\r\n }\r\n if (headB && headB.next == null) {\r\n lastHeadB = headB\r\n headB = originHeadA;\r\n } else {\r\n headB = headB.next;\r\n }\r\n if (lastHeadA && lastHeadB && lastHeadA != lastHeadB) {\r\n return null;\r\n }\r\n }\r\n return null;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n## 【🔥】高频算法题系列：字符串\r\n\r\n主要有以下几类高频考题：\r\n\r\n* 最长回文子串【中等】【双指针】【面试真题】\r\n* 最长公共前缀【简单】【双指针】\r\n* 无重复字符的最长子串【中等】【双指针】\r\n* 最小覆盖子串【困难】【滑动窗口】【面试真题】\r\n\r\n### 【面试真题】最长回文子串【双指针】\r\n\r\n👉 [【LeetCode 直通车】：5 最长回文子串（中等）](https://leetcode-cn.com/problems/longest-palindromic-substring/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {string} s\r\n * @return {string}\r\n */\r\nvar longestPalindrome = function(s) {\r\n if (s.length === 1) return s;\r\n let maxRes = 0, maxStr = '';\r\n for (let i = 0; i < s.length; i++) {\r\n let str1 = palindrome(s, i, i);\r\n let str2 = palindrome(s, i, i + 1); \r\n if (str1.length > maxRes) {\r\n maxStr = str1;\r\n maxRes = str1.length;\r\n }\r\n if (str2.length > maxRes) {\r\n maxStr = str2;\r\n maxRes = str2.length;\r\n }\r\n }\r\n return maxStr;\r\n};\r\nfunction palindrome(s, l, r) {\r\n while (l >= 0 && r < s.length && s[l] === s[r]) {\r\n l--;\r\n r++;\r\n }\r\n return s.slice(l + 1, r);\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 最长公共前缀【双指针】\r\n\r\n👉 [【LeetCode 直通车】：14 最长公共前缀（简单）](https://leetcode-cn.com/problems/longest-common-prefix/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {string[]} strs\r\n * @return {string}\r\n */\r\nvar longestCommonPrefix = function(strs) {\r\n if (strs.length === 0) return \"\";\r\n let first = strs[0];\r\n if (first === \"\") return \"\";\r\n let minLen = Number.MAX_SAFE_INTEGER;\r\n for (let i = 1; i < strs.length; i++) {\r\n const len = twoStrLongestCommonPrefix(first, strs[i]);\r\n minLen = Math.min(len, minLen);\r\n }\r\n return first.slice(0, minLen);\r\n};\r\nfunction twoStrLongestCommonPrefix (s, t) {\r\n let i = 0, j = 0;\r\n let cnt = 0;\r\n while (i < s.length && j < t.length) {\r\n console.log(s[i], t[j], cnt)\r\n if (s[i] === t[j]) {\r\n cnt++;\r\n } else {\r\n return cnt;\r\n }\r\n i++;\r\n j++;\r\n }\r\n return cnt;\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 无重复字符的最长子串【双指针】\r\n\r\n👉 [【LeetCode 直通车】：3 无重复字符的最长子串（中等）](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {string} s\r\n * @return {number}\r\n */\r\nvar lengthOfLongestSubstring = function(s) {\r\n let window = {};\r\n let left = 0, right = 0;\r\n let maxLen = 0, maxStr = '';\r\n while (right < s.length) {\r\n let c = s[right];\r\n right++;\r\n if (window[c]) window[c]++;\r\n else window[c] = 1\r\n while (window[c] > 1) {\r\n let d = s[left];\r\n left++;\r\n window[d]--;\r\n }\r\n if (maxLen < right - left) {\r\n maxLen = right - left;\r\n }\r\n }\r\n return maxLen;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 【面试真题】最小覆盖子串【滑动窗口】\r\n\r\n👉 [【LeetCode 直通车】：76 最小覆盖子串（困难）](https://leetcode-cn.com/problems/minimum-window-substring/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {string} s\r\n * @param {string} t\r\n * @return {string}\r\n */\r\nvar minWindow = function(s, t) {\r\n let need = {}, window = {};\r\n for (let c of t) {\r\n if (!need[c]) need[c] = 1;\r\n else need[c]++;\r\n }\r\n let left = 0, right = 0;\r\n let valid = 0, len = Object.keys(need).length;\r\n let minLen = s.length + 1, minStr = '';\r\n while (right < s.length) {\r\n const d = s[right];\r\n right++;\r\n if (!window[d]) window[d] = 1;\r\n else window[d]++;\r\n if (need[d] && need[d] === window[d]) {\r\n valid++;\r\n }\r\n console.log('left - right', left, right);\r\n while (valid === len) {\r\n if (right - left < minLen) {\r\n minLen = right - left;\r\n minStr = s.slice(left, right);\r\n }\r\n console.lo\r\n let c = s[left];\r\n left++;\r\n window[c]--;\r\n if (need[c] && window[c] < need[c]) {\r\n valid--;\r\n }\r\n }\r\n }\r\n return minStr;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n## 【🔥】高频算法题系列：数组问题\r\n\r\n主要有几类高频考题：\r\n\r\n* 俄罗斯套娃信封问题【困难】【排序+最长上升子序列】【面试真题】\r\n* 最长连续递增序列【简单】【双指针】\r\n* 最长连续序列【困难】【哈希表】\r\n* 盛最多水的容器【困难】【面试真题】\r\n* 寻找两个正序数组的中位数【困难】【双指针】\r\n* 删除有序数组中的重复项【简单】【快慢指针】\r\n* 和为K的子数组【中等】【哈希表】\r\n* nSum 问题【系列】【简单】【哈希表】\r\n* 接雨水【困难】【暴力+备忘录优化】【面试真题】\r\n* 跳跃游戏【系列】【中等】【贪心算法】\r\n\r\n### 【面试真题】俄罗斯套娃信封问题【排序+最长上升子序列】\r\n\r\n👉 [【LeetCode 直通车】：354 俄罗斯套娃信封问题（困难）](https://leetcode-cn.com/problems/russian-doll-envelopes/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[][]} envelopes\r\n * @return {number}\r\n */\r\nvar maxEnvelopes = function(envelopes) {\r\n if (envelopes.length === 1) return 1;\r\n envelopes.sort((a, b) => {\r\n if (a[0] !== b[0]) return a[0] - b[0];\r\n else return b[1] - a[1];\r\n });\r\n let LISArr = [];\r\n for (let [key, value] of envelopes) {\r\n LISArr.push(value);\r\n }\r\n console.log( LISArr);\r\n return LIS(LISArr);\r\n};\r\nfunction LIS(arr) {\r\n let dp = [];\r\n let maxAns = 0;\r\n for (let i = 0; i < arr.length; i++) {\r\n dp[i] = 1;\r\n }\r\n for (let i = 1; i < arr.length; i++) {\r\n for (let j = i; j >= 0; j--) {\r\n if (arr[i] > arr[j]) {\r\n dp[i] = Math.max(dp[i], dp[j] + 1)\r\n }\r\n maxAns = Math.max(maxAns, dp[i]);\r\n }\r\n }\r\n return maxAns;\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 最长连续递增序列【快慢指针】\r\n\r\n👉 [【LeetCode 直通车】：674 最长连续递增序列（简单）](https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums\r\n * @return {number}\r\n */\r\nvar findLengthOfLCIS = function(nums) {\r\n if (nums.length === 0) return 0;\r\n const n = nums.length;\r\n let left = 0, right = 1;\r\n let globalMaxLen = 1, maxLen = 1;\r\n while (right < n) {\r\n if (nums[right] > nums[left]) maxLen++;\r\n else {\r\n maxLen = 1;\r\n }\r\n left++;\r\n right++;\r\n globalMaxLen = Math.max(globalMaxLen, maxLen);\r\n }\r\n return globalMaxLen;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 最长连续序列【哈希表】\r\n\r\n👉 [【LeetCode 直通车】：128 最长连续序列（困难）](https://leetcode-cn.com/problems/longest-consecutive-sequence/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums\r\n * @return {number}\r\n */\r\nvar longestConsecutive = function(nums) {\r\n if (nums.length === 0) return 0;\r\n const set = new Set(nums);\r\n const n = nums.length;\r\n let globalLongest = 1;\r\n for (let i = 0; i < n; i++) {\r\n if (!set.has(nums[i] - 1)) {\r\n let longest = 1;\r\n let currentNum = nums[i];\r\n while (set.has(currentNum + 1)) {\r\n currentNum += 1;\r\n longest++;\r\n }\r\n globalLongest = Math.max(globalLongest, longest);\r\n }\r\n }\r\n return globalLongest;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 【面试真题】盛最多水的容器【哈希表】\r\n\r\n👉 [【LeetCode 直通车】：11 盛最多水的容器（中等）](https://leetcode-cn.com/problems/container-with-most-water/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} height\r\n * @return {number}\r\n */\r\nvar maxArea = function(height) {\r\n let n = height.length;\r\n let left = 0, right = n - 1;\r\n let maxOpacity = 0;\r\n while (left < right) {\r\n let res = Math.min(height[left], height[right]) * (right - left);\r\n maxOpacity = Math.max(maxOpacity, res);\r\n if (height[left] < height[right]) left++\r\n else right--;\r\n }\r\n return maxOpacity;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 寻找两个正序数组的中位数【双指针】\r\n\r\n👉 [【LeetCode 直通车】：4 寻找两个正序数组的中位数（困难）](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums1\r\n * @param {number[]} nums2\r\n * @return {number}\r\n */\r\nvar findMedianSortedArrays = function(nums1, nums2) {\r\n let m = nums1.length, n = nums2.length;\r\n let i = 0, j = 0;\r\n let newArr = [];\r\n while (i < m && j < n) {\r\n if (nums1[i] < nums2[j]) {\r\n newArr.push(nums1[i++]);\r\n } else {\r\n newArr.push(nums2[j++]);\r\n }\r\n }\r\n newArr = newArr.concat(i < m ? nums1.slice(i) : nums2.slice(j));\r\n const len = newArr.length;\r\n console.log(newArr)\r\n if (len % 2 === 0) {\r\n return (newArr[len / 2] + newArr[len / 2 - 1]) / 2;\r\n } else {\r\n return newArr[Math.floor(len / 2)];\r\n }\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 删除有序数组中的重复项【快慢指针】\r\n\r\n👉 [【LeetCode 直通车】：26 删除有序数组中的重复项（简单）](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums\r\n * @return {number}\r\n */\r\nvar removeDuplicates = function(nums) {\r\n if (nums.length <= 1) return nums.length;\r\n let lo = 0, hi = 0;\r\n while (hi < nums.length) {\r\n while (nums[lo] === nums[hi] && hi < nums.length) hi++;\r\n if (nums[lo] !== nums[hi] && hi < nums.length) {\r\n lo++;\r\n nums[lo] = nums[hi];\r\n }\r\n hi++;\r\n }\r\n return lo + 1;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 和为K的子数组【哈希表】\r\n\r\n👉 [【LeetCode 直通车】：560 和为K的子数组（中等）](https://leetcode-cn.com/problems/subarray-sum-equals-k/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums\r\n * @param {number} k\r\n * @return {number}\r\n */\r\nvar subarraySum = function(nums, k) {\r\n let cnt = 0;\r\n let sum0_i = 0, sum0_j = 0;\r\n let map = new Map();\r\n map.set(0, 1);\r\n for (let i = 0; i <= nums.length; i++) {\r\n sum0_i += nums[i];\r\n sum0_j = sum0_i - k;\r\n console.log('map', sum0_j, map.get(sum0_j))\r\n if (map.has(sum0_j)) {\r\n cnt += map.get(sum0_j);\r\n }\r\n let sumCnt = map.get(sum0_i) || 0;\r\n map.set(sum0_i, sumCnt + 1);\r\n }\r\n return cnt;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### nSum问题【哈希表】【系列】\r\n\r\n* 👉 [【LeetCode 直通车】：1 两数之和（简单）](https://leetcode-cn.com/problems/two-sum/)\r\n* 👉 [【LeetCode 直通车】：167 两数之和 II - 输入有序数组（简单）](https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/)\r\n* 👉 [【LeetCode 直通车】：15 三数之和（中等）](https://leetcode-cn.com/problems/3sum/)\r\n* 👉 [【LeetCode 直通车】：18 四数之和（中等）](https://leetcode-cn.com/problems/4sum/)\r\n\r\n受限于篇幅，这里只给出第一道题的代码模板，也是一面常考真题。\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums\r\n * @param {number} target\r\n * @return {number[]}\r\n */\r\nvar twoSum = function(nums, target) {\r\n let map2 = new Map();\r\n for (let i = 0; i < nums.length; i++) {\r\n map2.set(nums[i], i);\r\n }\r\n for (let i = 0; i < nums.length; i++) {\r\n if (map2.has(target - nums[i]) && map2.get(target - nums[i]) !== i) return [i, map2.get(target - nums[i])]\r\n }\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 【面试真题】接雨水【暴力+备忘录优化】\r\n\r\n👉 [【LeetCode 直通车】：42 接雨水（困难）](https://leetcode-cn.com/problems/trapping-rain-water/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} height\r\n * @return {number}\r\n */\r\nvar trap = function(height) {\r\n let l_max = [], r_max = [];\r\n let len = height.length;\r\n let maxCapacity = 0;\r\n for (let i = 0; i < len; i++) {\r\n l_max[i] = height[i];\r\n r_max[i] = height[i];\r\n }\r\n for (let i = 1; i < len; i++) {\r\n l_max[i] = Math.max(l_max[i - 1], height[i]);\r\n }\r\n for (let j = len - 2; j >= 0; j--) {\r\n r_max[j] = Math.max(r_max[j + 1], height[j]);\r\n }\r\n for (let i = 0; i < len; i++) {\r\n maxCapacity += Math.min(l_max[i], r_max[i]) - height[i];\r\n }\r\n return maxCapacity;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 跳跃游戏【贪心算法】【系列】\r\n\r\n* 👉 [【LeetCode 直通车】：55 跳跃游戏（中等）](https://leetcode-cn.com/problems/jump-game/)\r\n* 👉 [【LeetCode 直通车】：45 跳跃游戏 II（中等）](https://leetcode-cn.com/problems/jump-game-ii/)\r\n\r\n受限于篇幅，这里只给出第一道题的代码模板，也是一面常考真题。\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums\r\n * @return {boolean}\r\n */\r\nvar canJump = function(nums) {\r\n let faster = 0;\r\n for (let i = 0; i < nums.length - 1; i++) {\r\n faster = Math.max(faster, i + nums[i]);\r\n if (faster <= i) return false;\r\n }\r\n return faster >= nums.length - 1;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n## 高频算法题系列：二叉树\r\n\r\n主要有以下几类高频考题：\r\n\r\n* 二叉树的最近公共祖先【简单】【二叉树】\r\n* 二叉搜索树中的搜索【简单】【二叉树】\r\n* 删除二叉搜索树中的节点【中等】【二叉树】\r\n* 完全二叉树的节点个数【中等】【二叉树】\r\n* 二叉树的锯齿形层序遍历【中等】【二叉树】\r\n\r\n### 二叉树的最近公共祖先【二叉树】\r\n\r\n👉 [【LeetCode 直通车】：236 二叉树的最近公共祖先（简单）](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for a binary tree node.\r\n * function TreeNode(val) {\r\n * this.val = val;\r\n * this.left = this.right = null;\r\n * }\r\n */\r\n/**\r\n * @param {TreeNode} root\r\n * @param {TreeNode} p\r\n * @param {TreeNode} q\r\n * @return {TreeNode}\r\n */\r\nlet visited;let parent;\r\nvar lowestCommonAncestor = function(root, p, q) {\r\n visited = new Set();\r\n parent = new Map();\r\n dfs(root);\r\n while (p != null) {\r\n visited.add(p.val);\r\n p = parent.get(p.val);\r\n }\r\n while (q != null) {\r\n if (visited.has(q.val)) {\r\n return q;\r\n }\r\n q = parent.get(q.val);\r\n }\r\n return null;\r\n};\r\nfunction dfs(root) {\r\n if (root.left != null) {\r\n parent.set(root.left.val, root);\r\n dfs(root.left);\r\n }\r\n if (root.right != null) {\r\n parent.set(root.right.val, root);\r\n dfs(root.right);\r\n }\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 二叉搜索树中的搜索【二叉树】\r\n\r\n👉 [【LeetCode 直通车】：700 二叉搜索树中的搜索（简单）](https://leetcode-cn.com/problems/search-in-a-binary-search-tree/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for a binary tree node.\r\n * function TreeNode(val) {\r\n * this.val = val;\r\n * this.left = this.right = null;\r\n * }\r\n */\r\n/**\r\n * @param {TreeNode} root\r\n * @param {number} val\r\n * @return {TreeNode}\r\n */\r\nvar searchBST = function(root, val) {\r\n if (root == null) return null;\r\n if (root.val === val) return root;\r\n if (root.val > val) {\r\n return searchBST(root.left, val);\r\n } else if (root.val < val) {\r\n return searchBST(root.right, val);\r\n }\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 删除二叉搜索树中的节点【二叉树】\r\n\r\n👉 [【LeetCode 直通车】：450 删除二叉搜索树中的节点（中等）](https://leetcode-cn.com/problems/delete-node-in-a-bst/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for a binary tree node.\r\n * function TreeNode(val) {\r\n * this.val = val;\r\n * this.left = this.right = null;\r\n * }\r\n */\r\n/**\r\n * @param {TreeNode} root\r\n * @param {number} key\r\n * @return {TreeNode}\r\n */\r\nvar deleteNode = function(root, key) {\r\n if (root == null) return null;\r\n if (root.val === key) {\r\n if (root.left == null && root.right == null) return null;\r\n if (root.left == null) return root.right;\r\n if (root.right == null) return root.left;\r\n if (root.left != null && root.right != null) {\r\n let target = getMinTreeMaxNode(root.left);\r\n root.val = target.val;\r\n root.left = deleteNode(root.left, target.val);\r\n }\r\n }\r\n if (root.val < key) {\r\n root.right = deleteNode(root.right, key);\r\n } else if (root.val > key) {\r\n root.left = deleteNode(root.left, key);\r\n }\r\n return root;\r\n};\r\nfunction getMinTreeMaxNode(root) {\r\n if (root.right == null) return root;\r\n return getMinTreeMaxNode(root.right);\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 完全二叉树的节点个数【二叉树】\r\n\r\n👉 [【LeetCode 直通车】：222 完全二叉树的节点个数（中等）](https://leetcode-cn.com/problems/count-complete-tree-nodes/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for a binary tree node.\r\n * function TreeNode(val) {\r\n * this.val = val;\r\n * this.left = this.right = null;\r\n * }\r\n */\r\n/**\r\n * @param {TreeNode} root\r\n * @return {number}\r\n */\r\nvar countNodes = function(root) {\r\n if (root == null) return 0;\r\n let l = root, r = root;\r\n let lh = 0, rh = 0;\r\n while (l != null) {\r\n l = l.left;\r\n lh++;\r\n }\r\n while (r != null) {\r\n r = r.right;\r\n rh++;\r\n }\r\n if (lh === rh) {\r\n return Math.pow(2, lh) - 1;\r\n }\r\n return 1 + countNodes(root.left) + countNodes(root.right);\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 二叉树的锯齿形层序遍历【二叉树】\r\n\r\n👉 [【LeetCode 直通车】：103 二叉树的锯齿形层序遍历（中等）](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for a binary tree node.\r\n * function TreeNode(val) {\r\n * this.val = val;\r\n * this.left = this.right = null;\r\n * }\r\n */\r\n/**\r\n * @param {TreeNode} root\r\n * @return {number[][]}\r\n */\r\nlet res;\r\nvar zigzagLevelOrder = function(root) {\r\n if (root == null) return [];\r\n res = [];\r\n BFS(root, true);\r\n return res;\r\n};\r\nfunction BFS(root, inOrder) {\r\n let arr = [];\r\n let resItem = [];\r\n let node;\r\n let stack1 = new Stack();\r\n let stack2 = new Stack();\r\n // 判断交换时机\r\n let flag;\r\n stack1.push(root);\r\n res.push([root.val]);\r\n inOrder = !inOrder;\r\n while (!stack1.isEmpty() || !stack2.isEmpty()) {\r\n if (stack1.isEmpty()) {\r\n flag = 'stack1';\r\n } else if (stack2.isEmpty()) {\r\n flag = 'stack2';\r\n }\r\n // 决定取那个栈里面的元素\r\n if (flag === 'stack2' && !stack1.isEmpty()) node = stack1.pop();\r\n else if (flag === 'stack1' && !stack2.isEmpty()) node = stack2.pop();\r\n if (inOrder) {\r\n if (node.left) {\r\n if (flag === 'stack1') {\r\n stack1.push(node.left);\r\n } else {\r\n stack2.push(node.left);\r\n }\r\n resItem.push(node.left.val);\r\n }\r\n if (node.right) {\r\n if (flag === 'stack1') {\r\n stack1.push(node.right);\r\n } else {\r\n stack2.push(node.right);\r\n }\r\n resItem.push(node.right.val);\r\n }\r\n } else {\r\n if (node.right) {\r\n if (flag === 'stack1') {\r\n stack1.push(node.right);\r\n } else {\r\n stack2.push(node.right);\r\n }\r\n resItem.push(node.right.val);\r\n }\r\n if (node.left) {\r\n if (flag === 'stack1') {\r\n stack1.push(node.left);\r\n } else {\r\n stack2.push(node.left);\r\n }\r\n resItem.push(node.left.val);\r\n }\r\n }\r\n // 判断下次翻转的时机\r\n if ((flag === 'stack2' && stack1.isEmpty()) || (flag === 'stack1' && stack2.isEmpty())) {\r\n inOrder = !inOrder;\r\n // 需要翻转了，就加一轮值\r\n if (resItem.length > 0) {\r\n res.push(resItem);\r\n } \r\n resItem = [];\r\n }\r\n }\r\n}\r\nclass Stack {\r\n constructor() {\r\n this.count = 0;\r\n this.items = [];\r\n }\r\n push(element) {\r\n this.items[this.count] = element;\r\n this.count++;\r\n }\r\n pop() {\r\n if (this.isEmpty()) return undefined;\r\n const element = this.items[this.count - 1];\r\n delete this.items[this.count - 1];\r\n this.count--;\r\n return element;\r\n }\r\n size() {\r\n return this.count;\r\n }\r\n isEmpty() {\r\n return this.size() === 0;\r\n }\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n## 【🔥】高频算法题系列：排序算法\r\n\r\n主要有以下几类高频考题：\r\n\r\n* 用最少数量的箭引爆气球【中等】【排序】\r\n* 合并区间【中等】【排序算法+区间问题】【面试真题】\r\n\r\n### 用最少数量的箭引爆气球【排序算法】\r\n\r\n👉 [【LeetCode 直通车】：452 用最少数量的箭引爆气球（中等）](https://leetcode-cn.com/problems/minimum-number-of-arrows-to-burst-balloons/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[][]} points\r\n * @return {number}\r\n */\r\nvar findMinArrowShots = function(points) {\r\n if (points.length === 0) return 0;\r\n points.sort((a, b) => a[1] - b[1]);\r\n let cnt = 1;\r\n let resArr = [points[0]];\r\n let curr, last;\r\n for (let i = 1; i < points.length; i++) {\r\n curr = points[i];\r\n last = resArr[resArr.length - 1];\r\n if (curr[0] > last[1]) {\r\n resArr.push(curr);\r\n cnt++;\r\n }\r\n }\r\n return cnt;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 合并区间【排序算法+区间问题】\r\n\r\n👉 [【LeetCode 直通车】：56 合并区间（中等）](https://leetcode-cn.com/problems/merge-intervals/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[][]} intervals\r\n * @return {number[][]}\r\n */\r\nvar merge = function(intervals) {\r\n if (intervals.length === 0) return [];\r\n intervals.sort((a, b) => a[0] - b[0]);\r\n let mergeArr = [intervals[0]];\r\n let last, curr;\r\n for (let j = 1; j < intervals.length; j++) {\r\n last = mergeArr[mergeArr.length - 1];\r\n curr = intervals[j];\r\n if (last[1] >= curr[0]) {\r\n last[1] = Math.max(curr[1], last[1]);\r\n } else {\r\n mergeArr.push(curr);\r\n }\r\n }\r\n return mergeArr;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n## 高频算法题系列：二分查找\r\n\r\n主要有以下几类高频考题：\r\n\r\n* 寻找两个正序数组的中位数【困难】【二分查找】\r\n* 判断子序列【简单】【二分查找】\r\n* 在排序数组中查找元素的第一个和最后一个位置【中等】【二分查找】\r\n\r\n### 寻找两个正序数组的中位数【二分查找】\r\n\r\n👉 [【LeetCode 直通车】：4 寻找两个正序数组的中位数（困难）](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums1\r\n * @param {number[]} nums2\r\n * @return {number}\r\n */\r\nvar findMedianSortedArrays = function(nums1, nums2) {\r\n let m = nums1.length, n = nums2.length;\r\n let i = 0, j = 0;\r\n let newArr = [];\r\n while (i < m && j < n) {\r\n if (nums1[i] < nums2[j]) {\r\n newArr.push(nums1[i++]);\r\n } else {\r\n newArr.push(nums2[j++]);\r\n }\r\n }\r\n newArr = newArr.concat(i < m ? nums1.slice(i) : nums2.slice(j));\r\n const len = newArr.length;\r\n console.log(newArr)\r\n if (len % 2 === 0) {\r\n return (newArr[len / 2] + newArr[len / 2 - 1]) / 2;\r\n } else {\r\n return newArr[Math.floor(len / 2)];\r\n }\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 判断子序列【二分查找】\r\n\r\n👉 [【LeetCode 直通车】：392 判断子序列（简单）](https://leetcode-cn.com/problems/is-subsequence/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {string} s\r\n * @param {string} t\r\n * @return {boolean}\r\n */\r\nvar isSubsequence = function(s, t) {\r\n let hash = {};\r\n for (let i = 0; i < t.length; i++) {\r\n if (!hash[t[i]]) hash[t[i]] = [];\r\n hash[t[i]].push(i);\r\n }\r\n let lastMaxIndex = 0;\r\n for (let i = 0; i < s.length; i++) {\r\n if (hash[s[i]]) {\r\n const index = binarySearch(hash[s[i]], lastMaxIndex);\r\n console.log('index', index, hash[s[i]]);\r\n if (index === -1) return false;\r\n lastMaxIndex = hash[s[i]][index] + 1;\r\n } else return false;\r\n }\r\n return true;\r\n};\r\nfunction binarySearch(array, targetIndex) {\r\n let left = 0, right = array.length;\r\n while (left < right) {\r\n let mid = left + Math.floor((right - left) / 2);\r\n if (array[mid] >= targetIndex) {\r\n right = mid;\r\n } else if (array[mid] < targetIndex) {\r\n left = mid + 1;\r\n }\r\n }\r\n if (left >= array.length || array[left] < targetIndex) return -1;\r\n return left;\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 💁 在排序数组中查找元素的第一个和最后一个位置【二分搜索】\r\n\r\n👉 [【LeetCode 直通车】：34 在排序数组中查找元素的第一个和最后一个位置（中等）](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums\r\n * @param {number} target\r\n * @return {number[]}\r\n */\r\nvar searchRange = function(nums, target) {\r\n const left = leftBound(nums, target);\r\n const right = rightBound(nums, target);\r\n return [left, right];\r\n};\r\nfunction leftBound(nums, target) {\r\n let left = 0;\r\n let right = nums.length - 1;\r\n while (left <= right) {\r\n let mid = Math.floor(left + (right - left) / 2);\r\n if (nums[mid] === target) {\r\n right = mid - 1;\r\n } else if (nums[mid] < target) {\r\n left = mid + 1;\r\n } else if (nums[mid] > target) {\r\n right = mid - 1;\r\n }\r\n }\r\n if (left >= nums.length || nums[left] !== target) {\r\n return -1;\r\n }\r\n return left;\r\n}\r\nfunction rightBound(nums, target) {\r\n let left = 0;\r\n let right = nums.length - 1;\r\n while (left <= right) {\r\n let mid = Math.floor(left + (right - left) / 2);\r\n if (nums[mid] === target) {\r\n left = mid + 1;\r\n } else if (nums[mid] < target) {\r\n left = mid + 1;\r\n } else if (nums[mid] > target) {\r\n right = mid - 1;\r\n }\r\n }\r\n if (right < 0 || nums[right] !== target) {\r\n return -1;\r\n }\r\n return right;\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n## 【🔥】高频算法题系列：动态规划\r\n\r\n主要有以下几类高频考题：\r\n\r\n* 最长递增子序列【中等】【动态规划】\r\n* 零钱兑换【中等】【动态规划】【面试真题】\r\n* 最长公共子序列【中等】【动态规划】【面试真题】\r\n* 编辑距离【困难】【动态规划】\r\n* 最长回文子序列【中等】【动态规划】【面试真题】\r\n* 最大子序和【简单】【动态规划】【面试真题】\r\n* 买卖股票的最佳时机系列【系列】【动态规划】【面试真题】\r\n\r\n### 最长递增子序列【动态规划】\r\n\r\n👉 [【LeetCode 直通车】：300 最长递增子序列（中等）](https://leetcode-cn.com/problems/longest-increasing-subsequence/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums\r\n * @return {number}\r\n */\r\nvar lengthOfLIS = function(nums) {\r\n let maxLen = 0, n = nums.length;\r\n let dp = [];\r\n for (let i = 0; i < n; i++) {\r\n dp[i] = 1;\r\n }\r\n for (let i = 0; i < n; i++) {\r\n for (let j = 0; j < i; j++) {\r\n if (nums[i] > nums[j]) {\r\n dp[i] = Math.max(dp[i], dp[j] + 1);\r\n }\r\n }\r\n maxLen = Math.max(maxLen, dp[i]);\r\n }\r\n return maxLen;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 【面试真题】零钱兑换【动态规划】\r\n\r\n👉 [【LeetCode 直通车】：322 零钱兑换（中等）](https://leetcode-cn.com/problems/coin-change/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} coins\r\n * @param {number} amount\r\n * @return {number}\r\n */\r\nvar coinChange = function(coins, amount) {\r\n if (amount === 0) return 0;\r\n let dp = [];\r\n for (let i = 0; i <= amount; i++) {\r\n dp[i] = amount + 1;\r\n }\r\n dp[0] = 0;\r\n for (let i = 0; i <= amount; i++) {\r\n for (let j = 0; j < coins.length; j++) {\r\n if (i >= coins[j]) {\r\n dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i])\r\n }\r\n }\r\n }\r\n return dp[amount] === amount + 1 ? -1 : dp[amount];\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 【面试真题】最长公共子序列【动态规划】\r\n\r\n👉 [【LeetCode 直通车】：1143 最长公共子序列（中等）](https://leetcode-cn.com/problems/longest-common-subsequence/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {string} text1\r\n * @param {string} text2\r\n * @return {number}\r\n */\r\nvar longestCommonSubsequence = function(text1, text2) {\r\n let n1 = text1.length, n2 = text2.length;\r\n let dp = [];\r\n for (let i = -1; i < n1; i++) {\r\n dp[i] = [];\r\n for (let j = -1; j < n2;j++) {\r\n dp[i][j] = 0;\r\n }\r\n }\r\n for (let i = 0; i < n1; i++) {\r\n for (let j = 0; j < n2; j++) {\r\n if (text1[i] === text2[j]) {\r\n dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);\r\n } else {\r\n dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])\r\n }\r\n }\r\n }\r\n return dp[n1 - 1][n2 - 1];\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 编辑距离【动态规划】\r\n\r\n👉 [【LeetCode 直通车】：72 编辑距离（困难）](https://leetcode-cn.com/problems/edit-distance/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {string} word1\r\n * @param {string} word2\r\n * @return {number}\r\n */\r\nvar minDistance = function(word1, word2) {\r\n let len1 = word1.length, len2 = word2.length;\r\n let dp = [];\r\n for (let i = 0; i <= len1; i++) {\r\n dp[i] = [];\r\n for (let j = 0; j <= len2; j++) {\r\n dp[i][j] = 0;\r\n if (i === 0) {\r\n dp[i][j] = j;\r\n }\r\n if (j === 0) {\r\n dp[i][j] = i;\r\n }\r\n }\r\n }\r\n for (let i = 1; i <= len1; i++) {\r\n for (let j = 1; j <= len2; j++) {\r\n if (word1[i - 1] === word2[j - 1]) {\r\n dp[i][j] = dp[i - 1][j - 1];\r\n } else {\r\n dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);\r\n }\r\n }\r\n }\r\n return dp[len1][len2];\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 【面试真题】最长回文子序列【动态规划】\r\n\r\n👉 [【LeetCode 直通车】：516 最长回文子序列（中等）](https://leetcode-cn.com/problems/longest-palindromic-subsequence/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {string} s\r\n * @return {number}\r\n */\r\nvar longestPalindromeSubseq = function(s) {\r\n let dp = [];\r\n for (let i = 0; i < s.length; i++) {\r\n dp[i] = [];\r\n for (let j = 0; j < s.length; j++) {\r\n dp[i][j] = 0;\r\n }\r\n dp[i][i] = 1;\r\n }\r\n for (let i = s.length - 1; i >= 0; i--) {\r\n for (let j = i + 1; j < s.length; j++) {\r\n if (s[i] === s[j]) {\r\n dp[i][j] = dp[i + 1][j - 1] + 2;\r\n } else {\r\n dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);\r\n }\r\n }\r\n }\r\n return dp[0][s.length - 1];\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 【面试真题】💁 最大子序和【动态规划】\r\n\r\n👉 [【LeetCode 直通车】：53 最大子序和（简单）](https://leetcode-cn.com/problems/maximum-subarray/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums\r\n * @return {number}\r\n */\r\nvar maxSubArray = function(nums) {\r\n let maxSum = -Infinity;\r\n let dp = [], n = nums.length;\r\n for (let i = -1; i < n; i++) {\r\n dp[i] = 0;\r\n }\r\n for (let i = 0; i < n; i++) {\r\n dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);\r\n maxSum = Math.max(maxSum, dp[i]);\r\n }\r\n return maxSum;\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n### 【面试真题】💁 买卖股票的最佳时机【动态规划】\r\n\r\n* 👉 [【LeetCode 直通车】：121 买卖股票的最佳时机（简单）](https://leetcode-cn.com/problems/container-with-most-water/)【面试真题】\r\n* 👉 [【LeetCode 直通车】：122 买卖股票的最佳时机 II（简单）](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/)\r\n* 👉 [【LeetCode 直通车】：123 买卖股票的最佳时机 III（困难）](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/)\r\n* 👉 [【LeetCode 直通车】：188 买卖股票的最佳时机IV（困难）](https://leetcode-cn.com/problems/container-with-most-water/)\r\n* 👉 [【LeetCode 直通车】：309 买卖股票的最佳时机含冷冻期（中等）](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/)\r\n* 👉 [【LeetCode 直通车】：714 买卖股票的最佳时机含手续费（中等）](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)\r\n\r\n受限于篇幅，这里只给出第一道题的代码模板，也是一面常考真题，笔者在面试字节跳动时就遇到过。\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} prices\r\n * @return {number}\r\n */\r\nvar maxProfit = function(prices) {\r\n let dp = [];\r\n for (let i = -1; i < prices.length; i++) {\r\n dp[i] = []\r\n for (let j = 0; j <= 1; j++) {\r\n dp[i][j] = [];\r\n dp[i][j][0] = 0;\r\n dp[i][j][1] = 0;\r\n if (i === -1) {\r\n dp[i][j][1] = -Infinity;\r\n }\r\n if (j === 0) {\r\n dp[i][j][1] = -Infinity;\r\n }\r\n if (j === -1) {\r\n dp[i][j][1] = -Infinity;\r\n }\r\n }\r\n }\r\n for (let i = 0; i < prices.length; i++) {\r\n for (let j = 1; j <= 1; j++) {\r\n dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);\r\n dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);\r\n }\r\n }\r\n return dp[prices.length - 1][1][0];\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n## 高频算法题系列：BFS\r\n\r\n主要有以下几类高频考题：\r\n\r\n* 打开转盘锁【中等】【BFS】\r\n* 二叉树的最小深度【简单】【BFS】\r\n\r\n### 打开转盘锁【BFS】\r\n\r\n👉 [【LeetCode 直通车】：752 打开转盘锁（中等）](https://leetcode-cn.com/problems/open-the-lock/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {string[]} deadends\r\n * @param {string} target\r\n * @return {number}\r\n */\r\nvar openLock = function(deadends, target) {\r\n let queue = new Queue();\r\n let visited = new Set();\r\n let step = 0;\r\n queue.push('0000');\r\n visited.add('0000');\r\n while (!queue.isEmpty()) {\r\n let size = queue.size();\r\n for (let i = 0; i < size; i++) {\r\n let str = queue.pop();\r\n if (deadends.includes(str)) continue;\r\n if (target === str) {\r\n return step;\r\n }\r\n for (let j = 0; j < 4; j++) {\r\n let plusStr = plusOne(str, j);\r\n let minusStr = minusOne(str, j);\r\n if (!visited.has(plusStr)) {\r\n queue.push(plusStr);\r\n visited.add(plusStr)\r\n }\r\n if (!visited.has(minusStr)) {\r\n queue.push(minusStr);\r\n visited.add(minusStr)\r\n }\r\n }\r\n }\r\n step++;\r\n }\r\n return -1;\r\n};\r\nfunction plusOne(str, index) {\r\n let strArr = str.split('');\r\n if (strArr[index] === '9') {\r\n strArr[index] = '0'\r\n } else {\r\n strArr[index] = (Number(strArr[index]) + 1).toString()\r\n }\r\n return strArr.join('');\r\n}\r\nfunction minusOne(str, index) {\r\n let strArr = str.split('');\r\n if (strArr[index] === '0') {\r\n strArr[index] = '9'\r\n } else {\r\n strArr[index] = (Number(strArr[index]) - 1).toString()\r\n }\r\n return strArr.join('');\r\n}\r\nclass Queue {\r\n constructor() {\r\n this.items = [];\r\n this.count = 0;\r\n this.lowerCount = 0;\r\n }\r\n push(elem) {\r\n this.items[this.count++] = elem;\r\n }\r\n pop() {\r\n if (this.isEmpty()) {\r\n return;\r\n }\r\n const elem = this.items[this.lowerCount];\r\n delete this.items[this.lowerCount];\r\n this.lowerCount++;\r\n return elem;\r\n }\r\n isEmpty() {\r\n if (this.size() === 0) return true;\r\n return false;\r\n }\r\n size() {\r\n return this.count - this.lowerCount;\r\n }\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 二叉树的最小深度【BFS】\r\n\r\n👉 [【LeetCode 直通车】：111 二叉树的最小深度（简单）](https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for a binary tree node.\r\n * function TreeNode(val) {\r\n * this.val = val;\r\n * this.left = this.right = null;\r\n * }\r\n */\r\n/**\r\n * @param {TreeNode} root\r\n * @return {number}\r\n */\r\nvar minDepth = function(root) {\r\n if (root == null) return 0;\r\n let depth = 1;\r\n let queue = new Queue();\r\n queue.push(root);\r\n while (!queue.isEmpty()) {\r\n let size = queue.size();\r\n for (let i = 0; i < size; i++) {\r\n const node = queue.pop();\r\n if (node.left == null && node.right == null) return depth;\r\n if (node.left) {\r\n queue.push(node.left);\r\n }\r\n if (node.right) {\r\n queue.push(node.right);\r\n }\r\n }\r\n depth++;\r\n }\r\n return depth;\r\n};\r\nclass Queue {\r\n constructor() {\r\n this.items = [];\r\n this.count = 0;\r\n this.lowerCount = 0;\r\n }\r\n push(elem) {\r\n this.items[this.count++] = elem;\r\n }\r\n pop() {\r\n if (this.isEmpty()) {\r\n return;\r\n }\r\n const elem = this.items[this.lowerCount];\r\n delete this.items[this.lowerCount];\r\n this.lowerCount++;\r\n return elem;\r\n }\r\n isEmpty() {\r\n if (this.size() === 0) return true;\r\n return false;\r\n }\r\n size() {\r\n return this.count - this.lowerCount;\r\n }\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n## 【🔥】高频算法题系列：栈\r\n\r\n主要有以下几类高频考题：\r\n\r\n* 最小栈【简单】【栈】\r\n* 有效的括号【中等】【栈】【面试真题】\r\n* 简化路径【中等】【栈】\r\n* 下一个更大元素【系列】【栈】\r\n\r\n### 最小栈【栈】\r\n\r\n👉 [【LeetCode 直通车】：155 最小栈（简单）](https://leetcode-cn.com/problems/min-stack/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * initialize your data structure here.\r\n */\r\nvar MinStack = function() {\r\n this.stack = [];\r\n this.minArr = [];\r\n this.count = 0;\r\n this.min = Number.MAX_SAFE_INTEGER;\r\n};\r\n/** \r\n * @param {number} x\r\n * @return {void}\r\n */\r\nMinStack.prototype.push = function(x) {\r\n this.min = Math.min(this.min, x);\r\n this.minArr[this.count] = this.min;\r\n this.stack[this.count] = x;\r\n this.count++;\r\n};\r\n/**\r\n * @return {void}\r\n */\r\nMinStack.prototype.pop = function() {\r\n const element = this.stack[this.count - 1];\r\n if (this.count - 2 >= 0) this.min = this.minArr[this.count - 2];\r\n else this.min = Number.MAX_SAFE_INTEGER;\r\n delete this.stack[this.count - 1];\r\n delete this.minArr[this.count - 1];\r\n this.count--;\r\n return element;\r\n};\r\n/**\r\n * @return {number}\r\n */\r\nMinStack.prototype.top = function() {\r\n if (this.count >= 1) {\r\n return this.stack[this.count - 1];\r\n }\r\n return null;\r\n};\r\n/**\r\n * @return {number}\r\n */\r\nMinStack.prototype.getMin = function() {\r\n const element = this.minArr[this.count - 1];\r\n return element;\r\n};\r\n/**\r\n * Your MinStack object will be instantiated and called as such:\r\n * var obj = new MinStack()\r\n * obj.push(x)\r\n * obj.pop()\r\n * var param_3 = obj.top()\r\n * var param_4 = obj.getMin()\r\n */\r\n\r\n复制代码\r\n```\r\n\r\n### 【系列】下一个更大元素【栈】\r\n\r\n* 👉 [【LeetCode 直通车】：496 下一个更大元素 I（简单）](https://leetcode-cn.com/problems/next-greater-element-i/)\r\n* 👉 [【LeetCode 直通车】：503 下一个更大元素 II（中等）](https://leetcode-cn.com/problems/next-greater-element-ii/)\r\n\r\n受限于篇幅，这里只给出第一道题的代码模板\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums\r\n * @return {number[]}\r\n */\r\nvar nextGreaterElements = function(nums) {\r\n let ans = [];\r\n let stack = new Stack();\r\n const n = nums.length;\r\n for (let i = 2 * n - 1; i >= 0; i--) {\r\n while (!stack.isEmpty() && stack.top() <= nums[i % n]) {\r\n stack.pop();\r\n }\r\n ans[i % n] = stack.isEmpty() ? -1 : stack.top();\r\n stack.push(nums[i % n]);\r\n }\r\n return ans;\r\n};\r\nclass Stack {\r\n constructor() {\r\n this.count = 0;\r\n this.items = [];\r\n }\r\n top() {\r\n if (this.isEmpty()) return undefined;\r\n return this.items[this.count - 1];\r\n }\r\n push(element) {\r\n this.items[this.count] = element;\r\n this.count++;\r\n }\r\n pop() {\r\n if (this.isEmpty()) return undefined;\r\n const element = this.items[this.count - 1];\r\n delete this.items[this.count - 1];\r\n this.count--;\r\n return element;\r\n }\r\n isEmpty() {\r\n return this.size() === 0;\r\n }\r\n size() {\r\n return this.count;\r\n }\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 【面试真题】有效的括号【栈】\r\n\r\n👉 [【LeetCode 直通车】：20 有效的括号（中等）](https://leetcode-cn.com/problems/valid-parentheses/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {string} s\r\n * @return {boolean}\r\n */\r\nvar isValid = function(s) {\r\n if (s.length === 0) {\r\n return true;\r\n }\r\n if (s.length % 2 !== 0) {\r\n return false;\r\n }\r\n let map = {\r\n ')': '(',\r\n ']': '[',\r\n '}': '{',\r\n };\r\n let left = ['(', '[', '{'];\r\n let right = [')', ']', '}'];\r\n let stack = new Stack();\r\n for (let i = 0; i < s.length; i++) {\r\n if (!right.includes(s[i])) {\r\n stack.push(s[i]);\r\n } else {\r\n const matchStr = map[s[i]];\r\n while (!stack.isEmpty()) {\r\n const element = stack.pop();\r\n if (left.includes(element) && matchStr !== element) return false;\r\n if (element === matchStr) break;\r\n }\r\n }\r\n }\r\n return stack.isEmpty();\r\n};\r\nclass Stack {\r\n constructor() {\r\n this.count = 0;\r\n this.items = [];\r\n }\r\n push(element) {\r\n this.items[this.count] = element;\r\n this.count++;\r\n }\r\n pop() {\r\n if (this.isEmpty()) return undefined;\r\n const element = this.items[this.count - 1];\r\n delete this.items[this.count - 1];\r\n this.count--;\r\n return element;\r\n }\r\n isEmpty() {\r\n return this.size() === 0;\r\n }\r\n size() {\r\n return this.count;\r\n }\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 简化路径【栈】\r\n\r\n👉 [【LeetCode 直通车】：71 简化路径（中等）](https://leetcode-cn.com/problems/simplify-path/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {string} path\r\n * @return {string}\r\n */\r\nvar simplifyPath = function(path) {\r\n let newPath = path.split('/');\r\n newPath = newPath.filter(item => item !== \"\");\r\n const stack = new Stack();\r\n for (let s of newPath) {\r\n if (s === '..') stack.pop();\r\n else if (s !== '.') stack.push(s);\r\n }\r\n if (stack.isEmpty()) return '/';\r\n let str = '';\r\n while (!stack.isEmpty()) {\r\n const element = stack.pop();\r\n str = '/' + element + str;\r\n }\r\n return str;\r\n};\r\nfunction handleBack(stack, tag, num) {\r\n if (!stack.isEmpty()) return num;\r\n const element = stack.pop();\r\n if (element === '..') return handleBack(stack, tag, num + 1);\r\n else {\r\n stack.push(element);\r\n return num;\r\n }\r\n}\r\nclass Stack {\r\n constructor() {\r\n this.count = 0;\r\n this.items = [];\r\n }\r\n push(element) {\r\n this.items[this.count] = element;\r\n this.count++;\r\n }\r\n pop() {\r\n if (this.isEmpty()) return undefined;\r\n const element = this.items[this.count - 1];\r\n delete this.items[this.count - 1];\r\n this.count--;\r\n return element;\r\n }\r\n size() {\r\n return this.count;\r\n }\r\n isEmpty() {\r\n return this.size() === 0;\r\n }\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n## 【🔥】高频算法题系列：DFS\r\n\r\n主要有以下几类高频考题：\r\n\r\n* 岛屿的最大面积【中等】【DFS】\r\n* 相同的树【简单】【DFS】\r\n\r\n### 岛屿的最大面积【DFS】\r\n\r\n👉 [【LeetCode 直通车】：695 岛屿的最大面积（中等）](https://leetcode-cn.com/problems/max-area-of-island/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[][]} grid\r\n * @return {number}\r\n */\r\nlet maxX, maxY;let visited;let globalMaxArea;\r\nvar maxAreaOfIsland = function(grid) {\r\n visited = new Set();\r\n maxX = grid.length;\r\n maxY = grid[0].length;\r\n globalMaxArea = 0;\r\n for (let i = 0; i < maxX; i++) {\r\n for (let j = 0; j < maxY; j++) {\r\n if (grid[i][j] === 1) {\r\n visited.add(`(${i}, ${j})`);\r\n globalMaxArea = Math.max(globalMaxArea, dfs(grid, i, j));\r\n }\r\n visited.clear();\r\n }\r\n }\r\n return globalMaxArea;\r\n};\r\nfunction dfs(grid, x, y) {\r\n let res = 1;\r\n for (let i = -1; i <= 1; i++) {\r\n for (let j = -1; j <= 1; j++) {\r\n if (Math.abs(i) === Math.abs(j)) continue;\r\n const newX = x + i;\r\n const newY = y + j;\r\n if (newX >= maxX || newX < 0 || newY >= maxY || newY < 0) continue;\r\n if (visited.has(`(${newX}, ${newY})`)) continue;\r\n visited.add(`(${newX}, ${newY})`);\r\n const areaCnt = grid[newX][newY]\r\n if (areaCnt === 1) {\r\n const cnt = dfs(grid, newX, newY);\r\n res += cnt;\r\n } \r\n }\r\n }\r\n return res;\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 相同的树【DFS】\r\n\r\n👉 [【LeetCode 直通车】：100 相同的树（简单）](https://leetcode-cn.com/problems/same-tree/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * Definition for a binary tree node.\r\n * function TreeNode(val) {\r\n * this.val = val;\r\n * this.left = this.right = null;\r\n * }\r\n */\r\n/**\r\n * @param {TreeNode} p\r\n * @param {TreeNode} q\r\n * @return {boolean}\r\n */\r\nvar isSameTree = function(p, q) {\r\n if (p == null && q == null) return true;\r\n if (p == null || q == null) return false;\r\n if (p.val !== q.val) return false;\r\n return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);\r\n};\r\n\r\n复制代码\r\n```\r\n\r\n## 【🔥】高频算法题系列：回溯算法\r\n\r\n主要有以下几类高频考题：\r\n\r\n* N皇后【困难】【回溯算法】【面试真题】\r\n* 全排列【中等】【回溯算法】\r\n* 括号生成【中等】【回溯算法】\r\n* 复原 IP 地址【中等】【回溯算法】\r\n* 子集【简单】【回溯算法】\r\n\r\n### 【面试真题】N皇后【回溯算法】\r\n\r\n👉 [【LeetCode 直通车】：51 N皇后（困难）](https://leetcode-cn.com/problems/n-queens/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number} n\r\n * @return {string[][]}\r\n */\r\nlet result = [];\r\nvar solveNQueens = function(n) {\r\n result = [];\r\n let board = [];\r\n for (let i = 0; i < n; i++) {\r\n board[i] = [];\r\n for (let j = 0; j < n; j++) {\r\n board[i][j] = '.'\r\n }\r\n }\r\n backtrack(0, board, n);\r\n return result;\r\n};\r\nfunction deepClone(board) {\r\n let res = [];\r\n for (let i = 0; i < board.length; i++) {\r\n res.push(board[i].join(''));\r\n }\r\n return res;\r\n}\r\nfunction backtrack(row, board, n) {\r\n if (row === n) {\r\n result.push(deepClone(board));\r\n return;\r\n }\r\n for (let j = 0; j < n; j++) {\r\n if (checkInValid(board, row, j, n)) continue;\r\n board[row][j] = 'Q';\r\n backtrack(row + 1, board, n);\r\n board[row][j] = '.';\r\n }\r\n}\r\nfunction checkInValid(board, row, column, n) {\r\n // 行\r\n for (let i = 0; i < n; i++) {\r\n if (board[i][column] === 'Q') return true;\r\n }\r\n for (let i = row - 1, j = column + 1; i >= 0 && j < n; i--, j++) {\r\n if (board[i][j] === 'Q') return true;\r\n }\r\n for (let i = row - 1, j = column - 1; i >= 0 && j >= 0; i--, j--) {\r\n if (board[i][j] === 'Q') return true;\r\n }\r\n return false;\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 全排列【回溯算法】\r\n\r\n👉 [【LeetCode 直通车】：46 全排列（中等）](https://leetcode-cn.com/problems/permutations/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums\r\n * @return {number[][]}\r\n */\r\nlet results = [];var permute = function(nums) {\r\n results = [];\r\n backtrack(nums, []);\r\n return results;\r\n};\r\nfunction backtrack(nums, track) {\r\n if (nums.length === track.length) {\r\n results.push(track.slice());\r\n return;\r\n }\r\n for (let i = 0; i < nums.length; i++) {\r\n if (track.includes(nums[i])) continue;\r\n track.push(nums[i]);\r\n backtrack(nums, track);\r\n track.pop();\r\n }\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 括号生成【回溯算法】\r\n\r\n👉 [【LeetCode 直通车】：22 括号生成（中等）](https://leetcode-cn.com/problems/generate-parentheses/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number} n\r\n * @return {string[]}\r\n */\r\nvar generateParenthesis = function(n) {\r\n let validRes = [];\r\n backtrack(n * 2, validRes, '');\r\n return validRes;\r\n};\r\nfunction backtrack(len, validRes, bracket) {\r\n if (bracket.length === len) {\r\n if (isValidCombination(bracket)) {\r\n validRes.push(bracket);\r\n }\r\n return;\r\n }\r\n for (let str of ['(', ')']) {\r\n bracket += str;\r\n backtrack(len, validRes, bracket);\r\n bracket = bracket.slice(0, bracket.length - 1);\r\n }\r\n}\r\nfunction isValidCombination(bracket) {\r\n let stack = new Stack();\r\n for (let i = 0; i < bracket.length; i++) {\r\n const str = bracket[i];\r\n if (str === '(') {\r\n stack.push(str);\r\n } else if (str === ')') {\r\n const top = stack.pop();\r\n if (top !== '(') return false;\r\n }\r\n }\r\n return stack.isEmpty();\r\n}\r\nclass Stack {\r\n constructor() {\r\n this.count = 0;\r\n this.items = [];\r\n }\r\n push(element) {\r\n this.items[this.count] = element;\r\n this.count++;\r\n }\r\n pop() {\r\n if (this.isEmpty()) return;\r\n const element = this.items[this.count - 1];\r\n delete this.items[this.count - 1];\r\n this.count--;\r\n return element;\r\n }\r\n size() {\r\n return this.count;\r\n }\r\n isEmpty() {\r\n return this.size() === 0;\r\n }\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 复原 IP 地址【回溯算法】\r\n\r\n👉 [【LeetCode 直通车】：93 复原 IP 地址（中等）](https://leetcode-cn.com/problems/restore-ip-addresses/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {string} s\r\n * @return {string[]}\r\n */\r\nvar restoreIpAddresses = function(s) {\r\n if (s.length > 12) return [];\r\n let res = [];\r\n const track = [];\r\n backtrack(s, track, res);\r\n return res;\r\n};\r\nfunction backtrack(s, track, res) {\r\n if (track.length === 4 && s.length === 0) {\r\n res.push(track.join('.'));\r\n return;\r\n }\r\n let len = s.length >= 3 ? 3 : s.length;\r\n for (let i = 0; i < len; i++) {\r\n const c = s.slice(0, i + 1);\r\n if (parseInt(c) > 255) continue;\r\n if (i >= 1 && parseInt(c) < parseInt((1 + '0'.repeat(i)))) continue;\r\n track.push(c);\r\n backtrack(s.slice(i + 1), track, res);\r\n track.pop();\r\n }\r\n}\r\n\r\n复制代码\r\n```\r\n\r\n### 子集【回溯算法】\r\n\r\n👉 [【LeetCode 直通车】：78 子集（中等）](https://leetcode-cn.com/problems/subsets/)\r\n\r\n#### 题解\r\n\r\n→点击展开查看\r\n\r\n```\r\n\r\n/**\r\n * @param {number[]} nums\r\n * @return {number[][]}\r\n */\r\nvar subsets = function(nums) {\r\n if (nums.length === 0) return [[]];\r\n let resArr = [];\r\n backtrack(nums, 0, [], resArr);\r\n return resArr;\r\n};\r\nfunction backtrack(nums, index, subArr, resArr) {\r\n if (Array.isArray(subArr)) {\r\n resArr.push(subArr.slice());\r\n }\r\n if (index === nums.length) {\r\n return;\r\n } \r\n for (let i = index; i < nums.length; i++) {\r\n subArr.push(nums[i]);\r\n backtrack(nums, i + 1, subArr, resArr);\r\n subArr.pop(nums[i]);\r\n }\r\n}\r\n\r\n复制代码\r\n```\r\n原文地址 [干货文章分享](https://ideras.com) - [字节跳动最常考的 64 道JS算法题](https://ideras.com/zi-jie-tiao-dong-zui-ai-kao-de-64-dao-suan-fa-ti-jsban/)\r\n\r\n### 原创不易\r\n\r\n喜欢的话原创不易，给点鼓励吧 ❤️ 别忘了分享、点赞、在看三连哦~。","title","字节跳动最常考的 64 道JS算法题","last_reply_at","2021-04-09 14:23:56.399","good","top","visit_count",3724,"author",{"_13":52,"_22":53},"fengmao","https://avatars.githubusercontent.com/u/30584594?v=4"]