企业官网建设流程全解析

1. 先搞清楚这道题到底在问什么

1.1 丑数的定义：先说清楚什么是“丑”

丑数这道题，我第一次在刷题平台上看到的时候差点直接跳过，名字实在太劝退了。但真正碰过之后我改变看法——这是一道把动态规划核心思想浓缩得很干净的题，尤其适合用“先暴力、再优化、最后上 DP”的节奏来理解。

定义先背清楚：丑数是指只包含质因数 2、3、5 的正整数。质因数就是能整除这个数的质数，比如 10 的质因数是 2 和 5，14 的质因数是 2 和 7。按这个定义，6、8、10、12 都是丑数，因为它们质因数全在 {2, 3, 5} 里；14、21、42 不是，因为混入了 7。这里有个经常让人困惑的特例：数字 1 被约定为第一个丑数。为什么？因为它没有任何质因数，空集算作子集，数学上约定俗成，题目也明确规定了，记下来就行，后面所有推导都建立在这条约定上。

这个定义看起来简单，但两道题目从这里开始分岔。第一道题是“给你一个整数，判断它是不是丑数”，属于一次性的判断问题；第二道题是“按从小到大顺序，求出第 n 个丑数”，属于生成序列的问题。两者难度完全不同，动态规划的主角是第二道，但第一道是必要的前置理解，把判断逻辑吃透了，第二道题里的核心思想才顺理成章。

1.2 一个系列，两问：判断与生成

先说第一问，它真的有手就行。给一个整数 n，不断尝试让它被 2、3、5 整除，能整除就除，除到不能除为止，最后看剩下的是不是 1。如果是 1，说明它只剩下质因数 2、3、5，是丑数；如果不是 1，说明它含有其它质因子，不是丑数。逻辑一句话就能讲清楚，代码也是几行。

但第二问就有点东西了。如果给你一个 n=10，让你手工写一下前 10 个丑数，你会这么想：从 1 开始逐个整数判断，1 是，2 是，3 是，4 是，5 是，6 是，7 不是，8 是，9 是，10 是，第 10 个是 12（按题目序列，前 10 个丑数是 1、2、3、4、5、6、8、9、10、12）。这个方法对 n=10 没问题，但题目要的可能 n=1690，这时问题来了：暴力遍历的终止条件是什么？你不知道第 1690 个丑数大概落在多大的整数范围内，只能一边数一边往后扫。最坏情况很恐怖——丑数出现的密度随数值增大越来越低，扫到几亿、几十亿都可能。

这里隐藏着一个关键点：判断一个数是不是丑数很容易，但要在整数范围内按顺序挑出第 n 个丑数，暴力法的效率完全不可控。于是你需要换一个思路——不遍历整数，而是根据丑数的定义直接“生成”丑数。这就是动态规划的切入点。

1.3 为什么这个系列值得认真做

我后来带过几个刚入门刷题的同学，发现一个普遍现象：大家看到“动态规划”四个字就发怵，下意识觉得要建复杂的状态转移方程、要画出二维表格。但丑数 II 是一道非常温柔的 DP 入门题，它不需要你定义什么 dp[i] 代表“前 i 个物品的最大价值”，也不用考虑背包容量，只有一个一维数组和三根指针。思维负担小，但核心味道已经齐全了：你需要在多个候选方案里每次挑一个最小的，同时维护好各自推进的起点。这个思想在很多更难的题里都会反复出现，值得花一下午把它彻底琢磨透。

2. 从暴力到动态规划：思路是怎么一步步逼出来的

2.1 暴力法看起来很美，实际跑不动

有的同学一看到第二问，第一反应是：我写一个 isUgly 函数，然后从 1 开始逐个数判断，数到第 n 个就返回。代码很简单，测试小数据也能跑通过。但你想过没有，这个方案连一个明确的循环上界都写不出来，只能写成while (count < n) num++这种形式。因为不知道大丑数长在哪个数值附近，只能死等。

我们用密度来感受一下问题的恐怖。丑数在整数里是稀疏的，100 以内还算密集，到 1000 以内大概还有一百多个，可越往后越稀。实际测试你会发现，想要数到第 1000 个丑数，从 1 开始逐个判断可能要跑好几百万次循环。n 再往上翻，暴力法直接原地爆炸，编程平台给你一个 n=1690 的测试点，基本就卡到超时。所以这道题从思路层面就排除暴力，不是要你优化常数，而是必须换方法论。

2.2 动态规划的核心观察：每个丑数都有“爸爸”

