前言
最近国内大厂面试中，呈现 LeetCode 真题考查的频率越来越高了。我也察看到有越来越多的前端同学开始关注算法这个话题。
然而算法是一个门槛很高的货色，在一个算法老手的眼里，它的智商门槛要求很高。事实上是这个样子的吗？如果你狐疑本人的 智商不够 去学习算法，那么你肯定要先看完这篇文章：《天生不聪慧》，也正是这篇文章激励了我开始了算法之路。
这篇文章，我会先总结几个 必学的题目分类 ，给出 这个分类下必做例题 的具体题解，并且在文章的开端给出 每个分类下必刷的题目 的获取形式。
肯定要急躁看到底，会有重磅干货。
心路
我从 5 月份筹备到职的时候开始学习算法，在此之前对于算法我是 零根底 ，在最开始我对于算法的感触也和大家一样，感觉本人智商可能不够，望而生畏。然而看了一些大佬对于算法和智商之间的关系，我发现算法如同也是一个通过练习能够缓缓成长的学科，而不是只有智商达到了某个点能力有入场券，所以我开始了我的算法之路。通过 视频课程 + 分类刷题 + 总结题解 + 回头温习 的形式，我在两个月的工夫里把力扣的解题数量刷到了 200 题。对于一个算法新人来说，这应该算是一个还能够的问题，这篇文章，我把我总结的一些学习心得，和一些经典例题分享给大家。
学习形式
- 分类刷题 ：很多第一次接触力扣的同学对于刷题的办法不太理解，有的人跟着题号刷，有的人跟着每日一题刷，然而这种漫无目的的刷题形式个别都会在中途某一天放弃，或者刷了很久然而却发现没什么积淀。这里不啰嗦，间接点明一个所有大佬都举荐的刷题办法：把本人的学习阶段扩散成几个时间段去刷不同分类的题型，比方第一周专门解 链表 相干题型，第二周专门解 二叉树 相干题型。这样你的常识会造成一个体系，通过一段时间的刻意练习把这个题型相干的知识点强化到你的脑海中，不容易忘记。
- 适当放弃 ：很多同学遇到一个难题，非得埋头钻研，干他 2 个小时。最初挫败感十足，长此以往可能就放弃了算法之路。要晓得算法是个积淀了几十年的畛域，题解里的某个算法可能是某些传授钻研很多年的心血，你想靠本人一个老手去想进去等同优良的解法，岂不是想太多了。所以要学会适当放弃，一般来说，比拟有目的性（面试）刷题的同学，他面对一道新的题目毫无脉络的话，会在 10 分钟之内间接放弃去看题解，而后记录下来， 重复温习，直到这个解法成为本人的常识为止。这是效率最高的学习方法。
-
承受本人是老手 ：没错，说的好听一点，承受本人不是蠢才这个事实。你在刷题的过程中会遇到很多困扰你的时候，比方雷同的题型曾经看过例题， 略微变了条件就解不进去 。或者对于一个
easy难度的题毫无脉络。或者甚至 看不懂他人的题解（没错我常常）置信我，这很失常，不能阐明你不适宜学习算法，只能阐明算法的确是一个博大精深的畛域，把本人在其余畛域的积淀抛开来，承受本人是老手这个事实，多看题解，多求教他人。
分类纲要
- 算法的复杂度剖析。
- 排序算法，以及他们的区别和优化。
- 数组中的双指针、滑动窗口思维。
- 利用 Map 和 Set 解决查找表问题。
- 链表的各种问题。
- 利用递归和迭代法解决二叉树问题。
- 栈、队列、DFS、BFS。
- 回溯法、贪婪算法、动静布局。
题解
接下来我会放出几个分类的经典题型，以及我对应的解说，当做开胃菜，并且在文章的开端我会给出获取每个分类 举荐你去刷 的题目的合集，记得看到底哦。
查找表问题
两个数组的交加 II-350
给定两个数组，编写一个函数来计算它们的交加。
示例 1:
输出: nums1 = [1,2,2,1], nums2 = [2,2]
输入: [2,2]
示例 2:
输出: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输入: [4,9]
复制代码起源：力扣（LeetCode）
链接：leetcode-cn.com/problems/in…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
为两个数组别离建设 map，用来存储 num -> count 的键值对，统计每个数字呈现的数量。
而后对其中一个 map 进行遍历，查看这个数字在两个数组中别离呈现的数量，取呈现的最小的那个数量（比方数组 1 中呈现了 1 次，数组 2 中呈现了 2 次，那么交加应该取 1 次），push 到后果数组中即可。
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
let intersect = function (nums1, nums2) {let map1 = makeCountMap(nums1)
let map2 = makeCountMap(nums2)
let res = []
for (let num of map1.keys()) {const count1 = map1.get(num)
const count2 = map2.get(num)
if (count2) {const pushCount = Math.min(count1, count2)
for (let i = 0; i < pushCount; i++) {res.push(num)
}
}
}
return res
}
function makeCountMap(nums) {let map = new Map()
for (let i = 0; i < nums.length; i++) {let num = nums[i]
let count = map.get(num)
if (count) {map.set(num, count + 1)
} else {map.set(num, 1)
}
}
return map
}
复制代码双指针问题
最靠近的三数之和 -16
给定一个包含 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最靠近。返回这三个数的和。假设每组输出只存在惟一答案。
示例：输出：nums = [-1,2,1,-4], target = 1
输入：2
解释：与 target 最靠近的和是 2 (-1 + 2 + 1 = 2)。复制代码提醒：
3 <= nums.length <= 10^3 -10^3 <= nums[i] <= 10^3 -10^4 <= target <= 10^4
起源：力扣（LeetCode）
链接：leetcode-cn.com/problems/3s…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
先依照升序排序，而后别离从左往右顺次抉择一个根底点 i（0 <= i <= nums.length - 3），在根底点的右侧用双指针去一直的找最小的差值。
假如根底点是 i，初始化的时候，双指针别离是：
-
left：i + 1，根底点左边一位。 -
right:nums.length - 1数组最初一位。
而后求此时的和，如果和大于 target，那么能够把右指针左移一位，去试试更小一点的值，反之则把左指针右移。
在这个过程中，不断更新全局的最小差值 min，和此时记录下来的和 res。
最初返回 res 即可。
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
let threeSumClosest = function (nums, target) {
let n = nums.length
if (n === 3) {return getSum(nums)
}
// 先升序排序 此为解题的前置条件
nums.sort((a, b) => a - b)
let min = Infinity // 和 target 的最小差
let res
// 从左往右顺次尝试定一个根底指针 左边至多再保留两位 否则无奈凑成 3 个
for (let i = 0; i <= nums.length - 3; i++) {let basic = nums[i]
let left = i + 1 // 左指针先从 i 右侧的第一位开始尝试
let right = n - 1 // 右指针先从数组最初一项开始尝试
while (left < right) {let sum = basic + nums[left] + nums[right] // 三数求和
// 更新最小差
let diff = Math.abs(sum - target)
if (diff < min) {
min = diff
res = sum
}
if (sum < target) {
// 求出的和如果小于目标值的话 能够尝试把左指针右移 扩充值
left++
} else if (sum > target) {
// 反之则右指针左移
right--
} else {
// 相等的话 差就为 0 肯定是答案
return sum
}
}
}
return res
}
function getSum(nums) {return nums.reduce((total, cur) => total + cur, 0)
}
复制代码滑动窗口问题
无反复字符的最长子串 -3
给定一个字符串，请你找出其中不含有反复字符的 最长子串 的长度。
示例 1:
输出: "abcabcbb"
输入: 3
解释: 因为无反复字符的最长子串是 "abc"，所以其长度为 3。复制代码示例 2:
输出: "bbbbb"
输入: 1
解释: 因为无反复字符的最长子串是 "b"，所以其长度为 1。复制代码示例 3:
输出: "pwwkew"
输入: 3
解释: 因为无反复字符的最长子串是 "wke"，所以其长度为 3。请留神，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。复制代码起源：力扣（LeetCode）链接：leetcode-cn.com/problems/lo… 著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
这题是比拟典型的滑动窗口问题，定义一个左边界 left 和一个右边界 right，造成一个窗口，并且在这个窗口中保障不呈现反复的字符串。
这须要用到一个新的变量 freqMap，用来记录窗口中的字母呈现的频率数。在此基础上，先尝试取窗口的右边界再左边一个地位的值，也就是 str[right + 1]，而后拿这个值去 freqMap 中查找：
- 这个值没有呈现过，那就间接把
right ++，扩充窗口右边界。 - 如果这个值呈现过，那么把
left ++，缩进左边界，并且记得把str[left]地位的值在freqMap中减掉。
循环条件是 left < str.length，容许左边界始终滑动到字符串的右界。
/**
* @param {string} s
* @return {number}
*/
let lengthOfLongestSubstring = function (str) {
let n = str.length
// 滑动窗口为 s[left...right]
let left = 0
let right = -1
let freqMap = {} // 记录以后子串中下标对应的呈现频率
let max = 0 // 找到的满足条件子串的最长长度
while (left < n) {let nextLetter = str[right + 1]
if (!freqMap[nextLetter] && nextLetter !== undefined) {freqMap[nextLetter] = 1
right++
} else {freqMap[str[left]] = 0
left++
}
max = Math.max(max, right - left + 1)
}
return max
}
复制代码链表问题
两两替换链表中的节点 -24
给定一个链表，两两替换其中相邻的节点，并返回替换后的链表。
你不能只是单纯的扭转节点外部的值，而是须要理论的进行节点替换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
复制代码起源：力扣（LeetCode）
链接：leetcode-cn.com/problems/sw…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
这题本意比较简单，1 -> 2 -> 3 -> 4 的状况下能够定义一个递归的辅助函数 helper，这个辅助函数对于节点和它的下一个节点进行替换，比方 helper(1) 解决 1 -> 2，并且把替换变成 2 -> 1 的尾节点 1的 next 持续指向 helper(3)也就是替换后的 4 -> 3。
边界状况在于，如果顺利的作了两两替换，那么替换后咱们的函数返回进来的是 替换后的头部节点 ，然而如果是奇数残余项的状况下，没方法做替换，那就须要间接返回 本来的头部节点 。这个在 helper 函数和主函数中都有体现。
let swapPairs = function (head) {if (!head) return null
let helper = function (node) {
let tempNext = node.next
if (tempNext) {
let tempNextNext = node.next.next
node.next.next = node
if (tempNextNext) {node.next = helper(tempNextNext)
} else {node.next = null}
}
return tempNext || node
}
let res = helper(head)
return res || head
}
复制代码深度优先遍历问题
二叉树的所有门路 -257
给定一个二叉树，返回所有从根节点到叶子节点的门路。
阐明: 叶子节点是指没有子节点的节点。
示例:
输出:
1
/ \
2 3
\
5
输入: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的门路为: 1->2->5, 1->3
复制代码起源：力扣（LeetCode）
链接：leetcode-cn.com/problems/bi…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
用以后节点的值去拼接左右子树递归调用以后函数取得的所有门路。
也就是根节点拼上以左子树为根节点失去的门路，加上根节点拼上以右子树为根节点失去的所有门路。
直到叶子节点，仅仅返回蕴含以后节点的值的数组。
let binaryTreePaths = function (root) {let res = []
if (!root) {return res}
if (!root.left && !root.right) {return [`${root.val}`]
}
let leftPaths = binaryTreePaths(root.left)
let rightPaths = binaryTreePaths(root.right)
leftPaths.forEach((leftPath) => {res.push(`${root.val}->${leftPath}`)
})
rightPaths.forEach((rightPath) => {res.push(`${root.val}->${rightPath}`)
})
return res
}
复制代码广度优先遍历（BFS）问题
在每个树行中找最大值 -515
leetcode-cn.com/problems/fi…
您须要在二叉树的每一行中找到最大的值。
输出:
1
/ \
3 2
/ \ \
5 3 9
输入: [1, 3, 9]
复制代码这是一道典型的 BFS 题目，BFS 的套路其实就是保护一个 queue 队列，在读取子节点的时候同时把发现的孙子节点 push 到队列中，然而 先不解决 ，等到这一轮队列中的子节点解决实现当前，下一轮再持续解决的就是 孙子节点 了，这就实现了层序遍历，也就是一层层的去解决。
然而这里有一个问题卡住我了一会，就是如何晓得以后解决的节点是 哪个层级 的，在最开始的时候我尝试写了一下二叉树求某个 index 所在层级的公式，然而发现这种公式只能解决「均衡二叉树」。
前面看题解发现他们都没有专门保护层级，再认真一看才明确层级的思路：
其实就是在每一轮 while 循环里，再开一个 for 循环，这个 for 循环的起点是「提前缓存好的 length 快照」，也就是进入这轮 while 循环时，queue 的长度。其实这个长度就恰好代表了「一个层级的长度」。
缓存后，for 循环里能够平安的把子节点 push 到数组里而不影响缓存的以后层级长度。
另外有一个小 tips，在 for 循环解决实现后，应该要把 queue 的长度截取掉上述的缓存长度。一开始我应用的是 queue.splice(0, len)，后果速度只击败了 33% 的人。前面换成 for 循环中去一个一个 shift 来截取，速度就击败了 77% 的人。
/**
* @param {TreeNode} root
* @return {number[]}
*/
let largestValues = function (root) {if (!root) return []
let queue = [root]
let maximums = []
while (queue.length) {
let max = Number.MIN_SAFE_INTEGER
// 这里须要先缓存 length 这个 length 代表以后层级的所有节点
// 在循环开始后 会 push 新的节点 length 就不稳固了
let len = queue.length
for (let i = 0; i < len; i++) {let node = queue[i]
max = Math.max(node.val, max)
if (node.left) {queue.push(node.left)
}
if (node.right) {queue.push(node.right)
}
}
// 本「层级」处理完毕，截取掉。for (let i = 0; i < len; i++) {queue.shift()
}
// 这个 for 循环完结后 代表以后层级的节点全副处理完毕
// 间接把计算出来的最大值 push 到数组里即可。maximums.push(max)
}
return maximums
}
复制代码栈问题
无效的括号 -20
给定一个只包含 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否无效。
无效字符串需满足：
- 左括号必须用雷同类型的右括号闭合。
- 左括号必须以正确的程序闭合。
- 留神空字符串可被认为是无效字符串。
示例 1:
输出: "()"
输入: true
复制代码示例 2:
输出: "()[]{}"
输入: true
复制代码示例 3:
输出: "(]"
输入: false
复制代码示例 4:
输出: "([)]"
输入: false
复制代码示例 5:
输出: "{[]}"
输入: true
复制代码leetcode-cn.com/problems/va…
提前记录好左括号类型 (, {, [和右括号类型 ), }, ] 的映射表，当遍历中遇到左括号的时候，就放入栈 stack 中（其实就是数组），当遇到右括号时，就把 stack 顶的元素 pop 进去，看一下是否是这个右括号所匹配的左括号（比方 ( 和 ) 是一对匹配的括号）。
当遍历完结后，栈中不应该剩下任何元素，返回胜利，否则就是失败。
/**
* @param {string} s
* @return {boolean}
*/
let isValid = function (s) {
let sl = s.length
if (sl % 2 !== 0) return false
let leftToRight = {"{": "}",
"[": "]",
"(": ")",
}
// 建设一个反向的 value -> key 映射表
let rightToLeft = createReversedMap(leftToRight)
// 用来匹配左右括号的栈
let stack = []
for (let i = 0; i < s.length; i++) {let bracket = s[i]
// 左括号 放进栈中
if (leftToRight[bracket]) {stack.push(bracket)
} else {let needLeftBracket = rightToLeft[bracket]
// 左右括号都不是 间接失败
if (!needLeftBracket) {return false}
// 栈中取出最初一个括号 如果不是须要的那个左括号 就失败
let lastBracket = stack.pop()
if (needLeftBracket !== lastBracket) {return false}
}
}
if (stack.length) {return false}
return true
}
function createReversedMap(map) {return Object.keys(map).reduce((prev, key) => {const value = map[key]
prev[value] = key
return prev
}, {})
}
复制代码递归与回溯
间接看我写的这两篇文章即可，递归与回溯甚至是平时业务开发中最常见的算法场景之一了，所以我重点总结了两篇文章。
《前端电商 sku 的全排列算法很难吗？学会这个套路，彻底把握排列组合。》
前端「N 皇后」递归回溯经典问题图解
动静布局
打家劫舍 – 198
你是一个业余的小偷，打算偷窃沿街的屋宇。每间房内都藏有肯定的现金，影响你偷窃的惟一制约因素就是相邻的屋宇装有互相连通的防盗零碎，如果两间相邻的屋宇在同一早晨被小偷闯入，零碎会主动报警。
给定一个代表每个屋宇寄存金额的非负整数数组，计算你在不触动警报安装的状况下，可能偷窃到的最高金额。
示例 1:
输出: [1,2,3,1]
输入: 4
解释: 偷窃 1 号屋宇 (金额 = 1)，而后偷窃 3 号屋宇 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4。示例 2:
输出: [2,7,9,3,1]
输入: 12
解释: 偷窃 1 号屋宇 (金额 = 2), 偷窃 3 号屋宇 (金额 = 9)，接着偷窃 5 号屋宇 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12。复制代码起源：力扣（LeetCode）链接：leetcode-cn.com/problems/ho… 著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
动静布局的一个很重要的过程就是找到「状态」和「状态转移方程」，在这个问题里，设 i 是以后屋子的下标，状态就是 以 i 为终点偷窃的最大价值
在某一个房子背后，盗贼只有两种抉择：偷或者不偷。
- 偷的话，价值就是「以后房子的价值」+「下两个房子开始偷盗的最大价值」
- 不偷的话，价值就是「下一个房子开始偷盗的最大价值」
在这两个值中，抉择 最大值 记录在 dp[i]中，就失去了 以 i 为终点所能偷窃的最大价值。。
动静布局的起手式，找 根底状态 ，在这题中，以 起点 为终点的最大价值肯定是最好找的，因为起点不可能再持续往后偷窃了，所以设 n 为房子的总数量，dp[n - 1] 就是 nums[n - 1]，小偷只能抉择偷窃这个房子，而不能跳过去抉择下一个不存在的房子。
那么就找到了动静布局的状态转移方程：
// 抢劫以后房子
robNow = nums[i] + dp[i + 2] //「以后房子的价值」+「i + 2 下标房子为终点的最大价值」// 不抢以后房子，抢下一个房子
robNext = dp[i + 1] //「i + 1 下标房子为终点的最大价值」// 两者抉择最大值
dp[i] = Math.max(robNow, robNext)
复制代码，并且 从后往前 求解。
function (nums) {if (!nums.length) {return 0;}
let dp = [];
for (let i = nums.length - 1; i >= 0; i--) {let robNow = nums[i] + (dp[i + 2] || 0)
let robNext = dp[i + 1] || 0
dp[i] = Math.max(robNow, robNext)
}
return dp[0];
};
复制代码最初返回 以 0 为终点开始打劫的最大价值 即可。
贪婪算法问题
散发饼干 -455
假如你是一位很棒的家长，想要给你的孩子们一些小饼干。然而，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 gi，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 sj。如果 sj >= gi，咱们能够将这个饼干 j 调配给孩子 i，这个孩子会失去满足。你的指标是尽可能满足越多数量的孩子，并输入这个最大数值。
留神：
你能够假如胃口值为正。一个小朋友最多只能领有一块饼干。
示例 1:
输出: [1,2,3], [1,1]
输入: 1
解释:
你有三个孩子和两块小饼干，3 个孩子的胃口值别离是：1,2,3。尽管你有两块小饼干，因为他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。所以你应该输入 1。示例 2:
输出: [1,2], [1,2,3]
输入: 2
解释:
你有两个孩子和三块小饼干，2 个孩子的胃口值别离是 1,2。你领有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输入 2.
复制代码起源：力扣（LeetCode）链接：leetcode-cn.com/problems/as… 著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
把饼干和孩子的需要都排序好，而后从最小的饼干调配给需要最小的孩子开始，一直的尝试新的饼干和新的孩子，这样能保障每个分给孩子的饼干都恰到好处的不节约，又满足需要。
利用双指针一直的更新 i 孩子的需要下标和 j饼干的值，直到两者有其一达到了起点地位：
- 如果以后的饼干不满足孩子的胃口，那么把
j++寻找下一个饼干，不必放心这个饼干被节约，因为这个饼干更不可能满足下一个孩子（胃口更大）。 - 如果满足，那么
i++; j++; count++记录以后的胜利数量，持续寻找下一个孩子和下一个饼干。
/**
* @param {number[]} g
* @param {number[]} s
* @return {number}
*/
let findContentChildren = function (g, s) {g.sort((a, b) => a - b)
s.sort((a, b) => a - b)
let i = 0
let j = 0
let count = 0
while (j < s.length && i < g.length) {let need = g[i]
let cookie = s[j]
if (cookie >= need) {
count++
i++
j++
} else {j++}
}
return count
}
复制代码必做题目
其实写了这么多，以上分类所提到的题目，只是以后分类下比拟适宜作为例题来解说的题目而已，在整个 LeetCode 学习过程中只是冰山一角。这些题能够作为你深刻这个分类的一个入门例题，然而不可避免的是，你必须去下苦功夫刷 每个分类下的其余经典题目。
如果你信赖我，你也能够 点击这里 获取各个分类下 必做题目 的具体题解，我跟着一个 ACM 亚洲区奖牌获得者 给出的提纲，整顿了 100+ 道 必做题目的 具体题解。
那么什么叫必做题目呢？
- 它外围考查 算法思维，而不是奇巧淫技。
- 它考查的知识点，能够 触类旁通 的利用到很多类似题目上。
- 面试热门 题，大厂喜爱考这个题目，阐明这个知识点很重要。
当然你也能够去知乎等平台搜寻相干的问题，也会有很多人总结，然而比我总结的全的不多见。100 多题说多也不多，说少也不少。认真学习、解答、排汇这些题目大略要花费 1 个月 左右的工夫。然而置信我，1 个月当前你在算法方面会本性难移，应答国内大厂的算法面试也会变得熟能生巧。
总结
对于算法在工程方面有用与否的争执，曾经是一个经久不衰的话题了。这里不探讨这个，我集体的观点是 相对有用 的，只有你不是一个甘于只做简略需要的人，你肯定会在后续开发架构、遇到难题的过程中或多或少的从你的算法学习中受害。
再说的功利点，就算是为了面试，刷算法可能进入大厂也是你职业生涯的一个腾飞点，大厂给你带来的的环境、严格的 Code Review、欠缺的导师机制和合作流程也是你作为 工程师 所梦寐以求的。
心愿这篇文章能让你不再持续胆怯算法面试，跟着我一起攻下这座城堡吧，大家加油！