颜色分类1. 题目回顾问题描述给定一个包含红色、白色和蓝色一共 nn 个元素的数组原地对它们进行排序使得相同颜色的元素相邻并按照红色、白色、蓝色的顺序排列。数值映射使用整数0、1和2分别代表红色、白色和蓝色。约束条件必须在不使用代码库自带的排序函数的情况下解决且要求原地排序。进阶挑战是设计一个仅使用常数空间的一趟扫描算法。示例输入[2,0,2,1,1,0]→→ 输出[0,0,1,1,2,2]2. 核心思路线性扫描与模拟归并虽然题目名为“颜色分类”本质上是一个三路划分3-way Partition问题。我们可以借鉴快速排序中“分区”的思想通过线性扫描将数组划分为三个区域。区域定义我们将数组想象成被两个边界线切分成了三段左区已处理全为0。中区已处理全为1。右区已处理全为2。未处理区夹在中区和右区之间是当前扫描指针正在探索的区域。策略维护三个指针随着扫描的进行不断压缩“未处理区”直到其消失从而实现类似归并排序中将不同元素归类到对应区间的效果。3. 算法详细步骤3.1 递归终止条件边界处理虽然本题最优解通常采用迭代循环方式但在算法逻辑上“终止条件”定义了问题的结束状态和初始边界无效输入处理如果数组为空或长度小于 2直接返回无需处理。循环终止判定我们设定一个当前遍历指针curr和一个右边界指针p2。当curr p2时意味着“未处理区”已经消失所有元素都已归位算法终止。初始边界设定p0 0指向下一个0应该放置的位置即左区的右边界。p2 n - 1指向下一个2应该放置的位置即右区的左边界。curr 0当前正在检查的元素索引。3.2 分解过程双指针移动这里实际上是三指针协同工作的过程。我们需要根据nums[curr]的值决定如何移动指针来分解数组遇到0归入左区将nums[curr]与nums[p0]交换。移动p0向右移一位扩大 0 的区域curr向右移一位继续检查下一个。注交换回来的必然是 1所以 curr 可以安全前进。遇到2归入右区将nums[curr]与nums[p2]交换。移动p2向左移一位扩大 2 的区域。关键点curr不动因为从后面换过来的元素可能是 0需要再次检查。遇到1归入中区移动仅需curr向右移一位。1 自然留在了中间区域。3.3 解决过程值的捕获这一步描述了算法如何通过“捕获”特定值来推进排序进度捕获0当我们捕获到0时实际上是将它从“混乱的未处理区”扔到了“有序的左区”。通过与p0交换我们确保了p0左侧全是 0。捕获2当我们捕获到2时将其扔到“有序的右区”。通过与p2交换我们确保了p2右侧全是 2。忽略11是最安全的元素。只要 0 都在左边2 都在右边剩下的中间位置自然就是 1。因此遇到 1 不需要交换操作直接“放过”即可。3.4 合并过程结果计算这里的“合并”并非指数组拼接而是指状态的收敛区间闭合随着curr的不断右移和p2的不断左移未处理区间[curr, p2]逐渐缩小。最终状态当curr越过p2时三个区间完美拼接[0...p0-1][p0...p2](此时为空) [p21...n-1]。结果产出此时原数组nums已经被修改为有序状态无需额外的返回值或新数组原地修改即为最终结果。4. 代码实现class Solution { public void sortColors(int[] nums) { // 3.1 边界处理 if (nums null || nums.length 1) return; int p0 0; // 指向0的右边界 int curr 0; // 当前遍历指针 int p2 nums.length - 1; // 指向2的左边界 // 3.2 3.4 循环直到未知区域为空 while (curr p2) { if (nums[curr] 0) { // 3.3 捕获0交换到左边 swap(nums, curr, p0); p0; curr; // 换过来的一定是1可以直接走 } else if (nums[curr] 2) { // 3.3 捕获2交换到右边 swap(nums, curr, p2); p2--; // 注意curr不动因为换过来的数还需要检查 } else { // 遇到1直接放过 curr; } } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } }5. 复杂度分析时间复杂度O(n) 。算法只进行了一次线性扫描curr指针从 0 移动到 n 每个元素最多被访问和交换常数次。空间复杂度O(1) 。我们只使用了p0,curr,p2三个指针变量没有使用任何额外的数组或递归栈空间完全符合原地排序的要求。杨辉三角1. 题目回顾问题描述给定一个非负整数numRows生成杨辉三角的前numRows行。核心规律除了每行的首尾元素为 1 之外其余每个元素都等于它左上方和右上方的元素之和。示例输入numRows 5输出text[1] [1,1] [1,2,1] [1,3,3,1] [1,4,6,4,1]2. 核心思路动态规划与状态转移既然杨辉三角的每个元素都依赖于它上一行的相邻元素这天然就是一个动态规划问题。状态定义我们将整个杨辉三角看作一个二维状态表res。res.get(i).get(j)表示第 ii 行、第 jj 列的值。状态转移方程当 j0j0 或 jiji 时即行首和行尾res[i][j] 1其他情况res[i][j] res[i-1][j-1] res[i-1][j]3. 算法详细步骤3.1 递归终止条件边界处理在动态规划中边界处理决定了状态转移能否安全进行外层循环边界如果numRows 0则无需生成直接返回空列表。内层循环边界行首与行尾在计算每一行的元素时当列索引j 0或j i时直接赋值为1。这避免了在计算第一行i0时去访问不存在的上一行i-1 -1而导致的数组越界异常。3.2 分解过程逐行生成我们将生成整个三角的大问题分解为生成 nn 个独立行的子问题外层循环遍历行数i从0到numRows - 1。行长度确定根据杨辉三角的规律第i行恰好有i 1个元素。因此内层循环的列索引j从0遍历到i包含i。3.3 解决过程值的捕获状态转移这一步是算法的核心即如何获取当前元素的值捕获首尾值如果j 0 || j i直接temp.add(1)。捕获中间值如果处于中间位置则严格按照状态转移方程从结果集res中获取上一行i-1的两个相邻元素左上方元素res.get(i-1).get(j-1)右上方元素res.get(i-1).get(j)将两者相加后加入当前行的临时列表temp中。3.4 合并过程结果计算这里的“合并”指的是将每一行独立计算出的结果拼接到最终的全局结果集中行入列当内层循环结束当前行temp的所有元素都已计算完毕。此时执行res.add(temp)将这一行追加到结果集中。最终态当外层循环结束时res中已经按顺序包含了从第 0 行到第numRows - 1行的所有数据直接返回res即可。4. 代码实现class Solution { public ListListInteger generate(int numRows) { // 3.1 边界处理初始化结果集 ListListInteger res new ArrayListListInteger(); // 3.2 分解过程逐行生成 for (int i 0; i numRows; i) { ListInteger temp new ArrayListInteger(); // 3.3 解决过程计算当前行的每个元素 for (int j 0; j i; j) { if (j 0 || j i) { // 边界条件行首和行尾必定为 1 temp.add(1); } else { // 状态转移等于上一行相邻两数之和 temp.add(res.get(i - 1).get(j - 1) res.get(i - 1).get(j)); } } // 3.4 合并过程将当前行加入总结果集 res.add(temp); } return res; } }5. 复杂度分析时间复杂度O(numRows2)我们需要生成 numRows 行第 i 行有 i1 个元素。总的元素个数是 12⋯numRowsnumRows(numRows1)2​ 。每个元素的计算是 O(1)的因此总时间复杂度为 O(numRows2) 。空间复杂度O(numRows2)我们需要使用一个二维列表res来存储整个杨辉三角的所有元素占用的空间与元素总数成正