暴力不行，退回来从定义强推。一个丑数的质因数只有 2、3、5，这意味着什么？任何一个大于 1 的丑数，把它除以 2、除以 3 或除以 5，得到的数依然是丑数（前提是它能被整除）。反过来看：如果已知一个小丑数，把它乘以 2、3、5，得到的一定是丑数。这就是生成丑数的钥匙。

举例子：丑数 6 可以由 2 × 3 得到；丑数 8 可以由 4 × 2 得到；丑数 10 可以由 2 × 5 得到；丑数 12 可以由 6 × 2 得到。每个丑数都能追本溯源到一个更小的丑数乘上 2/3/5 之一。唯一的例外是 1，它是整个序列的起点。既然如此，我们从 dp[0]=1 出发，不断把已生成的丑数分别乘 2、乘 3、乘 5，取其中最小的放进序列，不就能从小到大生成全部丑数吗？

但这里立刻会出现一个工程问题：你有三条“流水线”，分别产出“某个丑数 × 2”、“某个丑数 × 3”、“某个丑数 × 5”的候选值。你怎么保证整体按序？怎么保证不重复？如果每次把所有已生成的丑数都翻一遍去乘 2/3/5，那 O(n²) 就回来了，本质没比暴力强多少。需要一种机制，让每一步只需要看三个候选值。这就是三指针法的价值。

2.3 三指针法：三条流水线的比赛

把 dp 数组理解成一条已经排好序的生产线。三个指针 p2、p3、p5 分别指向 dp 数组里的三个位置。约定是：p2 指向“下一个要被拿去乘 2 的最小丑数”，p3 和 p5 同理。每一步比较三个候选值 dp[p2]*2、dp[p3]*3、dp[p5]*5，取出最小的放进 dp 末尾。

为什么指针只往后走、不回头？因为 dp 本身是递增的，dp[0] < dp[1] < ... < dp[i-1] 已经生成完毕。p2 从 0 开始，dp[0]*2=2，被选中成为 dp[1] 之后，p2 前进到 1，表示“idx=0 的丑数乘 2 这个选项已经用过了，下一个该拿 idx=1 去乘 2”。此时 dp[1]*2=4，和 dp[0]*3=3、dp[0]*5=5 再比赛。每一步三个指针都在各自轨道上单调走，所以每条流水线每次产生的候选值只跟当前位置有关，整体呈现出一种“交错推进”的状态。这个机制跟归并排序里合并三个有序数组的思路一模一样，只是这里的三个数组长度不是预设的，而是动态生成的。

我还可以用一个生活化的类比帮你消化：假设三条装配线分别给产品装 2 号、3 号、5 号零件，每个装配线都有一个当前待处理的半成品位置（指针）。每条线每次只能前进一格，三台机器同时开工，每次产出最小的那个订单就出货。因为半成品从编号小的往编号大的排，指针单调往后走，所以每台机器下次产出的订单一定比这次大，三条线之间的比较永远只需要看队首。

3. 核心代码实现与参数拆解

3.1 丑数判断题的代码：三步除到底

先写丑数判断，这是基础中的基础。

public boolean isUgly(int n) { if (n <= 0) { return false; } int[] factors = {2, 3, 5}; for (int factor : factors) { while (n % factor == 0) { n /= factor; } } return n == 1; }

逻辑就三件事。第一，先处理非正数——丑数必须是正整数，负数、零直接返回 false，这一步容易漏。第二，用 2、3、5 依次去试除，注意这里用的是while而不是if，因为一个数可能被同一个因子多次整除，比如 8 = 2³，要连续除三次才能把因子 2 除干净。第三，返回时判断最后剩下的数是不是 1。比如输入 14，先除 2 得 7，7 除不了 2、除不了 3、也除不了 5，剩下 7，返回 false。

Python 写法同理，注意整除符号：

def is_ugly(n: int) -> bool: if n <= 0: return False for factor in (2, 3, 5): while n % factor == 0: n //= factor return n == 1

这里有一个值得一提的小细节：判断除法的顺序无所谓，因为除以因子和顺序无关，你除以 2 之后留下的数再去除 3 或 5，最终结果一致。

3.2 第 n 个丑数的动态规划实现：三指针的舞台

好戏在这里。维护一个长度为 n 的 dp 数组，dp[0] = 1，三个指针初始都指向 0。每次生成一个丑数，直到填满数组。

