31.下一个排列①题目题目目的使用原来的这些数字找到一个刚好比当前排列大的排列。题目要求②答案class Solution(object): def nextPermutation(self, nums): :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. n len(nums) # 第一步从右向左寻找第一个 nums[i] nums[i 1] 的位置 i n - 2 #让 i 从倒数第二个元素开始 while i 0 and nums[i] nums[i 1]: i - 1 #让 i 向左移动一个位置 # 如果找到了可以变大的位置 if i 0: # 第二步从右向左寻找第一个大于 nums[i] 的数字 j n - 1 while nums[j] nums[i]: j - 1 # 第三步交换 nums[i] 和 nums[j] nums[i], nums[j] nums[j], nums[i] # 第四步反转 i 后面的部分 left i 1 right n - 1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1③考点字典序字典序就是像查字典一样从左到右逐个比较。比较两个序列时先比较第一个元素如果相同再比较第二个一直比较到出现第一个不同的元素在这个位置元素更小的序列字典序更小。代码核心思路核心目标是在所有比当前数组大的排列中找到最小的那个排列。也就是让数组“刚好变大一点”而不是变大很多。代码思路可以概括为四步从右找转折点 → 从右找替换值 → 交换 → 反转后半部分第一步从右向左寻找第一个可以变大的位置第二步从右向左找一个刚好比nums[i]大的数字第三步交换nums[i]和nums[j]第四步反转i后面的部分32.困难最长的有效括号33.搜索螺旋排序数组①题目②答案class Solution(object): def search(self, nums, target): :type nums: List[int] :type target: int :rtype: int left 0 right len(nums) - 1 while left right: mid (left right) // 2 # 找到目标值 if nums[mid] target: return mid # 左半部分有序 if nums[left] nums[mid]: # target 在左半部分的有序区间中 if nums[left] target nums[mid]: right mid - 1 else: left mid 1 # 否则右半部分有序 else: # target 在右半部分的有序区间中 if nums[mid] target nums[right]: left mid 1 else: right mid - 1 return -1③考点为什么不能直接遍历最简单的方法是for i in range(len(nums)): if nums[i] target: return i但是这种方法的时间复杂度是O(n)题目明确要求O(log n)因此必须使用二分查找。34.在排序数组中查找元素的第一个和最后一个位置①题目②答案class Solution(object): def searchRange(self, nums, target): :type nums: List[int] :type target: int :rtype: List[int] # 查找 target 第一次出现的位置 def findLeft(): left 0 right len(nums) - 1 result -1 while left right: mid (left right) // 2 if nums[mid] target: result mid # 找到了以后继续向左寻找 right mid - 1 elif nums[mid] target: left mid 1 else: right mid - 1 return result # 查找 target 最后一次出现的位置 def findRight(): left 0 right len(nums) - 1 result -1 while left right: mid (left right) // 2 if nums[mid] target: result mid # 找到了以后继续向右寻找 left mid 1 elif nums[mid] target: left mid 1 else: right mid - 1 return result # 必须和 findLeft、findRight 函数定义保持同一级缩进 return [findLeft(), findRight()]③考点题目要求时间复杂度必须是O(log n)因此不能从头到尾遍历数组而要使用二分查找。普通二分查找不够普通二分查找只能保证找到某一个target但不一定找到第一个或最后一个。例如nums [5, 7, 7, 8, 8, 10]普通二分查找可能找到下标3也可能找到下标4。所以我们需要进行两次二分查找第一次寻找target的最左位置。第二次寻找target的最右位置35.搜索插入位置①题目②答案class Solution(object): def searchInsert(self, nums, target): :type nums: List[int] :type target: int :rtype: int left 0 right len(nums) - 1 while left right: mid (left right) // 2 if nums[mid] target: return mid elif nums[mid] target: left mid 1 else: right mid - 1 return left③考点二分查找为什么最后返回left这是这道题最重要的地方。当循环结束时一定有left right此时right指向最后一个小于target的位置left指向第一个大于target的位置因此left正是target应该插入的位置。也可以理解为小于 target 的元素 | target 应插入的位置 | 大于 target 的元素 ↑ left36.有效的数独①题目②答案class Solution(object): def isValidSudoku(self, board): :type board: List[List[str]] :rtype: bool # rows[i] 记录第 i 行出现过的数字 rows [set() for _ in range(9)] # cols[j] 记录第 j 列出现过的数字 cols [set() for _ in range(9)] # boxes[k] 记录第 k 个 3×3 宫格出现过的数字 boxes [set() for _ in range(9)] # 遍历 9 行 for i in range(9): # 遍历每一行的 9 列 for j in range(9): num board[i][j] # 空格不需要检查 if num .: continue # 计算当前位置属于哪个 3×3 宫格 box_index (i // 3) * 3 j // 3 # 只要行、列、宫格中有一个已经存在该数字就无效 if (num in rows[i] or num in cols[j] or num in boxes[box_index]): #if 条件换行时Python 编译器不知道条件是否结束,所以需要在整个 if 条件的外面包裹一层小括号 ()。 return False # 当前数字没有重复将它记录下来 rows[i].add(num) cols[j].add(num) boxes[box_index].add(num) # 所有位置都检查完没有发现重复 return True③考点set()set天生就是为“快速判断元素是否存在”设计的所以比用列表更符合题意。continue跳过当前这一轮循环直接进入下一轮循环break彻底终止整个循环。一旦遇到break整个循环直接结束后面的所有轮次都不执行37.困难解数独38.外观数列①题目②答案class Solution(object): def countAndSay(self, n): :type n: int :rtype: str # 第一项固定是 1 s 1 # 已经有了第 1 项因此只需要再生成 n - 1 次 for _ in range(n - 1): next_s [] count 1 # 从第二个字符开始与前一个字符比较 for i in range(1, len(s)): if s[i] s[i - 1]: # 和前一个字符相同连续数量加一 count 1 else: # 和前一个字符不同说明上一组连续字符结束 next_s.append(str(count)) next_s.append(s[i - 1]) # 开始统计新的一组字符 count 1 # 循环结束后最后一组字符还没有加入结果 next_s.append(str(count)) next_s.append(s[-1]) # 列表拼接成字符串作为下一轮的输入 s .join(next_s) return s③考点1.在代码中需要维护count当前字符连续出现了多少次next_s用来保存生成的下一项2.当s 1时字符串的长度len(s)等于 1。因此循环语句for i in range(1, len(s)):实际上变成了for i in range(1, 1):。在 Python 中range(1, 1)是一个空序列所以i不会取到任何值整个for循环体被完全跳过。3.s[-1]就是字符串1的最后一个字符也就是1本身4.append是“打包塞进去”extend是“拆开铺进去”。39.组合总和①题目②答案class Solution(object): def combinationSum(self, candidates, target): :type candidates: List[int] :type target: int :rtype: List[List[int]] result [] #保存所有符合要求的组合 path [] #表示当前正在尝试的组合 # 排序后可以进行剪枝 candidates.sort() #start 表示这次可以从 candidates 的哪个位置开始选择 #remain 表示距离目标值还差多少 def backtrack(start, remain): # 剩余值恰好为 0说明当前组合满足要求 if remain 0: result.append(path[:]) #path[:] 会复制一份当前列表将独立的列表保存到 result 中。 return for i in range(start, len(candidates)): num candidates[i] # 因为已经排序当前数字大于 remain # 后面的数字只会更大可以直接结束循环 if num remain: break # 选择当前数字 path.append(num) # i 不加 1表示当前数字还可以继续重复使用 backtrack(i, remain - num) # 撤销选择尝试下一个数字 path.pop() backtrack(0, target) return result③考点回溯法“剪枝”Pruning是计算机科学特别是算法和人工智能中的一个核心优化策略。它的核心思想非常直白在搜索或遍历的过程中通过某些规则提前判断出某些分支不可能产生最优解或有效解从而直接放弃“剪掉”这些分支不再继续往下搜索。1. 为什么不能直接result.append(path)在 Python 中当你执行result.append(path)时你并没有把path里的数据复制一份放进result你只是把path这个变量的内存地址引用放进了result中。回溯算法的核心在于“状态重置”。当我们在一条分支上找到答案后会通过path.pop()撤销刚才的选择退回到上一步继续寻找下一个答案。如果你直接append(path)由于result和path指向的是内存中的同一个列表后续所有的pop()操作都会把result里刚刚存进去的数据给“掏空”。最终你的result里会装满空列表[]。2.path[:]做了什么path[:]是 Python 中的切片操作它的完整写法相当于path[0:len(path)]。这个操作会在内存中创建一个全新的列表把path当前时刻的所有元素复制过去。当你执行result.append(path[:])时你存入result的是一个独立的快照副本。无论后续path怎么pop()、怎么变化这个已经存入result的副本都不会受到任何影响。path.append(num)的目的是“推进状态”在回溯的探索过程中我们需要不断地往当前路径中添加新的元素以便进入下一层递归。我们确实需要修改path这个列表本身。append正是用来修改原列表的方法。result.append(path[:])的目的是“保存快照”当我们找到一条完整的路径时我们需要把它存起来。此时我们绝对不能修改path而是需要把path当前的状态复制一份存进result。所以这里用path[:]来创建副本。break的作用是提前结束整个for循环不再尝试当前层级的后续数字。continue的作用是跳过当前这一轮的循环直接进入下一轮循环。40.组合总和Ⅱ①题目②答案class Solution(object): def combinationSum2(self, candidates, target): :type candidates: List[int] :type target: int :rtype: List[List[int]] # 先排序方便去重和剪枝 candidates.sort() res [] path [] def backtrack(start, remain): # remain 等于 0说明 path 中的数字之和正好等于 target if remain 0: res.append(path[:]) return # 从 start 开始选择数字 for i in range(start, len(candidates)): # 当前层中跳过重复数字 if i start and candidates[i] candidates[i - 1]: continue # 当前数字已经大于剩余目标值 # 后面的数字更大不需要继续尝试 if candidates[i] remain: break # 选择 candidates[i] path.append(candidates[i]) # i 1 表示当前元素不能再次使用 backtrack(i 1, remain - candidates[i]) # 撤销刚才的选择 path.pop() backtrack(0, target) return res③考点排序 回溯回溯的过程可以理解为依次尝试选择一个数字如果选择后还没有达到目标值就继续向后选择尝试完成后撤销这次选择再尝试其他数字。candidates.sort()默认是从小到大升序排列的如果想从大到小降序排列candidates.sort(reverseTrue)知识点复杂度