大厂面试笔试算法精华题¶

本文讨论了大厂面试笔试算法精华题相关内容，涵盖AI大模型教程、二叉树和数组等经典问题及回溯、动态规划等算法问题。关键要点包括：

AI大模型教程：有全套教程和企业级应用开发教程，还有MCP Server开发零基础教程，也探讨了AI大模型工程师就业现状及学习方向等问题。

二叉树相关：介绍了满二叉树、完美二叉树、完全二叉树、二叉搜索树和平衡二叉树的概念，还给出了给定节点总数时完全二叉树最小高度、是否为满二叉树的判断方法，以及二叉搜索树前驱后继查找、节点删除和不同结构数量计算的方法。

数组算法：讲解了二分查找的闭区间、开区间和左闭右开区间三种写法，以及滑动窗口算法和二分答案算法在寻找非负整数数组中和不大于给定值的最长子数组长度问题中的应用。

回溯算法：是通过穷举所有可能解求解问题的方法，适用于枚举子集、解决组合和排列问题等，在解题时要确定搜索空间、策略和终止条件，可利用剪枝优化搜索。

其他经典问题：还提及了动态规划、基础数据结构（链表、队列、栈）、字符串、基础图论和基础计算几何等经典问题。

二叉树经典问题¶

什么是满二叉树、完全二叉树、完美二叉树、二叉搜索树和平衡二叉树？下面逐个解释这些概念：

满二叉树（Full Binary Tree）是一种特殊的二叉树结构，其中每个节点要么是叶子节点（没有子节点），要么有两个子节点。这意味着每一层上的节点都是完全填满的

完美二叉树（Perfect Binary Tree）是一种特殊的二叉树结构，其中每个节点要么是叶子节点（没有子节点），要么有两个子节点，并且左右子树都完全相同。这意味着每一层上的节点都是完全填满的。和满

二叉树最大的不同在于，完美二叉树不是节点粒度上的填满，而是层粒度上的填满

完全二叉树（Complete Binary Tree）是一种特殊的二叉树结构，其中除了最后一层节点，其他层节点都是满的，并且最后一层节点从左向右依次排布。这是一种完美二叉树的弱化版本，因为完美二叉树尽管拥有很多很好的性质，但是最后一层的节点数量会指数上升。而完全二叉树是一种可以动态决定最后一层节点数量的二叉树结构，同时保证了完美二叉树的一些良好性质（平衡性），主要用于实现堆数据结构

二叉搜索树是一种有序的二叉树，其中每个节点的值都满足一定的排序规则：对于任意一个节点，其左子树上所有节点的值都小于该节点的值，而右子树上所有节点的值都大于该节点的值。二叉搜索树是一种常见的数据结构，其中每一个子树也是二叉搜索树，利用这个性质可以递归构造二叉搜索树

平衡二叉树是一种特殊的二叉搜索树，它保持二叉树的高度尽可能小，从而确保查找、插入、删除操作的时间复杂度尽量接近 $ O(\text{log}_n) $。平衡二叉树需要定义平衡规则，而由于二叉树的操作时间复杂度和树的高度直接相关，所以平衡二叉树的规则基本都是限制住树的高度。最常见的两种平衡二叉树是 AVL 树和红黑树，在 AVL 树中，任何节点的两个子树的高度差最多为 1，而红黑树更加复杂，想了解更多可以参考 $ \underline{\text{深入理解红黑树}} $

给定节点总数，完全二叉树可能的最小高度是多少？¶

高度（从1开始）为的完美二叉树有个节点。那么可以得到高度为的完全二叉树的节点数量满足。于是给定节点数量，我们试图找到第一个，其满足，那么就可以得到最小的高度

给定节点总数，这有可能是一棵满二叉树吗？¶

满二叉树的节点数量，所以只需要判断是否为偶数即可

二叉搜索树的前驱后继怎么找（迭代实现）？¶

下面给出二叉树的寻找前驱的迭代实现。

代码块 1 class TreeNode: 2 def init(self, val=0, parent=None, left=None, right=None): 3 self.val = val 4 self.left = left 5 self.right = right 6 self.parent = parent 7 8 def find_preprocessor(root, val): 9 cur = self.root

二叉搜索树的怎么删除一个节点？¶

二叉搜索树的删除操作没有那么简单，总共可以分为以下几种情况：

删除的节点是叶子节点，直接删除即可

删除的节点只有一个子节点，那么直接将子节点替换到删除节点的位置即可

