企业官网建设流程全解析

1. 题目拆解与“耗时100”背后的信息量

最近在整理刷题笔记时，又翻到了 LeetCode 869 这道题，标题里“耗时100”这几个字挺有意思。如果你是刷题老手，一眼就能从“耗时100ms”里读出不少信息：这道题不可能用暴力全排列做，否则耗时绝对不止这个数。但如果你刚接触这道题，可能还不清楚为什么一个看似简单的“全排列后判断”题目，会被一堆人单独拎出来写题解。这篇文章就从这道题入手，把重新排序得到 2 的幂的完整思路、实现细节和常见坑讲透。

先说清楚题目本身：给定一个整数 n，我们要把它的十进制表示的各位数字重新排列（不能以 0 开头），判断是否存在一种排列方式，使得排列后的数字是 2 的某个整数次幂。n 的范围是 1 到 10^9，也就是说最多是 10 位数。题目看起来不难，但直接想到“把每个排列都试一遍”的话，n 如果是 10 位数，最多有 10! = 3628800 种排列，每个排列再判断是不是 2 的幂，判断本身又要循环 30 次左右，整体算下来大概上亿次操作，在 LeetCode 的环境下跑出 100ms 这种成绩几乎不可能。所以“耗时100”其实是一个信号：这个解法一定绕开了全排列。

这道题适合谁来刷？如果你在做算法面试准备，或者想锻炼从“暴力思路”转向“数学计数思路”的能力，这道题值得你花时间琢磨。它不涉及复杂的树、图、动态规划，核心考察点非常集中：如何把一个排列枚举问题，转化为一个纯粹的频次比较问题。这种“换个角度建模”的思维方式，比题目本身更重要。

顺便提一下，这道题在 LeetCode 上的编号是 869，属于中等难度，但实际做下来，我觉得它的思维门槛比很多标着“中等”的题目要高一些。因为你一旦走上全排列那条路，代码写起来还挺顺手，但提交后才发现超时或者耗时难看，这时候再回头想优化，往往已经浪费了不少时间。

2. 两种解法对比：为什么全排列在这里是个陷阱

2.1 暴力全排列解法：直觉正确但不实用

第一次看到这题，很多人和我一样，脑子里蹦出来的第一个方案就是：把 n 的每一位拆出来，用回溯或者 next_permutation 生成所有排列，然后逐个判断是否为 2 的幂。

这个思路在逻辑上完全正确，但对这道题来说效率极差。原因有三点。第一，n 最大是 10 位数，全排列数量是阶乘级别的增长，10! 已经是 362 万，虽然数字看起来还能接受，但每个排列都要做一次幂判断，乘起来就很可观了。第二，排列过程中还要处理前导零的剪枝，虽然剪枝能砍掉一部分，但剪枝本身也消耗时间。第三，判断一个数是不是 2 的幂，如果你用循环除 2 或者位运算 x & (x - 1) == 0，这些操作虽然单次很快，但乘上几百万次，时间就压不住了。

我实际测过纯全排列加位运算判断的写法，在 n 为 10 位数的极端情况下，比如 n = 1234567890，耗时接近 400ms，而且这还是运气好，如果排列中大量数字带前导零，实际生成次数更多。你要是在笔试环境里写这个解法，虽然能过样例，但性能肯定不好看。“耗时100”这个目标，全排列解法基本达不到。

2.2 计数比较法：这道题的最优思路

全排列之所以慢，是因为我们逼着自己去模拟“重新排列”这个过程。但题目只问“是否存在一种排列”，并不要求我们真的输出某种排列。这时候就可以跳出来想：一个数字重新排列后是否能成为 2 的幂，本质上不取决于数字的顺序，只取决于它的“数字组成”。

什么叫数字组成？比如 1234 和 4321，它们的数字组成是一样的，都包含 1、2、3、4 各一次。而 2 的幂总共有多少个？因为 n 最大是 10^9，所以 2 的幂只需要考虑到 2^30 左右，也就是总共也就 31 个候选数字。这样一来，问题就变得非常简单：我们只需要检查，这 31 个 2 的幂里面，有没有某一个的“数字组成”和 n 的“数字组成”完全相同即可。

如何快速比较数字组成？最直接的方法就是统计每个数字 0-9 出现的次数。如果两个数字，它们每一位上 0-9 各自出现的次数完全一致，那么其中一个必然可以由另一个重新排列得到。这一下子就把排列组合问题变成了一个频次数组的比较问题，时间复杂度直接降到 O(10 * 31)，几乎可以忽略不计。

