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 最小是 1power 最小也是 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 是 42949672962^33 是 8589934592这些都是 10 位数。实际上2 的幂中 10 位数的范围是从 2^30 到 2^33这里需要仔细算2^29 是 5368709129 位数2^30 是 107374182410 位数2^33 是 858993459210 位数2^34 是 1717986918411 位数已经超出了 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 429496729610 位2^33 858993459210 位2^34 1717986918411 位。也就是说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、42949672962,2,4,4,6,6,7,9,9,4不对4294967296 拆开是 4,2,9,4,9,6,7,2,9,6 共 10 个数字、85899345928,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^92^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 最大是 21474836472^30 10737418242^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 最大为 302^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 的幂又只有几十个候选。只要把这个关系抓住代码自然就简洁高效了。
