1. 509. 斐波那契数（简单）
题目详情
斐波那契数（通常用 F(n) 表示）形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0，F(1) = 1；F(n) = F(n - 1) + F(n - 2)，其中 n > 1。给定 n ，请计算 F(n)。
示例
•示例 1：输入n = 2，输出1；解释：F(2) = F(1) + F(0) = 1 + 0 = 1
•示例 2：输入n = 3，输出2；解释：F(3) = F(2) + F(1) = 1 + 1 = 2
•示例 3：输入n = 4，输出3；解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示
0 <= n <= 30
核心解题思路
本题可采用递归或迭代解法，递归解法简洁但存在重复计算（时间复杂度O(2ⁿ)），面试中优先采用迭代解法（时间复杂度O(n)，空间复杂度O(1)）。通过两个变量交替更新，存储前两项的值，避免额外空间消耗，高效计算第n项斐波那契数。
Python面试手撕代码
class Solution(object): def fib(self, n): """ :type n: int :rtype: int """ # 迭代解法（面试最优，空间O(1)，时间O(n)） a, b = 0, 1 # 初始化F(0)=0，F(1)=1 for _ in range(n): # 循环n次，更新a和b的值 a, b = b, (a + b) # a变为前一项b，b变为前两项之和 return a # 循环结束后，a即为F(n)
2. LCR 136. 删除链表的节点（简单）
题目详情
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
示例
•示例 1：输入head = [4,5,1,9], val = 5，输出[4,1,9]；解释：删除值为5的节点后，链表变为4->1->9。
•示例 2：输入head = [4,5,1,9], val = 1，输出[4,5,9]；解释：删除值为1的节点后，链表变为4->5->9。
说明
题目保证链表中节点的值互不相同；若使用C或C++语言，不需要free或delete被删除的节点。
核心解题思路
采用「虚拟头节点」技巧（面试高频），避免处理头节点被删除的特殊情况。定义虚拟头节点dummy，使其next指向原头节点，再用prev（前驱节点）和cur（当前节点）双指针遍历链表，找到目标节点后，让前驱节点的next指向当前节点的next，即可完成删除，最后返回dummy.next。
Python面试手撕代码
# Definition for singly-linked list.# class ListNode(object):# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution(object): def deleteNode(self, head, val): """ :type head: Optional[ListNode] :type val: int :rtype: Optional[ListNode] """ # 虚拟头节点，避免头节点被删除的特殊情况 dummy = ListNode(-1) dummy.next = head prev = dummy # 前驱节点，初始指向虚拟头节点 cur = head # 当前节点，初始指向原头节点 while cur: if cur.val == val: # 找到目标节点，删除：前驱节点next指向当前节点next prev.next = cur.next cur = cur.next # 跳过被删除节点，继续遍历 else: # 未找到，双指针同步后移 prev = prev.next cur = cur.next # 返回删除后的链表头节点（虚拟头节点的next） return dummy.next
3. 442. 数组中重复的数据（中等）
题目详情
给你一个长度为n的整数数组nums，其中nums的所有整数都在范围[1, n]内，且每个整数出现最多两次。请你找出所有出现两次的整数，并以数组形式返回。要求设计并实现时间复杂度为O(n)且仅使用常量额外空间（不包括存储输出所需的空间）的算法。
示例
•示例 1：输入nums = [4,3,2,7,8,2,3,1]，输出[2,3]
•示例 2：输入nums = [1,1,2]，输出[1]
•示例 3：输入nums = [1]，输出[]
提示
•n == nums.length
•1 <= n <= 10⁵
•1 <= nums[i] <= n
•nums中的每个元素出现一次或两次
核心解题思路
利用「数组下标与元素值的对应关系」（元素范围[1,n]，下标范围[0,n-1]），通过正负标记法实现常量空间。遍历数组，对于每个元素num，取其绝对值作为下标index，若index对应的元素为正，说明首次遇到，将其置为负；若为负，说明已遇到过，即为重复元素，加入结果列表。
Python面试手撕代码
class Solution(object): def findDuplicates(self, nums): """ :type nums: List[int] :rtype: List[int] """ ans = [] # 存储重复元素的结果列表 for num in nums: num = abs(num) # 取绝对值，避免负号影响下标定位 # 以num-1为下标（因为元素范围1~n，下标0~n-1） if nums[num-1] > 0: # 首次遇到，标记为负 nums[num-1] = - nums[num-1] else: # 已标记过，说明重复，加入结果 ans.append(num) return ans
4. 74. 搜索二维矩阵（中等）
题目详情
给你一个满足下述两条属性的m x n整数矩阵：每行中的整数从左到右按非严格递增顺序排列；每行的第一个整数大于前一行的最后一个整数。给你一个整数target，如果target在矩阵中，返回true；否则，返回false。
示例
•示例 1：输入matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3，输出true
提示
•m == matrix.length
•n == matrix[i].length
•1 <= m, n <= 100
•-10⁴ <= matrix[i][j], target <= 10⁴
核心解题思路
利用矩阵的有序性，采用「右上角指针法」（面试高频），避免暴力遍历。初始指针指向矩阵右上角（row=0，col=n-1），若当前元素等于target，直接返回true；若当前元素大于target，向左移动指针（col--）；若当前元素小于target，向下移动指针（row++），直至指针越界，返回false。
Python面试手撕代码
class Solution(object): def searchMatrix(self, matrix, target): """ :type matrix: List[List[int]] :type target: int :rtype: bool """ m, n = len(matrix), len(matrix[0]) # m行n列 row, col = 0, n-1 # 初始指针：右上角 while row < m and col >= 0: # 指针未越界 if matrix[row][col] == target: # 找到目标值，返回true return True elif matrix[row][col] > target: # 当前值大于目标，向左移动 col -= 1 else: # 当前值小于目标，向下移动 row += 1 # 遍历结束未找到，返回false return False
5. 206. 反转链表（简单）
题目详情
给你单链表的头节点head，请你反转链表，并返回反转后的链表。
示例
•示例 1：输入head = [1,2,3,4,5]，输出[5,4,3,2,1]
•示例 2：输入head = [1,2]，输出[2,1]
•示例 3：输入head = []，输出[]
提示
•链表中节点的数目范围是[0, 5000]
•-5000 <= Node.val <= 5000
进阶
链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
核心解题思路
面试优先采用迭代解法（简洁易写，空间O(1)），通过prev（前驱节点）、head（当前节点）、nxt（后继节点）三个指针，逐个反转节点指向。初始prev为None，遍历链表时，先保存当前节点的后继节点，再将当前节点的next指向prev，最后更新prev和head，直至head为空，prev即为反转后的头节点。
Python面试手撕代码
# Definition for singly-linked list.# class ListNode(object):# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution(object): def reverseList(self, head): """ :type head: Optional[ListNode] :rtype: Optional[ListNode] """ prev = None # 前驱节点，初始为None（反转后尾节点指向None） while head: # 遍历链表，直至当前节点为空 nxt = head.next # 保存当前节点的后继节点，避免断链 head.next = prev # 反转当前节点指向，指向前驱节点 prev = head # 前驱节点后移，变为当前节点 head = nxt # 当前节点后移，变为之前保存的后继节点 return prev # 遍历结束，prev为反转后的头节点
6. 153. 寻找旋转排序数组中的最小值（中等）
题目详情
已知一个长度为n的数组，预先按照升序排列，经由1到n次旋转后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]旋转4次得到[4,5,6,7,0,1,2]，旋转7次得到原数组。给定一个元素值互不相同的数组nums，它原来是一个升序排列的数组，并进行了1至n次旋转，请找出并返回数组中的最小元素。要求设计时间复杂度为O(log n)的算法。
示例
•示例 1：输入nums = [3,4,5,1,2]，输出1；解释：原数组为[1,2,3,4,5]，旋转3次得到输入数组。
•示例 2：输入nums = [4,5,6,7,0,1,2]，输出0；解释：原数组为[0,1,2,4,5,6,7]，旋转4次得到输入数组。
•示例 3：输入nums = [11,13,15,17]，输出11；解释：原数组旋转4次得到输入数组（与原数组一致）。
提示
•n == nums.length
•1 <= n <= 5000
•-5000 <= nums[i] <= 5000
•nums中的所有整数互不相同
•nums原来是一个升序排序的数组，并进行了1至n次旋转
核心解题思路
利用数组旋转后的有序性，采用二分查找（O(log n)）。数组旋转后分为左右两个升序子数组，最小值是两个子数组的分界点。通过left和right双指针，计算mid = left + (right - left) // 2（避免溢出），若nums[mid] < nums[right]，说明最小值在左半部分（包括mid），令right=mid；否则最小值在右半部分（不包括mid），令left=mid+1，循环直至left>right，此时nums[right]即为最小值。
Python面试手撕代码
class Solution(object): def findMin(self, nums): """ :type nums: List[int] :rtype: int """ left, right = 0, len(nums)-1 # 二分查找双指针 while left <= right: # 计算mid，避免left+right溢出 mid = left + (right - left) // 2 if nums[mid] < nums[right]: # 最小值在左半部分（包括mid），收缩右边界 right = mid else: # 最小值在右半部分（不包括mid），收缩左边界 left = mid + 1 # 循环结束，right指向最小值 return nums[right]
7. 79. 单词搜索（中等）
题目详情
给定一个m x n二维字符网格board和一个字符串word。如果word存在于网格中，返回true；否则，返回false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例
示例 1：输入board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"，输出true
提示
•m == board.length
•n = board[i].length
•1 <= m, n <= 6
•1 <= word.length <= 15
•board和word仅由大小写英文字母组成
进阶
你可以使用搜索剪枝的技术来优化解决方案，使其在board更大的情况下可以更快解决问题？
核心解题思路
采用「深度优先搜索（DFS）+ 回溯」算法，结合剪枝优化。遍历网格的每个单元格，若当前单元格与word的第一个字符匹配，启动DFS；DFS中，标记当前单元格为已访问，再向上下左右四个方向递归搜索下一个字符，搜索结束后回溯（取消标记）；若递归索引等于word长度，说明找到完整单词，返回true；若所有路径均未找到，返回false。
Python面试手撕代码
class Solution: def exist(self, board: List[List[str]], word: str) -> bool: # DFS函数：i,j为当前网格坐标，index为当前匹配word的索引，visited标记已访问单元格 def dfs(i, j, index, visited): # 所有字符都匹配完成，返回true if index == len(word): return True # 边界判断：坐标越界、当前字符不匹配、已访问过，返回false if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[index] or visited[i][j]: return False visited[i][j] = True # 标记当前单元格为已访问 # 向上下左右四个方向递归搜索，只要有一个方向匹配成功，就返回true result = dfs(i+1, j, index+1, visited) or \ dfs(i-1, j, index+1, visited) or \ dfs(i, j-1, index+1, visited) or \ dfs(i, j+1, index+1, visited) visited[i][j] = False # 回溯：取消标记，供其他路径使用 return result m, n = len(board), len(board[0]) # 初始化访问标记矩阵，默认全为false visited = [[False] * n for _ in range(m)] # 遍历网格每个单元格，寻找匹配word首字符的起点 for i in range(m): for j in range(n): if dfs(i, j, 0, visited): return True # 所有起点都未找到匹配路径，返回false return False
8. 面试题 02.02. 返回倒数第 k 个节点（简单）
题目详情
实现一种算法，找出单向链表中倒数第k个节点。返回该节点的值。注意：本题相对原题稍作改动。
示例
输入：1->2->3->4->5 和 k = 2，输出：4
说明
给定的k保证是有效的。
核心解题思路
采用「双指针（快慢指针）」技巧（面试高频），无需遍历两次链表。让fast指针先前进k步，然后slow和fast指针同步前进，当fast指针到达链表末尾（为空）时，slow指针恰好指向倒数第k个节点，返回slow.val即可，时间复杂度O(n)，空间复杂度O(1)。
Python面试手撕代码
# Definition for singly-linked list.# class ListNode(object):# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclass Solution(object): def kthToLast(self, head, k): """ :type head: Optional[ListNode] :type k: int :rtype: int """ slow, fast = head, head # 快慢指针初始都指向头节点 # fast指针先前进k步，拉开与slow的距离 for _ in range(k): fast = fast.next # 快慢指针同步前进，直到fast到达末尾 while fast: slow = slow.next fast = fast.next # slow指针指向倒数第k个节点，返回其值 return slow.val
9. LCR 143. 子结构判断（中等）
题目详情
给定两棵二叉树tree1和tree2，判断tree2是否以tree1的某个节点为根的子树具有相同的结构和节点值。注意，空树不会是以tree1的某个节点为根的子树具有相同的结构和节点值。
示例
•示例 1：输入tree1 = [1,7,5], tree2 = [6,1]，输出false；解释：tree2与tree1的一个子树没有相同的结构和节点值。
•示例 2：输入tree1 = [3,6,7,1,8], tree2 = [6,1]，输出true；解释：tree2与tree1的一个子树拥有相同的结构和节点值（6->1）。
提示
0 <= 节点个数 <= 10000
核心解题思路
采用「递归」解法，分两步判断：1. 递归判断tree1的当前节点为根的子树，是否与tree2完全一致（用recur函数实现）；2. 若当前节点不一致，递归判断tree1的左子树和右子树，是否包含tree2作为子结构。recur函数中，若tree2为空，说明匹配完成；若tree1为空或节点值不相等，说明匹配失败；否则递归判断左右子节点是否一致。
Python面试手撕代码
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution(object): def isSubStructure(self, A, B): """ :type A: Optional[TreeNode] :type B: Optional[TreeNode] :rtype: bool """ # 辅助递归函数：判断以A为根的树是否与以B为根的树完全一致 def recur(A, B): if not B: # B为空，说明所有节点都匹配完成 return True if not A or A.val != B.val: # A为空或节点值不相等，匹配失败 return False # 递归判断左右子节点是否都匹配 return recur(A.left, B.left) and recur(A.right, B.right) # 边界判断：A或B为空，直接返回false（空树不能作为子结构） # 递归判断：A当前节点匹配 / A左子树匹配 / A右子树匹配 return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))
10. LCR 152. 验证二叉搜索树的后序遍历序列（中等）
题目详情
请实现一个函数来判断整数数组postorder是否为二叉搜索树的后序遍历结果。
示例
•示例 1：输入postorder = [4,9,6,5,8]，输出false；解释：无法构建二叉搜索树。
•示例 2：输入postorder = [4,6,5,9,8]，输出true；解释：可构建符合要求的二叉搜索树。
提示
•数组长度 <= 1000
•postorder中无重复数字
核心解题思路
二叉搜索树后序遍历的特性：序列最后一个元素是根节点；左子树所有元素都小于根节点，右子树所有元素都大于根节点；左、右子树也满足二叉搜索树的后序遍历规则。采用递归解法，找到左子树和右子树的分界点，判断右子树是否存在小于根节点的元素（若存在则无效），再递归验证左、右子树。
Python面试手撕代码
class Solution(object): def verifyTreeOrder(self, postorder): """ :type postorder: List[int] :rtype: bool """ # 递归函数：验证postorder[left..right]是否为二叉搜索树的后序遍历 def dfs(nums, left, right): if left >= right: # 单个节点或空，返回true return True post_root = nums[right] # 后序遍历的根节点是最后一个元素 post_left = left # 左子树的起始索引 # 找到左子树的分界点：所有小于根节点的元素都是左子树 while nums[post_left] < post_root: post_left += 1 cur_index = post_left # 验证右子树：所有元素都应大于根节点，若有小于的则无效 while cur_index < right: cur_index += 1 if nums[cur_index] < post_root: return False # 递归验证左子树（left..post_left-1）和右子树（post_left..right-1） return dfs(nums, left, post_left-1) and dfs(nums, post_left, right-1) # 整体验证整个数组 return dfs(postorder, 0, len(postorder)-1)
11. 面试题 17.14. 最小K个数（中等）
题目详情
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例
输入：arr = [1,3,5,7,2,4,6,8], k = 4，输出：[1,2,3,4]（任意顺序均可）
提示
•0 <= len(arr) <= 100000
•0 <= k <= min(100000, len(arr))
核心解题思路
采用「快速排序分区」思路（面试高频，时间复杂度O(n)），优于直接排序（O(n log n)）。通过随机选择基准值（避免极端情况），将数组分区，若分区后的基准值索引等于k，说明基准值左侧的k个元素即为最小k个数；若基准值索引小于k，继续在右侧分区；若大于k，继续在左侧分区，直至找到索引为k的基准值，返回左侧k个元素。
Python面试手撕代码
class Solution(object): def smallestK(self, arr, k): """ :type arr: List[int] :type k: int :rtype: List[int] """ # 分区函数：将数组nums[left..right]分区，返回基准值的最终索引 def partition(nums, left, right): # 随机选择基准值，避免极端情况（如数组已排序） idx = random.randint(left, right) nums[idx], nums[left] = nums[left], nums[idx] pivot = nums[left] # 基准值 while left < right: # 从右向左找小于基准值的元素，放到左指针位置 while left < right and nums[right] >= pivot: right -= 1 nums[left] = nums[right] # 从左向右找大于基准值的元素，放到右指针位置 while left < right and nums[left] <= pivot: left += 1 nums[right] = nums[left] nums[left] = pivot # 基准值放到最终位置 return left left, right = 0, len(arr)-1 while left <= right: mid = partition(arr, left, right) if mid == k: # 基准值索引为k，左侧k个元素即为最小k个数 return arr[:k] elif mid < k: # 基准值索引小于k，最小k个数在右侧 left = mid + 1 else: # 基准值索引大于k，最小k个数在左侧 right = mid - 1 # k=0或数组为空时，返回空列表 return []
例题来自力扣网https://leetcode-cn.com/