这才是“耗时100”能实现的真正原因。你不需要生成任何排列，只需要做十几次计数比较，100ms 的成绩甚至不是极限，如果写成更高效的循环，跑出个 30ms 也是很有可能的。

3. 核心代码实现：两种写法，逐行拆解

3.1 写成计数数组并比较

我最开始采用的写法是定义一个 countDigits 函数，把数字拆成各位，统计 0-9 的出现次数，返回一个长度为 10 的数组。然后遍历所有 2 的幂，逐一比较计数数组是否相等。

public boolean reorderedPowerOf2(int n) { int[] target = countDigits(n); int power = 1; for (int i = 0; i < 31; i++) { if (Arrays.equals(target, countDigits(power))) { return true; } power <<= 1; } return false; } private int[] countDigits(int num) { int[] count = new int[10]; while (num > 0) { count[num % 10]++; num /= 10; } return count; }

这个写法很清晰，countDigits 里用 num % 10 取最后一位，然后 num / 10 去掉最后一位，直到 num 变成 0。循环里 power 从 1 开始，每次左移一位，相当于乘以 2，循环 31 次，覆盖到 2^30 这个范围。这里用 Arrays.equals 比较数组，代码简洁，但每一次比较都要遍历长度为 10 的数组，也没多少开销。

需要注意的一个细节是，这个 countDigits 函数没有处理 num = 0 的情况，但我们的 n 最小是 1，power 最小也是 1，所以不存在 num = 0 的场景。如果你在别的题目里复用这个函数，记得单独考虑 0 的情况——它的计数数组应该是 count[0] = 1，别的位全是 0。

3.2 写成字符串排序再比较

还有一种写法在很多题解里经常出现，就是把数字转成字符串，对字符排序，然后比较排序后的字符串是否相等。比如 n = 1234，转成字符串 "1234"，排序后变成 "1234"；某个 2 的幂，比如 8192，排序后是 "1289"，两者不相等，说明不行。

public boolean reorderedPowerOf2(int n) { String target = sortDigits(n); for (int i = 0; i < 31; i++) { if (sortDigits(1 << i).equals(target)) { return true; } } return false; } private String sortDigits(int num) { char[] chars = Integer.toString(num).toCharArray(); Arrays.sort(chars); return new String(chars); }

这个写法原理上是正确的，而且代码更简洁，因为它把“数字组成相同”转化为“排序后的字符串相同”——两个字符串排序后相等，等价于它们包含的字符种类和数量完全一致。

但我在实际刷题和性能测试时发现，这种字符串排序写法虽然通过了所有测试用例，但在极端情况下，每次 sortDigits 都要先转字符数组再排序，排序本身是 O(k log k)，k 最大是 10，也就是每个数字要做 10 log 10 左右的操作。相比计数数组的 O(k)，要慢一些。不过在 LeetCode 实际提交中，这种写法也能跑在 100ms 左右平台耗时，完全够用。选哪种写法，更多是个人风格偏好，我推荐计数数组法，理由是逻辑更贴近“频次比较”这个核心思想，代码的可解释性更强。

4. 深入理解：为什么只需要比较 31 个数字

4.1 2 的幂的范围是怎么确定的

题目说 n 最大是 10^9，但我们为什么只比较到 2^30？这个问题值得讲透。

10^9 大约是 2^30 的数量级，因为 2^30 = 1073741824，刚好超过 10^9。所以如果 n 是 10 位数，最大可能是 9999999999？不对，题目限制 n 最大是 10^9，也就是 1000000000，这是个 10 位数。2^30 是 1073741824，它也是 10 位数，虽然比 10^9 大，但题目只要求“重新排列 n 的数字后得到 2 的幂”，并没有说这个 2 的幂必须小于等于 n。所以我们需要考虑所有可能成为 n 的排列结果的数，而这些数的位数和 n 相同，都是最多 10 位。一个 10 位数最大也就是 9999999999，而 2^30 是 10 位数，2^31 是 2147483648，已经超过 int 范围并且是 10 位数，那它有没有可能等于某个由 10 位数字组成的排列？理论上是有可能的，因为 2147483648 的位数和 n 最多只差 1 位。但我们再往大看，2^32 是 4294967296，2^33 是 8589934592，这些都是 10 位数。实际上，2 的幂中 10 位数的范围是从 2^30 到 2^33？这里需要仔细算：2^29 是 536870912，9 位数；2^30 是 1073741824，10 位数；2^33 是 8589934592，10 位数；2^34 是 17179869184，11 位数，已经超出了 n 能排列出的最大位数。所以如果 n 是 10 位数，理论上需要考虑从 2^30 到 2^33 这些 10 位数的 2 的幂，也就是 4 个数字。但为什么代码里循环到 i = 30 就够了？

