【技能进阶5】刷题不是越多越好，首先要学会套公式

最近似乎到了26届校招er们开始发力的时候了，眼瞅着自己仨师弟师妹都打算走嵌入式这条不归路（不是）并开始准备系统化的学习和做项目了，没啥好劝的，只是把积攒的资料和盘托出给他们；

我们课题组的研究方向是机器人 & AI，所以不管是和嵌入式还是前后端都不搭边，以至于我的工程技术基础其实很一般，属于八股选手和刷题选手，日常靠着全A的笔试和流畅的八股通过前两轮考核，对算法笔试题的评价是：

这玩意就跟咱当年高考数学物理似的，不是刷题越多就越好；

要掌握技巧，把题目分好类，首先得知道这道题要套什么公式才好。

所以参考了一些网上的资料，把一般的笔试题分为了如下15类，建议搭配代码随想录等资源进行学习

1. 前缀和（Prefix Sum）

前缀和模式通过对数组进行预处理，生成一个新数组，其中索引i处的元素表示从数组开头到i位置的元素总和。这种模式能够高效地对子数组进行求和查询。

适用场景：当需要对子数组进行多次求和查询，或者需要计算累加和时，可使用该模式。

示例问题：给定一个数组nums，回答关于特定区间[i, j]内元素之和的多个查询。

示例：

• 输入：nums = [1, 2, 3, 4, 5, 6]，i = 1，j = 3
• 输出：9
• 解释：预处理数组A以创建前缀和数组：P = [1, 3, 6, 10, 15, 21]。要找出索引i和j之间的元素和，使用公式：P[j] - P[i - 1]。

相关题目：

2. 双指针（Two Pointers）

双指针模式使用两个指针来遍历数组或列表，常用于查找满足特定条件的数对或元素。

适用场景：在处理有序数组或列表，且需要查找满足特定条件的数对时，可使用该模式。

示例问题：在一个有序数组中找出两个数，使其和等于目标值。

示例：

• 输入：nums = [1, 2, 3, 4, 6]，target = 6
• 输出：[1, 3]
• 解释：初始化两个指针，一个指向数组开头（左指针），一个指向数组末尾（右指针）。检查两个指针所指元素的和。如果和等于目标值，返回这两个元素的索引。如果和小于目标值，将左指针向右移动。如果和大于目标值，将右指针向左移动。

相关题目：

3. 滑动窗口（Sliding Window）

滑动窗口模式用于查找满足特定条件的子数组或子字符串，通过维护一个元素窗口来优化时间复杂度。

适用场景：在处理涉及连续子数组或子字符串的问题时，可使用该模式。

示例问题：找出大小为k的子数组的最大和。

示例：

• 输入：nums = [2, 1, 5, 1, 3, 2]，k = 3
• 输出：9
• 解释：先计算前k个元素的和。每次将窗口向右滑动一个元素，减去移出窗口的元素，再加上新进入窗口的元素。记录遇到的最大和。

相关题目：

4. 快慢指针（Fast & Slow Pointers）

快慢指针（龟兔赛跑，Tortoise and Hare）模式用于检测链表及其他类似结构中是否存在循环。

适用场景：在检测链表是否存在循环时，可使用该模式。

示例问题：检测一个链表是否存在循环。

解释：初始化两个指针，一个每次移动一步（慢指针），另一个每次移动两步（快指针）。如果存在循环，快指针最终会与慢指针相遇。如果快指针到达链表末尾，则不存在循环。

相关题目：

5. 链表原地反转（LinkedList In-place Reversal）

链表原地反转模式可在不使用额外空间的情况下，反转链表的部分节点。

适用场景：当你需要反转链表的某些部分时，可使用该模式。

示例问题：反转链表中从位置m到n的子链表。

示例：

• 输入：head = [1, 2, 3, 4, 5]，m = 2，n = 4
• 输出：[1, 4, 3, 2, 5]
• 解释：确定子链表的起始和结束位置。通过调整指针来原地反转节点。

相关题目：

6. 单调栈（Monotonic Stack）

单调栈模式使用栈来维护按特定顺序（递增或递减）排列的元素序列。

适用场景：在需要查找下一个更大或更小元素的问题中，可使用该模式。

示例问题：找出数组中每个元素的下一个更大元素。如果不存在更大元素，则输出-1。

示例：

• 输入：nums = [2, 1, 2, 4, 3]
• 输出：[4, 2, 4, -1, -1]
• 解释：使用栈来记录那些还未找到下一个更大元素的元素。遍历数组，对于每个元素，将栈中元素弹出，直到找到一个更大的元素。如果栈不为空，将栈顶元素对应的结果设置为当前元素。将当前元素入栈。

相关题目：

7. 前K大（小）元素（Top ‘K’ Elements）

前K大（小）元素模式使用堆或排序的方法，从数组或数据流中找出前k个最大或最小的元素。

适用场景：在需要从数组或数据流中找出前k个最大或最小元素时，可使用该模式。

示例问题：在一个未排序的数组中找出第k个最大的元素。

示例：

• 输入：nums = [3, 2, 1, 5, 6, 4]，k = 2
• 输出：5
• 解释：使用大小为k的最小堆来跟踪k个最大元素。遍历数组，将元素加入堆中。如果堆的大小超过k，则移除堆中最小的元素。堆顶元素就是第k个最大元素。

相关题目：

