二刷 LeetCode：75. 颜色分类 31. 下一个排列 复盘笔记

目录一、75. 颜色分类荷兰国旗问题题目回顾思路复盘核心思想Python 代码实现易错点 二刷心得二、31. 下一个排列题目回顾思路复盘核心步骤Python 代码实现易错点 二刷心得三、两道题的共性总结 二刷收获这两道题是数组 / 排序专题的经典中等题也是面试中常考的 “原地操作” 类型非常适合用来巩固双指针和贪心思想。二刷时我们重点拆解核心思路、优化写法并总结通用解题模板。一、75. 颜色分类荷兰国旗问题题目回顾给定一个包含红色、白色和蓝色、共n个元素的数组nums原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色顺序排列。我们使用整数0、1和2分别表示红色、白色和蓝色。思路复盘这道题的最优解是三指针法荷兰国旗问题时间复杂度 \(O(n)\)空间复杂度 \(O(1)\)一次遍历完成排序。核心思想定义三个指针p0指向 0 的右边界初始为 0p2指向 2 的左边界初始为len(nums)-1curr当前遍历的元素指针初始为 0遍历规则当nums[curr] 0和nums[p0]交换p0、curr当nums[curr] 2和nums[p2]交换p2--注意curr不增加因为交换来的元素需要再判断当nums[curr] 1直接currPython 代码实现python运行def sortColors(nums: list[int]) - None: p0 curr 0 p2 len(nums) - 1 while curr p2: if nums[curr] 0: nums[p0], nums[curr] nums[curr], nums[p0] p0 1 curr 1 elif nums[curr] 2: nums[curr], nums[p2] nums[p2], nums[curr] p2 - 1 else: curr 1易错点 二刷心得边界控制循环条件必须是curr p2因为p2左边的元素还未处理完。交换 2 时的指针处理交换curr和p2后curr不能自增因为新交换来的元素可能是 0 或 2需要再次判断。原地修改题目要求不使用额外空间所以不能用计数排序后再重写数组三指针法是最优解。二、31. 下一个排列题目回顾实现获取下一个排列的函数算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列则将数字重新排列成最小的排列即升序排列。必须原地修改只允许使用额外常数空间。思路复盘这道题的核心是贪心思想找到 “下一个更大” 的排列关键步骤可以总结为 “找、换、反转” 三步。核心步骤找从后往前找第一个nums[i] nums[i1]的位置i这个位置是 “下降点”后面的元素是降序的。换从后往前找第一个比nums[i]大的元素nums[j]交换nums[i]和nums[j]。反转将i之后的元素反转使其变为升序这样得到的就是比原排列大的最小排列。Python 代码实现python运行def nextPermutation(nums: list[int]) - None: n len(nums) # 步骤1找下降点 i n - 2 while i 0 and nums[i] nums[i1]: i - 1 # 步骤2如果不是最后一个排列找比nums[i]大的最小数并交换 if i 0: j n - 1 while nums[j] nums[i]: j - 1 nums[i], nums[j] nums[j], nums[i] # 步骤3反转i之后的部分 left, right i 1, n - 1 while left right: nums[left], nums[right] nums[right], nums[left] left 1 right - 1易错点 二刷心得下降点的理解如果整个数组是降序的说明没有下一个排列直接反转整个数组即可。交换后反转的必要性交换nums[i]和nums[j]后i之后的部分仍然是降序的反转后才能变成升序得到最小的更大排列。边界处理当i 0时说明数组是降序的直接反转整个数组即可无需额外处理。三、两道题的共性总结 二刷收获原地操作的核心思想两道题都要求在不使用额外空间的情况下修改数组核心都是通过双指针 / 多指针实现元素的交换和重排。贪心算法的应用颜色分类通过指针划分区域一次遍历完成分类局部最优每次把元素放到正确位置得到全局最优。下一个排列通过 “找下降点、交换、反转” 三步找到字典序下的最小更大排列同样是贪心思想的体现。面试高频考点颜色分类重点考察三指针法和荷兰国旗问题是多指针思想的经典应用。下一个排列重点考察对排列字典序的理解和原地修改的技巧面试中常被追问时间复杂度和空间复杂度优化。