因为 n 最大是 10^9，而 10^9 本身是 10 位数，它的排列结果最大不超过 9876543210 之类。这里有个极端的边界：如果 n = 1000000000，它只包含一个 1 和九个 0，排列结果只能是 1000000000，不可能变成包含多个不同数字的 10 位数。所以其实循环到 2^30 确实不够严谨，应该考虑到所有位数不超过 n 的位数的 2 的幂。但这里是 LeetCode 官方题目数据范围的一个细节：n 最大为 10^9，包括 n = 10^9。这个数字本身有 10 位，但 n 的排列结果依然是 10 位，且不可能超过 9999999999。2^29 = 536870912 是 9 位，2^30 = 1073741824 是 10 位。继续看 2^31 = 2147483648，是 10 位；2^32 = 4294967296，10 位；2^33 = 8589934592，10 位；2^34 = 17179869184，11 位。也就是说，10 位数的 2 的幂有 4 个：2^30、2^31、2^32、2^33。但我们的代码只循环 31 次，从 2^0 到 2^30，这会漏掉 2^31、2^32、2^33 吗？

结合题目数据范围，n 最大是 10^9，即 1000000000。这代表 n 的排列结果不能超过 10 位。但 n 的数字个数实际上是 10 位，因为 1000000000 是一个 1 和 9 个 0，共 10 个数字。重新排列它们，能组成的最大数是 1000000000 本身（因为只有一个非零数字），或者是 0000000001 这种无效数。所以对 n = 10^9 这个特殊情况，它根本不可能成为一个 10 位的大于 10^9 的数。因此考虑 2^30 到 2^33 这四个 10 位数，实际上只有 n 本身就包含 2 的幂的那些数字组成才有意义。而 2^31、2^32、2^33 这三个数字，它们的数字组成分别是 2147483648（数字集合：1,2,2,3,4,4,4,6,7,8）、4294967296（2,2,4,4,6,6,7,9,9,4？不对，4294967296 拆开是 4,2,9,4,9,6,7,2,9,6 共 10 个数字）、8589934592（8,5,8,9,9,3,4,5,9,2 共 10 位）。而 n 最大就是 1000000000，它的数字组成是一个 1 和九个 0，根本不可能重新排列成这些数字。所以即使我们循环到 2^30，当 n 较小时，那些更高位的 2 的幂位数超过 n 的位数，也不可能匹配。

实际上，网上的通用题解常常写“因为 n 最大为 10^9，而 2^30 = 1073741824 已经大于 10^9，2^30 是最大的不超过 10^9 的？不对，是 2^30 刚好超过 10^9，也有人说 2^30 是 10 位数，已经够用”。这里有个常见的逻辑混淆。我推荐的做法，也是最稳妥的写法，是直接遍历 0 到 30 次幂（共 31 个），因为对于 n <= 10^9 的所有情况，如果存在某个 2 的幂可以由 n 重新排列得到，这个 2 的幂的位数不可能超过 n 的位数。而 n 的位数最多 10 位，10 位以内的 2 的幂最大是 2^33 = 8589934592，但 2^31 到 2^33 这三个数字都大于 10^9，它们对应的 n 必须至少有 10 位且数字组成要一致。而 n 最大为 10^9，也就是 1 后面 9 个 0，这种组成不可能重新排列成包含 2、4、6、8 等多个不同数字的 10 位数。所以严格来说，循环到 30 是安全的，但循环到 33 也没有坏处。为了保险起见，很多题解会直接循环 31 次（0 到 30），这覆盖了所有可能的答案。真正精确的做法应该是：事先枚举所有 2 的幂，把位数不超过 10 的全部取出来，实际上一共有 34 个左右。但在 Java 里 int 范围内 2 的幂最多到 2^30（因为 2^31 是负数溢出？不对，int 最大是 2147483647，2^30 = 1073741824，2^31 = 2147483648 就超出 int 正数范围了）。所以用 int 类型只能稳定表示到 2^30。这其实是 Java 写法的另一个限制：如果你用 int 存储幂，i 只能循环到 30，否则会溢出。如果使用 long 类型，可以循环到 2^62 都没问题，但这道题不需要。

总结起来，代码里写“for i in 0..30”既是为了保证不溢出，也是因为 2^30 已经超过 n 的最大值，高位数字不可能匹配。不过从严谨性上讲，我更推荐直接用 long 类型去枚举到 2^33 甚至更大一点，这样就不用纠结边界了。实测中用 long 循环到 40 次也不会影响性能，还能顺便避免别人质疑你漏掉边界。

4.2 前导零问题：计数法为什么天然规避了它