8. 区间重叠（Overlapping Intervals）

区间重叠模式用于合并或处理数组中的重叠区间。

适用场景：在按起始时间排序的区间数组中，两个区间[a, b]和[c, d]重叠的条件是b >= c（即第一个区间的结束时间大于或等于第二个区间的起始时间）。

示例问题：给定一个区间列表，合并所有重叠的区间。

示例：

• 输入：intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
• 输出：[[1, 6], [8, 10], [15, 18]]
• 解释：按区间的起始时间对区间进行排序。创建一个名为merged的空列表，用于存储合并后的区间。遍历区间，检查它是否与merged列表中的最后一个区间重叠。如果重叠，通过更新merged列表中最后一个区间的结束时间来合并区间。如果不重叠，直接将当前区间添加到merged列表中。

相关题目：

9. 变形二分查找（Modified Binary Search）

变形二分查找模式对二分查找进行改进，以解决更广泛的问题，例如在旋转排序数组中查找元素。

适用场景：在处理涉及排序或旋转数组，且需要查找特定元素的问题时，可使用该模式。

示例问题：在一个旋转排序数组中查找元素。

示例：

• 输入：nums = [4, 5, 6, 7, 0, 1, 2]，target = 0
• 输出：4
• 解释：进行二分查找时，额外增加一个判断，以确定数组的哪一半是有序的。然后检查目标元素是否在有序的那一半范围内。如果在，就在这一半中查找；否则，在另一半中查找。

相关题目：

10. 二叉树遍历（Binary Tree Traversal）

二叉树遍历是按照特定顺序访问二叉树中的所有节点。

• 前序遍历：根 -> 左 -> 右
• 中序遍历：左 -> 根 -> 右
• 后序遍历：左 -> 右 -> 根

适用场景：在需要按照特定顺序访问二叉树节点时，可使用该模式。

示例问题：对二叉树进行中序遍历。

示例：

• 输入：root = [1, null, 2, 3]
• 输出：[1, 3, 2]
• 解释：中序遍历按照左、根、右的顺序访问节点。可使用递归或栈来按此顺序遍历树。

相关题目：

11. 深度优先搜索（Depth-First Search，DFS）

深度优先搜索（DFS）是一种遍历技术，它会沿着一条分支尽可能深入地探索，然后再回溯。

适用场景：在探索图或树中的所有路径或分支时，可使用该模式。

示例问题：找出二叉树中从根节点到叶节点的所有路径。

示例：

• 输入：root = [1, 2, 3, null, 5]
• 输出：["1->2->5", "1->3"]
• 解释：使用递归或栈来遍历从根节点到叶节点的每条路径。在遍历过程中记录每条路径。

相关题目：

12. 广度优先搜索（Breadth-First Search，BFS）

广度优先搜索（BFS）是一种遍历技术，它按照树或图的层次依次探索节点。

适用场景：在查找无权图中的最短路径或对树进行层序遍历时，可使用该模式。

示例问题：对二叉树进行层序遍历。

示例：

• 输入：root = [3, 9, 20, null, null, 15, 7]
• 输出：[[3], [9, 20], [15, 7]]
• 解释：使用队列来记录每一层的节点。遍历每一层，并将当前节点的子节点加入队列。

相关题目：

13. 矩阵遍历（Matrix Traversal）

矩阵遍历涉及使用不同的技术（如DFS、BFS等）遍历矩阵中的元素。

适用场景：在处理涉及横向、纵向或对角线遍历二维网格或矩阵的问题时，可使用该模式。

示例问题：对二维网格进行颜色填充。将与起始单元格相连通的所有单元格都更改为新颜色。

示例：

• 输入：image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1，sc = 1，newColor = 2
• 输出：[[2,2,2],[2,2,0],[2,0,1]]
• 解释：使用DFS或BFS从给定单元格开始遍历矩阵。将连通单元格的颜色更改为新颜色。

相关题目：

14. 回溯（Backtracking）

回溯算法会探索所有可能的解，当某条解的路径行不通时就回溯。

适用场景：当你需要找出满足给定约束条件的所有（或部分）解时，例如组合问题（生成排列、组合或子集等），可使用该模式。

示例问题：生成给定数字列表的所有排列。

示例：

• 输入：nums = [1, 2, 3]
• 输出：[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
• 解释：使用递归来生成排列。对于每个元素，将其包含在当前排列中，并递归地生成剩余元素的排列。当某条路径下的所有排列都生成后，进行回溯。

相关题目：

15. 动态规划模式（Dynamic Programming Patterns）

动态规划（DP）是将问题分解为更小的子问题，并使用自底向上或自顶向下的方法来解决它们。

适用场景：在处理具有重叠子问题和最优子结构特性的问题时，可使用该模式。

动态规划本身包含多个子模式，其中一些最重要的子模式如下：

• 斐波那契数列
• 0/1背包问题
• 最长公共子序列（LCS）
• 最长递增子序列（LIS）
• 子集和问题
• 矩阵链乘法

示例问题：计算第n个斐波那契数。

示例：

• 输入：n = 5
• 输出：5（前五个斐波那契数是0，1，1，2，3，5）
• 解释：使用自底向上的方法来计算第n个斐波那契数。从最初的两个数（0和1）开始，通过迭代计算后续的数，如dp[i] = dp[i - 1] + dp[i - 2]。

相关题目：

#牛客激励计划##刷题##笔试#