public int nthUglyNumber(int n) { int[] dp = new int[n]; dp[0] = 1; int p2 = 0, p3 = 0, p5 = 0; for (int i = 1; i < n; i++) { int a = dp[p2] * 2; int b = dp[p3] * 3; int c = dp[p5] * 5; dp[i] = Math.min(a, Math.min(b, c)); if (dp[i] == a) { p2++; } if (dp[i] == b) { p3++; } if (dp[i] == c) { p5++; } } return dp[n - 1]; }

我逐段说明。dp 数组用来存放已经确认的丑数序列，它天然有序。三个指针指向的位置分别代表“我希望拿它去乘 2 / 乘 3 / 乘 5 的那个丑数下标”。每一轮只做两件事：从三个候选值里挑最小，写进 dp；然后检查这个最小值到底来自哪几条流水线，把对应指针前进。注意这里if是一个个判断而不是else if，这是去重的关键，后面会在排查节细讲。

Python 版本：

def nth_ugly_number(n: int) -> int: dp = [1] * n p2 = p3 = p5 = 0 for i in range(1, n): a, b, c = dp[p2] * 2, dp[p3] * 3, dp[p5] * 5 dp[i] = min(a, b, c) if dp[i] == a: p2 += 1 if dp[i] == b: p3 += 1 if dp[i] == c: p5 += 1 return dp[-1]

看起来短，但每一行的意图都要吃透。为了更直观地理解指针如何移动，我们手推一遍 n=10 的过程：

第 1 轮，三个指针都在 0，候选是 2、3、5，最小为 2，dp[1]=2，p2 前进到 1。 第 2 轮，候选是 dp[1]*2=4、dp[0]*3=3、dp[0]*5=5，最小为 3，dp[2]=3，p3 前进到 1。 第 3 轮，候选是 4、6、5，最小为 4，dp[3]=4，p2 前进到 2。 第 4 轮，候选是 dp[2]*2=6、dp[1]*3=6、dp[0]*5=5，最小为 5，dp[4]=5，p5 前进到 1。 第 5 轮，候选是 6、6、10，最小为 6，dp[5]=6，p2 和 p3 同时前进到 3 和 2。 第 6 轮，候选是 dp[3]*2=8、dp[2]*3=9、10，最小为 8，dp[6]=8，p2 前进到 4。 第 7 轮，候选是 dp[4]*2=10、9、10，最小为 9，dp[7]=9，p3 前进到 3。 第 8 轮，候选是 10、dp[3]*3=12、10，最小为 10，dp[8]=10，p2 和 p5 同时前进到 5 和 2。 第 9 轮，候选是 dp[5]*2=12、12、dp[2]*5=20，最小为 12，dp[9]=12，p2 和 p3 同时前进到 6 和 4。

最终 dp[9]=12，这就是第 10 个丑数。推完这 9 轮你会发现两个规律：dp 数组严格递增，没有跳过任何丑数；出现重复候选值时，多个指针同时前进，不会把重复值写进数组。

3.3 复杂度与参数边界：为什么这个方案很稳

时间上，每轮只做三次乘法、两次比较、常数次指针更新，一共执行 n-1 轮，时间复杂度 O(n)。空间上，一个长度 n 的 dp 数组，O(n)。对比暴力遍历，这是质的飞跃。对比堆方案（下一节会讲），同样是 O(nlogn) 变 O(n)，在 n=1690 时差距不明显，但如果把这道题推广到“超级丑数”或更大规模，三指针的优势就彻底体现出来了。

还有一个细节值得留意：dp 数组里存的是 int，在题目常见限制下是安全的。以最经典的约束 n≤1690 为例，第 1690 个丑数大概是 2123366400，没有超过 int 上限 2147483647，所以 int 可以安心用。但如果你在面试中遇到不限制 n 的变体，或者把这道题改造为“第 m 个某类丑数”，建议换个更宽的整数类型，或者提前判断溢出，这个我在下一节专门展开。

4. 实操避坑实录：这些坑我基本都踩过一轮

4.1 边界条件：n=1、0、负数，别想当然

先说出题人最喜欢埋的雷：n=1 时，第 1 个丑数就是 1，循环一次都不跑，直接返回 dp[n-1]=dp[0]=1。这个分支是在代码里天然成立的，前提是你正确初始化了 dp[0]=1。有些同学写循环时把for (int i = 1; i < n; i++)错写成for (int i = 0; i < n; i++)，导致 dp[0] 被覆盖，整个序列全乱。

其次是 n≤0 的非法输入。虽然题目一般保证 n 是正整数，但写工具函数时最好加防御，直接在入口if (n <= 0) return -1;或抛出异常。丑数判断那道题就必须处理非正数，判断一个负数或 0 永远不是丑数。这两处边界都做到位，才算真正理解丑数的正整数属性。