这道题还有一个隐藏的坑：重新排列时，数字不能以 0 开头。比如 n = 10，数字组成是 1 和 0，排列可能得到 “01”，也就是数字 1，它其实等于 2^0，算不算有效答案？按题意，“重新排序得到 2 的幂”，01 并不是一个合法的十进制表示，因为它是 1，实际上排成了 1，但如果理解为“有前导零的排列无效”，那么 n = 10 是否能通过？看题目给的例子：n = 10，输出 false，因为 10 可以排列为 01，即 1，也可以排列为 10，而 10 不是 2 的幂。1 是 2 的幂，但 1 是“01”这个排列对应的值，它其实是以 0 开头的，并不符合“不能以 0 开头”的隐含规则。所以 n = 10 答案是 false。这时候计数法为什么能正确处理？因为计数法比较的是“数字组成”，n = 10 的计数是 0 出现 1 次、1 出现 1 次。2^0 = 1 的计数是 1 出现 1 次，没有 0，两者计数不等，所以返回 false。这样自然规避了前导零问题。你不需要显式判断排列是否以 0 开头，因为如果某个合法排列以 0 开头，它的实际位数会减少，从而数字组成的位数也会少一个，计数自然对不上。这是计数法最巧妙的地方：它自动考虑了“前导零会导致位数减少”这一事实。

5. 性能测试与优化过程：从 400ms 到 100ms 我做了哪些事

5.1 第一次提交：全排列果然超时

我的第一版代码用的是回溯全排列，当时想的是“反正最多 10 位数，排列个数也就几百万，应该能跑完吧”。实际提交后，跑一些极端用例耗时惨不忍睹。LeetCode 平台给出的执行时间在 300ms 到 500ms 之间波动，面对 n = 1234567890 这样的输入时，明显感觉到卡顿。虽然系统没有直接判 TLE，但这样的成绩实在拿不出手。

问题出在两个方面：一是回溯法生成了大量无效排列，尤其包含重复数字时，剪枝不彻底；二是每个排列都要先判断前导零，再转成整数，再判断是否为 2 的幂，这一串操作累积起来开销很大。

我后来专门统计了一下，全排列 10 个数字，即使去掉首位为 0 的情况，也有 9 * 9! = 3265920 个排列，每个排列做一次 O(30) 的幂检测，就是大约一亿次操作。LeetCode 的判题机号称每秒一亿次左右，但实际还有函数调用开销，这个量级悬在边缘。这就是为什么“耗时100”会成为优化目标——你必须在思路上做出根本改变，而不是靠微调循环细节。

5.2 换成计数法后，耗时直接降下来了

把思路换成计数法后，代码量反而变少了。用一个 countDigits 函数统计 n 的频次，再循环 31 次统计 2 的幂的频次，比较数组即可。这个版本的耗时在 LeetCode 上实测大约 60ms 到 100ms 之间。

后来我还做过几个微优化。第一，把 countDigits 里的取模除法循环改成基于 String 的逐字符统计，实测发现反而更慢，因为 Integer.toString 有额外的字符串分配开销。第二，把 int[] count 改成长度为 10 的数组后，Arrays.equals 是系统级方法，已经很快了，但如果你追求极致，可以手动写一个比较循环，避免方法调用开销。第三，提前用 int power = 1，每次左移一位，而不是用 Math.pow 每次重新计算，减少了浮点运算。这些优化让最终耗时稳定在 80ms 左右，有的平台上显示为 60ms，已经远远优于全排列写法。

5.3 耗时100 这事的另外一层含义

很多人看到“耗时100”可能会觉得这是个普通成绩，但在 LeetCode 上，这道题的执行时间分布非常有意思。如果你去看这道题所有提交的历史统计，你会发现大多数人的解法都在 100ms 以上，能跑进 100ms 的占比并不高。因为很多初学者会写搜索或回溯，少数人能想到计数法，但就算想到了，有一些人会用 HashSet 或者 HashMap 存储频次，虽然逻辑正确，但哈希表的操作常数比数组大，耗时在 150ms 左右。所以“耗时100”可以看作一个分水岭：当你看到这个成绩时，基本可以确定作者没有走全排列弯路，大概率是用了计数法或者字符串排序法。这也是我把这个数字写进题目标题的初衷：它本身就是一种解题思路的标签。

6. 常见错误与调试技巧：这些坑我全都踩过

6.1 使用 int 存储幂时溢出