删除的节点有两个子节点，那么需要找到这个节点的右子树中的最小节点，将这个节点的值替换到删除节点的位置，然后删除这个最小节点即可

下面是实现的参考代码：¶

代码块¶

def transplant(root, u, v): # 移植子树 v 到 u 的位置，并且调整关系 if u.parent is None: root = v elif u == u.parent.left: u.parent.left = v else:

u.parent.right = v if v: v.parent = u.parent

def delete(root, val): cur = root # 找到 cur 的位置 while cur and cur.val != val: if val < cur.val: cur = cur.left else: cur = cur.right

结点数量为 n 的二叉树，有多少种不同的结构？¶

由于不同的二叉树结构决定了递归的顺序问题（出栈和入栈），令表示进栈，表示出栈，则可转化为求一个\（位、含个、个的二进制数，满足从左往右扫描到任意一位时，经过的数不多于数。显然，含个和个的位二进制数共有个，下面考虑不满足要求的数目

假设其中不合法的序列在位置处，此时恰好的数量比多一位，那么必然后面的的数量比多一位，具体而言，有位，有位。我们将及之后的序列进行反转，即可得到一个包含了个，个的序列。注意这是一个双射的过程，即一个不合法的序列经过构造始终得到唯一的一个包含了个，个的序列，而反过来该序列唯一对应一个不合法的序列。下面证明：

定义映射：从不满足条件的个和个的序列到个和个的序列。映射的构造：找到第一个违反条件的位置（称为关键位置）将此位置之后的所有变，变

证明是单射（一对一）：

假设两个不同的不满足条件的序列和映射到同一个序列：

和的关键位置必然相同（否则映射结果会不同）

如果和在关键位置之前有任何不同，映射后仍然不同

如果和在关键位置之后有任何不同，由于和互换，映射后仍然不同

因此，不可能有两个不同的序列映射到同一个序列。

证明是满射（映上）：

对于任何一个和个的序列，从左到右扫描，必然存在一个位置，的数量比的数量多2（因为总共多2个。这个位置就是我们寻找的关键位置，将此位置之后的和互换，得到一个个和个的序列。在关键位置之前满足条件，在关键位置不满足条件，因此是一个不满足原条件的序列，且

证明的逆映射：

对于任何一个和个的序列，找到比多2的位置（一定存在且唯一）。将此位置之后的和互换，这个过程是上述映射的逆过程

证毕所以合法的序列（也就是二叉树不同结构数量）等于：也就是卡特兰数。其实卡特兰数还满足以下的性质：可以看成是左子树的数量，可以看成是右子树的数量，根据乘法原理即可得到总的数量。

数组经典问题（双指针、滑动窗口、二分）¶

二分查找如何实现？开区间写法、闭区间写法？¶

二分查找是在有序数组中进行高效查找的简单算法，而且可以更加广义地使用在单调（非严格、严格）的函数上，于是可以得到算法模板常用的二分答案，其中最重要的事实在于证明计算的结果是具有某种单调性质的

不同于二分查找的思想，二分查找的实现具有大量的细节。下面主要以开闭区间为依据介绍三种常见的实现。

闭区间的写法是最为经典也是最为常见的实现，其中核心的形式为，其中和分别为左右边界，为数组长度。

我们可以定义一个函数，如果为真，则属于右侧合法区间，否则属于不合法区间。

如果区间的中点值满足，那么更新，否则更新

基于此，我们可以观察到两个循环不变量都是非法的，都是合法的，而是待确定的，那么结束的时候也可以知道或者是答案

代码块

举一个例子，我们寻找有序数组中第一个大于等于 target 的位置¶

$ f(x) = \text{nums}[x] $ >= target¶

def lower_bound(nums, target): n = len(nums) l, r = 0, n-1 while l <= r: # 保证区间不为空 mid = (l + r) // 2 if nums[mid] >= target: r = mid-1 else: l = mid+1 return l

那么基于上述的闭区间的写法，我们可以推导得到等价的开区间写法和左闭右开区间写法对于开区间而言，我们的循环不变量就是都是非法的，都是合法的，那么其中的是不确定的

代码块 1 # 开区间写法 2 3 def lower_bound(nums, target): 4 n = len(nums) 5 l, r = -1, n # 注意这里 l, r 的取值范围, l = l-1, r = r+1 6 while l+1 < r: 7 mid = (l+r) // 2 8 if nums[mid] >= target: 9 r = mid 10 else: 11 l = mid 12 return r