4.2 溢出：int 到底够不够用

我见过不止一个人把这三条乘法写成int a = dp[p2] * 2，写完就忘了检查溢出风险。在标准约束 n≤1690 下确实没问题，但一旦题目变形，比如问“第 2000 个丑数”，乘积就可能顶穿 int 上限。这里有个实际工作中的好习惯：如果你能提前估算最大值，就把估算过程写进注释；如果估算不出来，就直接换long数组存 dp，最后返回时再转 int，代价可以忽略。

估算方法其实不复杂，丑数的增长速度介于指数和幂之间。最经典的经验值：第 1690 个丑数约等于 2^31 以下，恰好卡在 int 的边界内，这是平台故意设计好的。我自己遇到过一回，把 c 语言版的题改成 Java 时没注意，某次把 dp 数组扩容到 2000，输出全是负数，排查半小时才发现是 int 溢出。从那之后，我遇到这类生成型题目一律先想边界值，不赌题目仁慈。

4.3 去重逻辑：为什么是三个 if，不是 else if

这是三指针法最容易写错的地方，也是面试官最喜欢追问的点。很多人第一次写会写成：

if (dp[i] == a) p2++; else if (dp[i] == b) p3++; else if (dp[i] == c) p5++;

看起来合理：我选中的是哪个候选值，就推进哪个指针。但只要候选值里有相同的数，这么写就会把重复值写进 dp 数组。比如生成 6 的那一轮，a 和 b 都等于 6，你只能推进 p2 或 p3 其中一个，另一个指针停在原地，下一轮它还会再产出一个 6，dp 里就出现两个 6，序列被污染。

正确的写法是三个独立的 if，每命中一个候选值就推进对应指针。当 6 同时来自 dp[p2]*2 和 dp[p3]*3 时，p2 和 p3 一起前进，后续这两条流水线都不会再输出 6。记住这个原则：值碰值，指针就一起走。这也是三指针法相比“每轮从所有已生成丑数里找最小倍数”的一大优势——天然去重，不需要额外维护集合。

4.4 指针越界与逻辑验证：手推样例比 debug 更快

还有一个隐蔽点：你有没有想过 p2、p3、p5 会不会越界？毕竟 dp 数组还没填满，指针会不会指到未初始化的位置？我最初也担心过。分析一下就能安心：每个指针最多前进到 i-1，而生成 dp[i] 时只用 dp[p2]、dp[p3]、dp[p5]，它们的下标最大是 i-1，这些位置都已经在之前的迭代中填好值了。更重要的是，因为 dp 严格递增，dp[p2]*2只会越来越大，不会回头，所以指针不会无限停在某个位置把同一个候选值反复生成。你可以用反证法：如果 p2 一直不动，dp[p2]*2 就永远只是一个固定值，而 dp[i] 在递增，早晚会超过它，那 p2 就必然有前进的理由，否则下一轮最小值永远是它，而它已经小于 dp[i-1] 了，序列不再递增，矛盾。

理论归理论，实操时我还是建议你手推一遍 n=6 或 n=10 的完整过程。我每次带人学这道题，都要求先在纸上画一个三行三列的表格，分别记录每轮的 p2、p3、p5 和三个候选值。推完两三组，指针逻辑就再也忘不掉了。debug 永远没有手动推演来得直觉化。

5. 方案对比与变体延伸：别只背这一种解法

5.1 堆 + Set 方案：更直觉，但更费

我知道有些同学更喜欢另一个思路：用最小堆。初始把 1 放进去，然后从堆里取出最小元素，把它乘以 2、3、5 产生的三个数加入堆，同时用 Set 去重，重复 n-1 次，堆顶就是第 n 个丑数。这个方案理解起来确实舒服，完全就是模拟“生成—排序—去重”的直观过程。代码大致长这样：

public int nthUglyNumber(int n) { PriorityQueue<Long> heap = new PriorityQueue<>(); Set<Long> seen = new HashSet<>(); heap.offer(1L); seen.add(1L); long cur = 1L; int[] factors = {2, 3, 5}; for (int i = 0; i < n; i++) { cur = heap.poll(); for (int f : factors) { long next = cur * f; if (seen.add(next)) { heap.offer(next); } } } return (int) cur; }

