企业官网建设流程全解析

颜色分类

1. 题目回顾

• 问题描述：给定一个包含红色、白色和蓝色，一共 nn 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色的顺序排列。
• 数值映射：使用整数0、1和2分别代表红色、白色和蓝色。
• 约束条件：必须在不使用代码库自带的排序函数的情况下解决，且要求原地排序。进阶挑战是设计一个仅使用常数空间的一趟扫描算法。
• 示例：
  • 输入：[2,0,2,1,1,0]→→ 输出：[0,0,1,1,2,2]

2. 核心思路：线性扫描与模拟归并

虽然题目名为“颜色分类”，本质上是一个三路划分（3-way Partition）问题。我们可以借鉴快速排序中“分区”的思想，通过线性扫描将数组划分为三个区域。

• 区域定义：我们将数组想象成被两个边界线切分成了三段：
  1. 左区（已处理）：全为0。
  2. 中区（已处理）：全为1。
  3. 右区（已处理）：全为2。
  4. 未处理区：夹在中区和右区之间，是当前扫描指针正在探索的区域。
• 策略：维护三个指针，随着扫描的进行，不断压缩“未处理区”，直到其消失，从而实现类似归并排序中将不同元素归类到对应区间的效果。

3. 算法详细步骤

3.1 递归终止条件（边界处理）

虽然本题最优解通常采用迭代（循环）方式，但在算法逻辑上，“终止条件”定义了问题的结束状态和初始边界：

• 无效输入处理：如果数组为空或长度小于 2，直接返回，无需处理。
• 循环终止判定：我们设定一个当前遍历指针curr和一个右边界指针p2。当curr > p2时，意味着“未处理区”已经消失，所有元素都已归位，算法终止。
• 初始边界设定：
  • p0 = 0：指向下一个0应该放置的位置（即左区的右边界）。
  • p2 = n - 1：指向下一个2应该放置的位置（即右区的左边界）。
  • curr = 0：当前正在检查的元素索引。

3.2 分解过程：双指针移动

这里实际上是三指针协同工作的过程。我们需要根据nums[curr]的值，决定如何移动指针来分解数组：

1. 遇到0（归入左区）：

   • 将nums[curr]与nums[p0]交换。
   • 移动：p0向右移一位（扩大 0 的区域），curr向右移一位（继续检查下一个）。
   • 注：交换回来的必然是 1，所以 curr 可以安全前进。

2. 遇到2（归入右区）：

   • 将nums[curr]与nums[p2]交换。
   • 移动：p2向左移一位（扩大 2 的区域）。
   • 关键点：curr不动！因为从后面换过来的元素可能是 0，需要再次检查。

3. 遇到1（归入中区）：

   • 移动：仅需curr向右移一位。1 自然留在了中间区域。

3.3 解决过程：值的捕获

这一步描述了算法如何通过“捕获”特定值来推进排序进度：

• 捕获0：当我们捕获到0时，实际上是将它从“混乱的未处理区”扔到了“有序的左区”。通过与p0交换，我们确保了p0左侧全是 0。
• 捕获2：当我们捕获到2时，将其扔到“有序的右区”。通过与p2交换，我们确保了p2右侧全是 2。
• 忽略1：1是最安全的元素。只要 0 都在左边，2 都在右边，剩下的中间位置自然就是 1。因此，遇到 1 不需要交换操作，直接“放过”即可。

3.4 合并过程：结果计算

这里的“合并”并非指数组拼接，而是指状态的收敛：

• 区间闭合：随着curr的不断右移和p2的不断左移，未处理区间[curr, p2]逐渐缩小。
• 最终状态：当curr越过p2时，三个区间完美拼接：[0...p0-1]+[p0...p2](此时为空) +[p2+1...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 列的值。
• 状态转移方程：
  • 当 j=0j=0 或 j=ij=i 时（即行首和行尾）：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。这避免了在计算第一行（i=0）时去访问不存在的上一行（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 List<List<Integer>> generate(int numRows) { // 3.1 边界处理：初始化结果集 List<List<Integer>> res = new ArrayList<List<Integer>>(); // 3.2 分解过程：逐行生成 for (int i = 0; i < numRows; i++) { List<Integer> temp = new ArrayList<Integer>(); // 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 行有 i+1 个元素。总的元素个数是 1+2+⋯+numRows=numRows(numRows+1)2​ 。每个元素的计算是 O(1)的，因此总时间复杂度为 O(numRows2) 。
• 空间复杂度：O(numRows2)
  • 我们需要使用一个二维列表res来存储整个杨辉三角的所有元素，占用的空间与元素总数成正