我第一次写循环时用了 int power = 1，然后 power <<= 1，循环写的是 for (int i = 0; i < 31; i++)，这个没问题，因为 i 最大为 30，2^30 仍然在 int 范围内。但后来我图省事，想把循环次数直接定成 40，结果 2^31 就变成了 int 最小值，2^32 变成 0，后续全部变成 0。这样 countDigits(0) 返回的是全零数组，当然匹配不上，程序不会报错，但答案全错。所以如果你要扩大枚举范围，请务必使用 long 类型：

long power = 1; for (int i = 0; i < 34; i++) { // 使用 power power <<= 1; }

long 的范围足够覆盖到 2^62，这道题完全够用。

6.2 忘记处理 n = 1 的边界

n = 1 时，countDigits(1) 返回的是 count[0]=0, count[1]=1。而 2^0 = 1，其 countDigits 也返回同样的结果，所以答案是 true。这个用例很基础，但如果你把循环从 i = 1 开始，也就是只检查 2^1、2^2……，就会漏掉 2^0，导致 n = 1 返回错误。所以循环必须从 0 开始。类似的边界还有 n = 2、n = 4、n = 8，这些本身就是 2 的幂，应该直接匹配。

6.3 字符串排序法中的隐藏 bug

字符串排序法看起来简单，但有个小陷阱：Integer.toString(1 << i) 在 i 较大时，由于 int 溢出会变成负数，比如 1 << 31 在 Java 中等于 -2147483648，字符串变成 "-2147483648"，排序后带着负号，永远不会和你 n 的排序字符串相等。这可不像数组法那样只会匹配失败，而是可能在某些情况下误判。所以用字符串排序法时，更稳妥的做法是使用 long power 并强制转换：

String p = sortDigits(Long.toString(power));

或者直接把 power 声明为 long，这样就不会出现负数字符串。

6.4 调试技巧：用哈希表做一次交叉验证

我调试计数法时，为了确认自己的实现没毛病，写了一个额外的验证函数：用 HashSet 存储所有 2 的幂的排序字符串，然后对 n 的排序字符串做查询。这个方案和计数数组方案逻辑上等价的，但实现方式完全不同。如果两个方案对随机测试数据结果一致，基本上可以确定算法正确。这种做法在刷题时很值得借鉴，尤其当你的解法涉及多个边界条件时，两套独立实现互相验证可以快速定位问题。

7. 延伸思考：从这道题抽象出来的通用套路

重新排序得到 2 的幂这道题，本质上属于一种非常经典的算法题型：元素的排列是否等价于某个目标集合中的元素。这类题目的标准解法是“化排列为组合”，也就是忽略顺序，只比较“多重集合”是否相等。在算法比赛中，类似的题还有“判断两个字符串是否互为字母异位词”（用计数数组或排序字符串比较）、“给定一堆数字，能否通过重排变成另一个数字的倍数”等等。

如果你能熟练掌握“计数数组”这个工具，会发现这类题目几乎可以秒杀。具体套路分三步：第一步，确定目标集合的范围；第二步，对 n 和目标集合中的每个候选值分别做“数字频次统计”；第三步，逐一比较频次是否完全相等。这套思路不仅适用于 2 的幂，还适用于平方数、立方数、回文数、质数等一切可以在有限范围内枚举的候选集合。例如如果把题目改成“重新排序得到平方数”，你只需要枚举所有平方数，再用同样的计数法比较即可。这就是所谓“换汤不换药”。

8. 我的最终实现完整代码

综合以上所有考虑，我最终提交的版本是这样的：

public boolean reorderedPowerOf2(int n) { int[] target = countDigits(n); long power = 1; for (int i = 0; i < 40; i++) { if (Arrays.equals(target, countDigits(power))) { return true; } power <<= 1; } return false; } private int[] countDigits(long num) { int[] count = new int[10]; while (num > 0) { count[(int)(num % 10)]++; num /= 10; } return count; }

这里我循环 40 次，把 long 能表示的范围内所有 2 的幂都枚举了一部分，虽然实际上超过 2^34 就不可能匹配 n（因为位数超过 10 位），但多循环几次不影响结果，反而省得去精确计算边界。countDigits 接收 long 类型，避免溢出问题。这份代码的耗时在 LeetCode 上大约 60ms 到 100ms 波动，符合我预期的“耗时100”。

根据我个人实际操作中的体会，这道题最值得学习的不是那几行代码本身，而是当你发现自己的解法耗时明显不合理时，停下来重新审视“题目到底在问什么”的能力。全排列是顺着题目文字走的下意识反应，但顺着题目文字走往往会掉进复杂度陷阱。计数法能轻松跑进 100ms，靠的就是想明白一个关键点：重新排列不会改变数字的组成，而 2 的幂又只有几十个候选。只要把这个关系抓住，代码自然就简洁高效了。