这段代码有两个细节：一是乘出来的结果可能瞬间爆炸，必须用 long 存；二是 Set 去重是必须的，因为同一个数可以从不同路径生成。比如 6，可以先由 2 乘 3 得到，也可以由 3 乘 2 得到。但这个方案的时间复杂度是 O(nlogn)，空间复杂度最坏 O(n)，因为堆里会同时存在大量暂时不用的小候选值。和三指针的 O(n) 时间、O(n) 空间相比，理论上确实逊一筹。不过在面试现场，如果你一时想不出三指针，写出堆方案也能拿大部分分数，至少证明你理解了“从小丑数翻倍生成大丑数”的核心观察。我的建议是两种方案都要会写，堆方案用来兜底和验证，三指针作为最优解。

5.2 三指针相比堆方案的核心优势

三指针不只是常数级的优化，它把动态规划的思想展露得很完整：状态数组是“已知的丑数序列”，状态转移是“三个指针各自乘积取最小”，去重不是靠额外的数据结构，而是靠指针的同步推进。面试官如果追问“为什么不用 Set”，你至少能答出三层：第一，三指针保证每个丑数按统一来源生成一次，不需要额外判重；第二，不需要维护 O(n) 规模的堆结构，实际运行更快；第三，你能口头证明指针不会产生重复也不会遗漏。我记得某次模拟面试里，对方要求我推导一下“为什么每个丑数都会被生成到”，我就用反证法说：任何一个丑数，除 1 外都能写成另一个丑数乘以 2、3、5 的形式，而那个更小的丑数一定已经在 dp 数组里，所以只要生成过程完整覆盖已知丑数，递归下去就能覆盖所有丑数。这是我推荐用这篇文章的标题来练手的原因——它一道题串起了“定义推导、状态设计、指针优化、去重处理”四件事。

5.3 变体题：超级丑数和丑数 III

如果你吃透了丑数 II，再去看变体会很爽。超级丑数那道题，只是把 2、3、5 换成一个长度为 k 的质数数组，三指针变成三个指针数组。写起来照样简洁：维护 dp 数组，维护一个长度和质数数组相同的指针数组，每轮比较所有候选值找到最小，然后遍历指针数组，凡是候选值等于 min 的指针都前进。复杂度 O(nk)，k 是质数个数。本质上和丑数 II 没有区别，你只需要把“三个指针”抽象成“指针数组”，把三次乘法抽象成循环。

丑数 III 又不同了，它让你求“能被 a 或 b 或 c 整除的第 n 个数”。这个场景和丑数 II 完全不同，因为前者的丑数集合是离散的乘法生成，后者却是筛法加容斥，通常用二分答案 + 容斥原理来做。我不建议一口气吃太胖，但你至少要知道这个系列是逐步进阶的：丑数 I 是基础定义，丑数 II 是 DP 生成，超级丑数是指针扩展，丑数 III 是数论二分。把前三道串起来刷，动态规划这块的“多路归并”思想基本就焊死在脑子里了。

6. 面试场景与个人经验总结

说一个我自己的经历。有次为某公司的算法轮做准备，把丑数 II 当作热身题，第一遍写得很顺，三分钟就默出了三指针代码。但对面面试官随口问了一句：“你这个指针为什么不会回退？”我当时愣了一下，居然只回了一句“因为 dp 是递增的”。这句话本身没错，但太单薄了。事后我认真把这个问题理了一遍，才真正理解三指针法的本质：每个指针代表一条独立流水的当前待处理位置，dp 递增保证每条流水线的输出只会越来越大，各自有序的三条流线归并成一条大流水线，这就是多路归并。从那以后，我不再背模板，而是把“指针为什么单调”、“为什么不会重复”、“为什么不会遗漏”三个问题刻在脑子里。你也可以试试，把每道 DP 题问透这三个问题，记忆会牢固很多。

还有一个更现实的经验：先把丑数判断那题作为工具函数写好。很多面试官会要求你现场写 isUgly，然后立刻追问 n=1690 的版本。你用 1 分钟写完 isUgly，再花 8 分钟把三指针代码和推演样例讲完，差不多就是完美的回答节奏。如果你先讲堆方案再讲三指针优化，面试官会更愿意听你的复杂度对比分析。最后提醒一句，第三轮的重复候选值处理是高频考点，就算你已经写出完整代码，也要在口头解释里刻意强调三个独立 if 的用意，这样既展示了你踩过坑，也展示了你对去重本质的理解。

丑数这道题虽然名字滑稽，却是我和小伙伴们在准备算法面试时一致认为“性价比极高”的题目。别嫌它简单，也别嫌它基础，把三指针法的每一步推理都讲得出道理，比做完十道模板题有价值得多。