对于左闭右开区间而言，循环不变量就变成了是非法的，都是合法的，那么其中的是不确定的

代码块 1 # 左闭右开写法 2 3 def lower_bound(nums, target): 4 n = len(nums) 5 l, r = 0, n 6 while l < r: 7 mid = (l + r) // 2 8 if nums[mid] >= target: 9 r = mid 10 else: 11 l = mid + 1 12 return l # l == r

滑动窗口算法与二分答案算法¶

题目：假设有一个长度为 $ \underline{\text{的非负整数的}} $数组，我们需要找到其中和不大于 $ \underline{\text{的最长子数组}} $的长度

上述题目是最经典的滑动窗口算法和二分答案算法的应用。先讲其中的二分答案算法

首先我们可以知道非负整数子数组的和总是越长和就越大，不会因为增加了长度反而和变小了。那么

假设我们找到了一个长度为 $ \underline{\text{的}} $子数组，我们是否可以找到一个大小介于 $ \underline{\text{的}} $子数组呢？显然可以，因为

我们只需要不断减少这个子数组的长度即可。因此我们可以知道这个答案是具有单调性质的，可以使用二分的方法加速寻找答案

使用了二分答案之后可以很明显感受到一点：这个最长的子数组是不是可以动态维护？比如说对于以结尾的子数组，我们知道了它的左边界最远为，那么对于以结尾的子数组，它的最远左边界能够是多少呢？因为刚才已经推导过了，对于长度越长的子数组，和会保持不减，所以其左边界最远就是，这可以使用反证法证明，这里就不啰嗦了。因此我们可以使用两个指针维护当前的最大子数组长度，也就是经典的双指针算法

代码块

双指针（滑动窗口）¶

2 3 def get_longgest_subarray(nums, sum): 4 n = len(nums) 5 l, s = 0, 0 6 ans = 0 7 for i in range(n): 8 s += nums[i] 9 while s > sum: 10 s -= nums[l] 11 l += 1 12 if i - l + 1 > ans: 13 ans = i - l + 1 14 return ans

二分答案经常用来解决一种答案具有单调性质的问题，而根据计算复杂度理论，检查是否成立比求解简单。而滑动窗口算法则是一种全局的优化，本质上是动态规划的思想。二分答案在面试算法题中是一种非常重要的算法。

回溯算法经典问题¶

回溯算法是一种通过穷举所有可能的解来求解问题的方法，广泛应用于各种经典的数学和计算机科学问题中。在面试中也是比较容易考察到的算法题目类型。而这种算法由于基于搜索，因此有很强的套路，需要熟练掌握。这类题目在思考的过程中可以遵循下面的思考步骤：

确定搜索的空间确定搜索的策略确定搜索的终止条件

枚举子集¶

定义：给定一个集合，求出其所有子集（或者统计其信息）

子集问题的核心在于每个元素都有两种状态：要么被选入当前子集，要么不被选入。因此，子集问题的规模为，即每个元素的选择组合

练习题目：电话号码的字母组合¶

分析一下题目，我们对于其中的每一个数字按键都有多种选择，形式上如果我们知道了按键长度，是可以使用迭代方法获取所有方案的，但是由于我们不知道按键的长度，这个时候就需要回溯算法来实现动态的搜索。

代码块 1 choice = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"] 2 class Solution: 4 def letterCombinations(self, digits: str) -> List[str]: 5 n = len(digits) 6 ans = [] 7 cur = [''] * n 8 if n == 0: 9 return ans 10 def dfs(i): 11 if i == n: # 确定好终止条件，这是很重要的，防止无限递归 12 ans.append(''.join(cur)) 13 return 14 for num in choice[int(digits[i])]: 15 cur[i] = num 16 dfs(i+1) 17 dfs(0) 18 return ans

练习题目：子集¶

对于每一个数字我们可以选或者不选，因为每一个元素都是不相同的，所以这保证了所有方案的独立性，不需要去重

代码块

1 class Solution: 2 def subsets(self, nums: List[int]) -> List[List[int]]: 3 n = len(nums) 4 ans = [] 5 cur = [] 6 def dfs(i): 7 if i == n: 8 ans.append(cur.copy()) 9 return 10 # 选择

cur.append(nums[i]) dfs(i+1)

回溯¶

cur.pop()

不选择¶

dfs(i+1) dfs(0) return ans

练习题目：分割回文串¶

