• 前端的算法进阶指南


    分类大纲

    1. 算法的复杂度分析。

    2. 排序算法,以及他们的区别和优化。

    3. 数组中的双指针、滑动窗口思想。

    4. 利用 Map 和 Set 处理查找表问题。

    5. 链表的各种问题。

    6. 利用递归和迭代法解决二叉树问题。

    7. 栈、队列、DFS、BFS。

    8. 回溯法、贪心算法、动态规划。

    题解

    接下来我会放出几个分类的经典题型,以及我对应的讲解,当做开胃菜,并且在文章的末尾我会给出获取每个分类推荐你去刷的题目的合集,记得看到底哦。

    查找表问题

    两个数组的交集 II-350

    给定两个数组,编写一个函数来计算它们的交集。

    1. 示例 1:
    2. 输入: nums1 = [1,2,2,1], nums2 = [2,2]
    3. 输出: [2,2]
    4. 示例 2:
    5. 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
    6. 输出: [4,9]

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/intersection-of-two-arrays-ii
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


    为两个数组分别建立 map,用来存储 num -> count 的键值对,统计每个数字出现的数量。

    然后对其中一个 map 进行遍历,查看这个数字在两个数组中分别出现的数量,取出现的最小的那个数量(比如数组 1 中出现了 1 次,数组 2 中出现了 2 次,那么交集应该取 1 次),push 到结果数组中即可。

    1. /**
    2.  * @param {number[]nums1
    3.  * @param {number[]nums2
    4.  * @return {number[]}
    5.  */
    6. let intersect = function (nums1, nums2) {
    7.   let map1 = makeCountMap(nums1)
    8.   let map2 = makeCountMap(nums2)
    9.   let res = []
    10.   for (let num of map1.keys()) {
    11.     const count1 = map1.get(num)
    12.     const count2 = map2.get(num)
    13.     if (count2) {
    14.       const pushCount = Math.min(count1, count2)
    15.       for (let i = 0; i < pushCount; i++) {
    16.         res.push(num)
    17.       }
    18.     }
    19.   }
    20.   return res
    21. }
    22. function makeCountMap(nums) {
    23.   let map = new Map()
    24.   for (let i = 0; i < nums.length; i++) {
    25.     let num = nums[i]
    26.     let count = map.get(num)
    27.     if (count) {
    28.       map.set(num, count + 1)
    29.     } else {
    30.       map.set(num, 1)
    31.     }
    32.   }
    33.   return map
    34. }

    双指针问题

    最接近的三数之和-16

    给定一个包括  n 个整数的数组  nums  和 一个目标值  target。找出  nums  中的三个整数,使得它们的和与  target  最接近。返回这三个数的和。假定每组输入只存在唯一答案。

    1. 示例:
    2. 输入:nums = [-1,2,1,-4], target = 1
    3. 输出:2
    4. 解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

    提示:

    3 <= nums.length <= 10^3-10^3 <= nums[i] <= 10^3-10^4 <= target <= 10^4

    来源:力扣(LeetCode)

    链接:https://leetcode-cn.com/problems/3sum-closest

    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


    先按照升序排序,然后分别从左往右依次选择一个基础点 i0 <= i <= nums.length - 3),在基础点的右侧用双指针去不断的找最小的差值。

    假设基础点是 i,初始化的时候,双指针分别是:

    • lefti + 1,基础点右边一位。

    • rightnums.length - 1 数组最后一位。

    然后求此时的和,如果和大于 target,那么可以把右指针左移一位,去试试更小一点的值,反之则把左指针右移。

    在这个过程中,不断更新全局的最小差值 min,和此时记录下来的和 res

    最后返回 res 即可。

    1. /**
    2.  * @param {number[]nums
    3.  * @param {numbertarget
    4.  * @return {number}
    5.  */
    6. let threeSumClosest = function (nums, target) {
    7.   let n = nums.length
    8.   if (n === 3) {
    9.     return getSum(nums)
    10.   }
    11.   // 先升序排序 此为解题的前置条件
    12.   nums.sort((a, b) => a - b)
    13.   let min = Infinity // 和 target 的最小差
    14.   let res
    15.   // 从左往右依次尝试定一个基础指针 右边至少再保留两位 否则无法凑成3个
    16.   for (let i = 0; i <= nums.length - 3; i++) {
    17.     let basic = nums[i]
    18.     let left = i + 1 // 左指针先从 i 右侧的第一位开始尝试
    19.     let right = n - 1 // 右指针先从数组最后一项开始尝试
    20.     while (left < right) {
    21.       let sum = basic + nums[left] + nums[right] // 三数求和
    22.       // 更新最小差
    23.       let diff = Math.abs(sum - target)
    24.       if (diff < min) {
    25.         min = diff
    26.         res = sum
    27.       }
    28.       if (sum < target) {
    29.         // 求出的和如果小于目标值的话 可以尝试把左指针右移 扩大值
    30.         left++
    31.       } else if (sum > target) {
    32.         // 反之则右指针左移
    33.         right--
    34.       } else {
    35.         // 相等的话 差就为0 一定是答案
    36.         return sum
    37.       }
    38.     }
    39.   }
    40.   return res
    41. }
    42. function getSum(nums) {
    43.   return nums.reduce((total, cur) => total + cur, 0)
    44. }

    滑动窗口问题

    无重复字符的最长子串-3

    给定一个字符串,请你找出其中不含有重复字符的   最长子串   的长度。

    示例  1:

    1. 输入: "abcabcbb"
    2. 输出: 3
    3. 解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3

    示例 2:

    1. 输入: "bbbbb"
    2. 输出: 1
    3. 解释: 因为无重复字符的最长子串是 "b",所以其长度为 1

    示例 3:

    1. 输入: "pwwkew"
    2. 输出: 3
    3. 解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3
    4.      请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


    这题是比较典型的滑动窗口问题,定义一个左边界 left 和一个右边界 right,形成一个窗口,并且在这个窗口中保证不出现重复的字符串。

    这需要用到一个新的变量 freqMap,用来记录窗口中的字母出现的频率数。在此基础上,先尝试取窗口的右边界再右边一个位置的值,也就是 str[right + 1],然后拿这个值去 freqMap 中查找:

    1. 这个值没有出现过,那就直接把 right ++,扩大窗口右边界。

    2. 如果这个值出现过,那么把 left ++,缩进左边界,并且记得把 str[left] 位置的值在 freqMap 中减掉。

    循环条件是 left < str.length,允许左边界一直滑动到字符串的右界。

    1. /**
    2.  * @param {strings
    3.  * @return {number}
    4.  */
    5. let lengthOfLongestSubstring = function (str) {
    6.   let n = str.length
    7.   // 滑动窗口为s[left...right]
    8.   let left = 0
    9.   let right = -1
    10.   let freqMap = {} // 记录当前子串中下标对应的出现频率
    11.   let max = 0 // 找到的满足条件子串的最长长度
    12.   while (left < n) {
    13.     let nextLetter = str[right + 1]
    14.     if (!freqMap[nextLetter] && nextLetter !== undefined) {
    15.       freqMap[nextLetter] = 1
    16.       right++
    17.     } else {
    18.       freqMap[str[left]] = 0
    19.       left++
    20.     }
    21.     max = Math.max(max, right - left + 1)
    22.   }
    23.   return max
    24. }

    链表问题

    两两交换链表中的节点-24

    给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

    你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

    示例:

    给定 1->2->3->4, 你应该返回 2->1->4->3.
    

    来源:力扣(LeetCode)

    链接:https://leetcode-cn.com/problems/swap-nodes-in-pairs

    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


    这题本意比较简单,1 -> 2 -> 3 -> 4 的情况下可以定义一个递归的辅助函数 helper,这个辅助函数对于节点和它的下一个节点进行交换,比如 helper(1) 处理 1 -> 2,并且把交换变成 2 -> 1 的尾节点 1next继续指向 helper(3)也就是交换后的 4 -> 3

    边界情况在于,如果顺利的作了两两交换,那么交换后我们的函数返回出去的是 交换后的头部节点,但是如果是奇数剩余项的情况下,没办法做交换,那就需要直接返回 原本的头部节点。这个在 helper函数和主函数中都有体现。

    1. let swapPairs = function (head) {
    2.   if (!head) return null
    3.   let helper = function (node) {
    4.     let tempNext = node.next
    5.     if (tempNext) {
    6.       let tempNextNext = node.next.next
    7.       node.next.next = node
    8.       if (tempNextNext) {
    9.         node.next = helper(tempNextNext)
    10.       } else {
    11.         node.next = null
    12.       }
    13.     }
    14.     return tempNext || node
    15.   }
    16.   let res = helper(head)
    17.   return res || head
    18. }

    深度优先遍历问题

    二叉树的所有路径-257

    给定一个二叉树,返回所有从根节点到叶子节点的路径。

    说明:  叶子节点是指没有子节点的节点。

    示例:

    1. 输入:
    2.    1
    3.  /   \
    4. 2     3
    5.  \
    6.   5
    7. 输出: ["1->2->5""1->3"]
    8. 解释: 所有根节点到叶子节点的路径为: 1->2->51->3

    来源:力扣(LeetCode)

    链接:https://leetcode-cn.com/problems/binary-tree-paths

    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


    用当前节点的值去拼接左右子树递归调用当前函数获得的所有路径。

    也就是根节点拼上以左子树为根节点得到的路径,加上根节点拼上以右子树为根节点得到的所有路径。

    直到叶子节点,仅仅返回包含当前节点的值的数组。

    1. let binaryTreePaths = function (root) {
    2.   let res = []
    3.   if (!root) {
    4.     return res
    5.   }
    6.   if (!root.left && !root.right) {
    7.     return [`${root.val}`]
    8.   }
    9.   let leftPaths = binaryTreePaths(root.left)
    10.   let rightPaths = binaryTreePaths(root.right)
    11.   leftPaths.forEach((leftPath) => {
    12.     res.push(`${root.val}->${leftPath}`)
    13.   })
    14.   rightPaths.forEach((rightPath) => {
    15.     res.push(`${root.val}->${rightPath}`)
    16.   })
    17.   return res
    18. }

    广度优先遍历(BFS)问题

    在每个树行中找最大值-515

    https://leetcode-cn.com/problems/find-largest-value-in-each-tree-row

    您需要在二叉树的每一行中找到最大的值。

    1. 输入:
    2.           1
    3.          / \
    4.         3   2
    5.        / \   \
    6.       5   3   9
    7. 输出: [139]

    这是一道典型的 BFS 题目,BFS 的套路其实就是维护一个 queue 队列,在读取子节点的时候同时把发现的孙子节点 push 到队列中,但是先不处理,等到这一轮队列中的子节点处理完成以后,下一轮再继续处理的就是孙子节点了,这就实现了层序遍历,也就是一层层的去处理。

    但是这里有一个问题卡住我了一会,就是如何知道当前处理的节点是哪个层级的,在最开始的时候我尝试写了一下二叉树求某个 index 所在层级的公式,但是发现这种公式只能处理「平衡二叉树」。

    后面看题解发现他们都没有专门维护层级,再仔细一看才明白层级的思路:

    其实就是在每一轮 while 循环里,再开一个 for 循环,这个 for 循环的终点是「提前缓存好的 length 快照」,也就是进入这轮 while 循环时,queue 的长度。其实这个长度就恰好代表了「一个层级的长度」。

    缓存后,for 循环里可以安全的把子节点 push 到数组里而不影响缓存的当前层级长度。

    另外有一个小 tips,在 for 循环处理完成后,应该要把 queue 的长度截取掉上述的缓存长度。一开始我使用的是 queue.splice(0, len),结果速度只击败了 33%的人。后面换成 for 循环中去一个一个shift来截取,速度就击败了 77%的人。

    1. /**
    2.  * @param {TreeNoderoot
    3.  * @return {number[]}
    4.  */
    5. let largestValues = function (root) {
    6.   if (!root) return []
    7.   let queue = [root]
    8.   let maximums = []
    9.   while (queue.length) {
    10.     let max = Number.MIN_SAFE_INTEGER
    11.     // 这里需要先缓存length 这个length代表当前层级的所有节点
    12.     // 在循环开始后 会push新的节点 length就不稳定了
    13.     let len = queue.length
    14.     for (let i = 0; i < len; i++) {
    15.       let node = queue[i]
    16.       max = Math.max(node.val, max)
    17.       if (node.left) {
    18.         queue.push(node.left)
    19.       }
    20.       if (node.right) {
    21.         queue.push(node.right)
    22.       }
    23.     }
    24.     // 本「层级」处理完毕,截取掉。
    25.     for (let i = 0; i < len; i++) {
    26.       queue.shift()
    27.     }
    28.     // 这个for循环结束后 代表当前层级的节点全部处理完毕
    29.     // 直接把计算出来的最大值push到数组里即可。
    30.     maximums.push(max)
    31.   }
    32.   return maximums
    33. }

    栈问题

    有效的括号-20

    给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

    有效字符串需满足:

    • 左括号必须用相同类型的右括号闭合。

    • 左括号必须以正确的顺序闭合。

    • 注意空字符串可被认为是有效字符串。

    示例 1:

    1. 输入: "()"
    2. 输出: true

    示例 2:

    1. 输入: "()[]{}"
    2. 输出: true

    示例 3:

    1. 输入: "(]"
    2. 输出: false

    示例 4:

    1. 输入: "([)]"
    2. 输出: false

    示例 5:

    1. 输入: "{[]}"
    2. 输出: true

    https://leetcode-cn.com/problems/valid-parentheses


    提前记录好左括号类型 (, {, [和右括号类型), }, ]的映射表,当遍历中遇到左括号的时候,就放入栈 stack 中(其实就是数组),当遇到右括号时,就把 stack 顶的元素 pop 出来,看一下是否是这个右括号所匹配的左括号(比如 ( 和 ) 是一对匹配的括号)。

    当遍历结束后,栈中不应该剩下任何元素,返回成功,否则就是失败。

    1. /**
    2.  * @param {strings
    3.  * @return {boolean}
    4.  */
    5. let isValid = function (s) {
    6.   let sl = s.length
    7.   if (sl % 2 !== 0return false
    8.   let leftToRight = {
    9.     "{""}",
    10.     "[""]",
    11.     "("")",
    12.   }
    13.   // 建立一个反向的 value -> key 映射表
    14.   let rightToLeft = createReversedMap(leftToRight)
    15.   // 用来匹配左右括号的栈
    16.   let stack = []
    17.   for (let i = 0; i < s.length; i++) {
    18.     let bracket = s[i]
    19.     // 左括号 放进栈中
    20.     if (leftToRight[bracket]) {
    21.       stack.push(bracket)
    22.     } else {
    23.       let needLeftBracket = rightToLeft[bracket]
    24.       // 左右括号都不是 直接失败
    25.       if (!needLeftBracket) {
    26.         return false
    27.       }
    28.       // 栈中取出最后一个括号 如果不是需要的那个左括号 就失败
    29.       let lastBracket = stack.pop()
    30.       if (needLeftBracket !== lastBracket) {
    31.         return false
    32.       }
    33.     }
    34.   }
    35.   if (stack.length) {
    36.     return false
    37.   }
    38.   return true
    39. }
    40. function createReversedMap(map) {
    41.   return Object.keys(map).reduce((prev, key) => {
    42.     const value = map[key]
    43.     prev[value] = key
    44.     return prev
    45.   }, {})
    46. }

    递归与回溯

    直接看我写的这两篇文章即可,递归与回溯甚至是平常业务开发中最常见的算法场景之一了,所以我重点总结了两篇文章。

    《前端电商 sku 的全排列算法很难吗?学会这个套路,彻底掌握排列组合。》[1]

    前端「N 皇后」递归回溯经典问题图解[2]

    动态规划

    打家劫舍 - 198

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

    给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。

    1. 示例 1:
    2. 输入: [1,2,3,1]
    3. 输出: 4
    4. 解释: 偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
    5.   偷窃到的最高金额 = 1 + 3 = 4 。
    6. 示例 2:
    7. 输入: [2,7,9,3,1]
    8. 输出: 12
    9. 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
    10.   偷窃到的最高金额 = 2 + 9 + 1 = 12 。

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/house-robber 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


    动态规划的一个很重要的过程就是找到「状态」和「状态转移方程」,在这个问题里,设 i 是当前屋子的下标,状态就是 以 i 为起点偷窃的最大价值

    在某一个房子面前,盗贼只有两种选择:偷或者不偷

    1. 偷的话,价值就是「当前房子的价值」+「下两个房子开始盗窃的最大价值」

    2. 不偷的话,价值就是「下一个房子开始盗窃的最大价值」

    在这两个值中,选择最大值记录在 dp[i]中,就得到了以 i 为起点所能偷窃的最大价值。

    动态规划的起手式,找基础状态,在这题中,以终点为起点的最大价值一定是最好找的,因为终点不可能再继续往后偷窃了,所以设 n 为房子的总数量, dp[n - 1] 就是 nums[n - 1],小偷只能选择偷窃这个房子,而不能跳过去选择下一个不存在的房子。

    那么就找到了动态规划的状态转移方程:

    1. // 抢劫当前房子
    2. robNow = nums[i] + dp[i + 2// 「当前房子的价值」 + 「i + 2 下标房子为起点的最大价值」
    3. // 不抢当前房子,抢下一个房子
    4. robNext = dp[i + 1//「i + 1 下标房子为起点的最大价值」
    5. // 两者选择最大值
    6. dp[i] = Math.max(robNow, robNext)

    ,并且从后往前求解。

    1. function (nums) {
    2.   if (!nums.length) {
    3.     return 0;
    4.   }
    5.   let dp = [];
    6.   for (let i = nums.length - 1; i >= 0; i--) {
    7.     let robNow = nums[i] + (dp[i + 2] || 0)
    8.     let robNext = dp[i + 1] || 0
    9.     dp[i] = Math.max(robNow, robNext)
    10.   }
    11.   return dp[0];
    12. };

    最后返回 以 0 为起点开始打劫的最大价值 即可。

    贪心算法问题

    分发饼干-455

    假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i ,都有一个胃口值  gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

    注意:

    你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。

    1. 示例 1:
    2. 输入: [1,2,3], [1,1]
    3. 输出: 1
    4. 解释:
    5. 你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3
    6. 虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
    7. 所以你应该输出1
    8. 示例 2:
    9. 输入: [1,2], [1,2,3]
    10. 输出: 2
    11. 解释:
    12. 你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2
    13. 你拥有的饼干数量和尺寸都足以让所有孩子满足。
    14. 所以你应该输出2.

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/assign-cookies 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


    把饼干和孩子的需求都排序好,然后从最小的饼干分配给需求最小的孩子开始,不断的尝试新的饼干和新的孩子,这样能保证每个分给孩子的饼干都恰到好处的不浪费,又满足需求。

    利用双指针不断的更新 i 孩子的需求下标和 j饼干的值,直到两者有其一达到了终点位置:

    1. 如果当前的饼干不满足孩子的胃口,那么把 j++ 寻找下一个饼干,不用担心这个饼干被浪费,因为这个饼干更不可能满足下一个孩子(胃口更大)。

    2. 如果满足,那么 i++; j++; count++ 记录当前的成功数量,继续寻找下一个孩子和下一个饼干。

    1. /**
    2.  * @param {number[]g
    3.  * @param {number[]s
    4.  * @return {number}
    5.  */
    6. let findContentChildren = function (g, s) {
    7.   g.sort((a, b) => a - b)
    8.   s.sort((a, b) => a - b)
    9.   let i = 0
    10.   let j = 0
    11.   let count = 0
    12.   while (j < s.length && i < g.length) {
    13.     let need = g[i]
    14.     let cookie = s[j]
    15.     if (cookie >= need) {
    16.       count++
    17.       i++
    18.       j++
    19.     } else {
    20.       j++
    21.     }
    22.   }
    23.   return count
    24. }

    必做题目

    其实写了这么多,以上分类所提到的题目,只是当前分类下比较适合作为例题来讲解的题目而已,在整个 LeetCode 学习过程中只是冰山一角。这些题可以作为你深入这个分类的一个入门例题,但是不可避免的是,你必须去下苦功夫刷每个分类下的其他经典题目

    如果你信任我,你也可以在我维护的题解仓库的 Issues 中[3]获取各个分类下必做题目的详细题解(拿到了记得收藏),我跟着一个ACM 亚洲区奖牌获得者给出的提纲,整理了100+道必做题目的详细题解

    那么什么叫必做题目呢?

    1. 它核心考察算法思想,而不是奇巧淫技。

    2. 它考察的知识点,可以举一反三的应用到很多相似题目上。

    3. 面试热门题,大厂喜欢考这个题目,说明这个知识点很重要。

    当然你也可以去知乎等平台搜索相关的问题,也会有很多人总结,但是比我总结的全的不多见。100 多题说多也不多,说少也不少。认真学习、解答、吸收这些题目大概要花费1 个月左右的时间。但是相信我,1 个月以后你在算法方面会脱胎换骨,应对国内大厂的算法面试也会变得游刃有余。

    总结

  • 相关阅读:
    计算机视觉图像处理面试笔试题整理——图像配准和图像拼接
    力扣第五十六题——合并区间
    mysql:如何设计互相关注业务场景
    matlab实现QPSK信号的产生与调制
    Flutter应用发布流程详解:从开发到上架一站式指南
    【PTE-day05 宽字节注入】
    [安卓android毕业设计]精品基于Uniapp+SSM实现的校园心理健康APP[源码]
    Oracle LiveLabs实验:Configure network environment for Oracle Database 21c
    达人评测 i7 12800hx和i9 12900h选哪个好
    企业架构LNMP学习笔记8
  • 原文地址:https://blog.csdn.net/qq_41581588/article/details/126164868