企业官网建设流程全解析

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

③考点

字典序

字典序就是：像查字典一样，从左到右逐个比较。比较两个序列时：

1. 先比较第一个元素；
2. 如果相同，再比较第二个；
3. 一直比较到出现第一个不同的元素；
4. 在这个位置，元素更小的序列字典序更小。

代码核心思路

核心目标是：

在所有比当前数组大的排列中，找到最小的那个排列。

也就是让数组“刚好变大一点”，而不是变大很多。

代码思路可以概括为四步：

从右找转折点 → 从右找替换值 → 交换 → 反转后半部分

第一步：从右向左寻找第一个可以变大的位置

第二步：从右向左找一个刚好比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。

所以我们需要进行两次二分查找：

1. 第一次寻找target的最左位置。
2. 第二次寻找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 的元素 ↑ left

36.有效的数独

①题目

②答案

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(reverse=True)

知识点

复杂度