回溯算法的思路是，对于每一个位置，我们尝试选择或者不选择，如果选择，那么判断是否为回文串，如果不是回文串，那么就直接剪枝

代码块

1 class Solution: 2 def partition(self, s: str) -> List[List[str]]: 3 n = len(s) 4 ans = [] 5 cur = [] 6 def dfs(i): 7 if i == n: 8 ans.append(cur.copy()) 9 return 10 for j in range(i,n): 11 t = s[i:j+1] 12 if t == t[:,-1]: # 判断回文串 13 cur.append(t)

解决组合问题¶

定义：从给定的元素中选取一定数量的元素，求出所有可能的组合。

组合问题的核心在于，每次选择时后面的元素不能再被重新选择，且每个组合的顺序不影响结果。这是区别于排列问题的最为关键的点。

练习题目： $ \underline{\text{组合}} $¶

这道题目就是最为经典的组合问题，我们需要在原有的子集问题基础上加多一个选择次数的限制，而利用这些限制，我们可以在原有的简单的搜索策略加上一些启发式的规则，统称为剪枝

代码块

1 class Solution:

def combine(self, n: int, k: int) -> List[List[int]]: ans = [] cur = [] def dfs(i): if len(cur) == k: ans.append(cur.copy()) return # 剪枝，[i,n] 还有 n-i+1个数字 if n-i+1 < k-len(cur): return for j in range(i,n+1): cur.append(j) dfs(j+1) cur.pop()

dfs(1) return ans

练习题目： $ \underline{\text{组合总和}} $¶

这道题目和练习题目1十分类似，但是多出了一个限制，那就是最后选择的元素和要等于一个制定的数字，那么我们就可以将这个限制放在搜索的策略中，并且制定对应的剪枝方法，从而实现高效的搜索

代码块

1 class Solution: 2 def combinationSum3(self, k: int, n: int) -> List[List[int]]: 3 ans = []

解决排列问题¶

定义：从给定的元素中选取一定数量的元素，使得元素间满足一定的顺序，求出所有可能的排列排列问题和组合问题的最大区别在于，排列问题需要考虑元素间的顺序，而组合问题只需要考虑元素是否被选择

练习题目1： $ \underline{\text{全排列}} $

代码块

1 class Solution: 2 def permute(self, nums: List[int]) -> List[List[int]]: 3 n = len(nums) 4 ans = [] 5 cur = [] 6 def dfs(s): 7 if s == 0:

8 ans.append(cur.copy()) 9 return 10 for j in range(n): 11 if s & (1<<j): 12 cur.append(nums[j]) 13 dfs(s ^ (1<<j)) 14 cur.pop() 15 dfs((1<<n)-1) 16 return ans

这里使用了二进制集合的方法表示了当前的选择的数字以及还没有选择的数字，比如数字 nums[i] 就对应了 s 中的第 i 位，0表示已经选择了，否则就表示还没有选择。

练习题目：N 皇后

此题的难点在于检查皇后是否处于同一行、同一列、同一对角线上。我们可以将对角线进行一个哈希编码，从而用于快速判断在某条对角线上是否存在皇后

代码块

1 class Solution: 2 def solveNQueens(self, n: int) -> List[List[str]]: 3 ans = [] 4 board = ["." * n for _ in range(n)] 5 if n == 0: 6 return ans 7 column = [False] * n 8 ldiag = [False] * (2 * n - 1) # 左对角线 9 rdiag = [False] * (2 * n - 1) # 右对角线 10 11 def backtrack(row): 12 if row == n: 13 ans.append(board.copy()) 14 return 15 for col in range(n): 16 # 计算左对角线和右对角线的索引 17 l_diag_index = row - col + (n - 1) 18 r_diag_index = row + col 19 # 检查当前位置是否被攻击 20 if column[col] or ldiag[l_diag_index] or rdiag[r_diag_index]: 21 continue 22 # 放置皇后 23 board[row] = board[row][:col] + 'Q' + board[row][col+1:] 24 column[col] = ldiag[l_diag_index] = rdiag[r_diag_index] = True 25 # 递归到下一行 26 backtrack(row + 1) 27 # 移除皇后（回溯）

board[row] = board[row][:col] + '.'.+ board[row][col+1:] column[col] = ldiag[l_diag_index] = rdiag[r_diag_index] = False backtrack(0)

动态规划经典问题¶

基础数据结构经典问题（链表、队列、栈）

字符串经典问题

基础图论问题

基础计算几何问题