LeetCode 869题解析：数字重排与2的幂判断的高效算法实现

1. 项目概述：从一道题看算法思维的深度

今天想和大家深入聊聊LeetCode上的第869题——“重新排序得到 2 的幂”。乍一看这个标题，可能很多朋友会觉得这又是一道关于数字或位运算的简单题。确实，它的标签是“中等”难度，题目描述也极其简洁：给定一个正整数n，我们可以通过重新排列其数字（可以包含前导零）来得到另一个数字。如果这个新数字是 2 的幂，则返回true；否则，返回false。例如，n=1返回true，n=10返回false（因为01不是有效的数字，10重排后也得不到 2 的幂）。

但如果你仅仅把它当作一道“数字重排+幂判断”的题目，用暴力枚举的思路去解，那可能就错过了这道题真正的价值。这道题的精妙之处在于，它像一把钥匙，能打开通往多种高效算法思维的大门。它考察的远不止是基础的编程能力，更是对问题转化、预处理、哈希映射和边界条件处理的综合运用。对于正在准备技术面试，尤其是国内外大厂算法轮的同学来说，深入理解这道题的多种解法及其背后的思想，远比刷完十道简单题更有意义。它教会我们，面对一个看似明确的问题时，如何跳出暴力穷举的惯性思维，去寻找更优雅、更高效的解决方案。

2. 核心思路拆解：为什么不能直接暴力搜索？

拿到题目，最直接的想法可能是：生成数字n所有可能的排列，然后逐个检查是否为 2 的幂。这个思路清晰明了，但存在一个致命问题：时间复杂度爆炸。一个长度为L的数字，其不同排列的数量是L!（阶乘）。对于n最大可以到10^9（即最多10位数字），最坏情况下需要检查10! = 3,628,800种排列。虽然对于单个测试用例现代计算机可能勉强能跑，但这绝不是算法题期望的解法，更无法通过所有测试用例。

因此，我们必须寻找更聪明的办法。这道题的核心约束在于“2的幂”。在整数范围内，2的幂是有限的、可预知的。一个关键的突破口是：如果两个数字可以通过重新排列数字得到，那么它们的数字构成（即每个数字0-9出现的次数）一定是相同的。例如，46和64，它们的数字构成都是{‘4’:1， ‘6’:1}。

基于这个观察，我们可以将原问题转化为一个模式匹配问题：

1. 预处理阶段：生成所有在给定数据范围内（比如n是32位整数）的 2 的幂。
2. 对于每个 2 的幂，计算其“数字签名”（Digital Signature）或“数字指纹”。这个指纹就是其十进制表示中，每个数字（0-9）出现的次数。
3. 对于输入的n，同样计算其数字指纹。
4. 最后，只需检查n的数字指纹是否存在于所有 2 的幂的数字指纹集合中。存在则返回true，否则返回false。

这种思路将问题从“排列组合+幂判断”的O(L!)复杂度，降低到了“计算指纹+集合查找”的O(L + K)复杂度（K是2的幂的个数），这是一个质的飞跃。

2.1 方案选型背后的考量

为什么选择“数字指纹”对比法，而不是其他方法？比如，为什么不直接对n的字符数组排序，然后和排序后的 2 的幂字符串比较？

实际上，排序对比法是完全可行的，也是很多解法的实现方式之一。但“数字指纹”法在概念上更清晰，并且为后续可能的优化（如使用位运算压缩指纹）留下了空间。排序法的核心逻辑是：如果两个数字是数字重排关系，那么它们排序后的字符串一定相等。例如，46排序后是"46"，64排序后也是"46"。我们只需要将所有 2 的幂转换成字符串并排序，存储起来，然后将输入n的字符串排序后与之比较即可。

两种方法（指纹法和排序法）在时间复杂度上相近。指纹法可能略快，因为计算数字出现次数通常比排序字符串快一丁点，但差异不大。选择哪一种，更多是个人编码习惯和清晰度的考量。在面试中，能够清晰阐述任何一种方法的原理和复杂度，都是合格的。

注意：这里有一个非常重要的细节，题目允许包含前导零。这意味着数字1和10重排后得到的01（即1）是有效的。在我们的解法中，无论是计算指纹还是排序字符串，“1”和“10”的指纹/排序结果都是不同的（“1”vs“01”），因此算法能正确处理。我们不需要在代码中特殊处理前导零，因为数字本身的字符串表示已经包含了其位数信息。

3. 核心细节解析与实操要点

3.1 “数字指纹”的具体实现

如何高效地计算和表示一个数字的“数字指纹”？这里提供两种主流方法：

方法一：长度固定的计数数组由于数字只能是0-9，我们可以用一个长度为10的整数数组count来表示指纹。count[i]表示数字i出现的次数。

def get_signature_count(num: int) -> tuple: count = [0] * 10 for ch in str(num): count[int(ch)] += 1 return tuple(count) # 转换为元组，以便放入集合或作为字典的键

将数组转换为元组tuple(count)是关键一步，因为Python的列表（list）是可变的，不能直接作为集合（set）的元素或字典（dict）的键，而元组是不可变的。

方法二：排序字符串将数字转换为字符串，然后对字符串中的字符进行排序，排序后的字符串本身就可以作为“指纹”。

def get_signature_sort(num: int) -> str: return ''.join(sorted(str(num)))

这种方法更直观，“46”和“64”排序后都得到“46”，直接比较字符串即可。

对比与选择：

• 计数数组法：更通用，理论上稍快（O(L)遍历 vsO(L log L)排序），且其数据结构（数组）更容易扩展到其他场景，比如用位图进一步压缩。
• 排序字符串法：实现极其简单，代码可读性高，在大多数情况下性能足够好，是快速解题时的首选。

在面试中，如果被问到“还有没有更优的方法？”，你可以提到计数数组法，并讨论其常数级别的性能优势。

3.2 2的幂的预处理范围

另一个关键细节是：我们需要预处理多少個 2 的幂？题目中n的范围是[1, 10^9]。因此，我们只需要考虑所有不超过10^9的 2 的幂。2^30 = 1,073,741,824已经大于10^9，所以2^29 = 536,870,912是范围内最大的一个。因此，我们需要预处理的 2 的幂是从2^0 = 1到2^29，总共30个数字。这是一个非常小的、固定的集合，预处理的开销可以忽略不计。

我们可以直接在代码中静态列出这30个数字，也可以在程序初始化时动态计算并缓存它们的指纹。动态计算更具通用性，如果题目范围变化也易于调整。

3.3 边界条件与特殊输入处理

1. 输入为1：1本身就是 2 的幂 (2^0)，应返回true。我们的算法能正确处理，因为1的指纹会在预处理集合中。
2. 输入包含数字0：例如n=1024。算法会计算“1024”的指纹（包含1个‘1’，1个‘0’，1个‘2’，1个‘4’），然后与2^10=1024的指纹匹配，返回true。包含零不会影响指纹的计算和比较。
3. 大数输入：例如n=999999999（9个9）。算法会计算其指纹（9个‘9’），然后与所有30个2的幂的指纹比较，无一匹配，返回false。这个过程是高效的。
4. 前导零问题：正如之前强调的，我们不需要也不应该试图生成带有前导零的重排数字。例如n=10，其排序后字符串是“01”，对应的数字是1。我们只需检查“01”是否等于某个2的幂排序后的字符串。2^0=1排序后是“1”，两者不相等，所以返回false。算法逻辑自然地处理了这一点，因为“10”和“1”的十进制表示不同，它们的排序字符串自然也不同。

4. 完整代码实现与逐步解析

下面我将以Python为例，分别用“排序字符串法”和“计数数组法”实现，并附上详细注释。

4.1 方法一：排序字符串法（推荐，清晰易懂）

class Solution: def reorderedPowerOf2(self, n: int) -> bool: # 第一步：预处理，计算所有可能范围内2的幂的“排序签名” # 2^29 = 536,870,912 是小于10^9的最大2的幂 power_of_2_signatures = set() power = 1 while power <= 10**9: # 将数字转为字符串，排序，作为唯一签名加入集合 signature = ''.join(sorted(str(power))) power_of_2_signatures.add(signature) power <<= 1 # 等价于 power *= 2，位运算更高效 # 第二步：计算输入n的签名 n_signature = ''.join(sorted(str(n))) # 第三步：判断n的签名是否存在于预处理的签名集合中 return n_signature in power_of_2_signatures

代码解析：

1. power_of_2_signatures = set(): 使用集合（set）来存储所有2的幂的签名，因为集合的in操作平均时间复杂度是O(1)，非常高效。
2. while power <= 10**9: 循环生成所有不超过10^9的2的幂。从1(2^0) 开始。
3. signature = ''.join(sorted(str(power))): 这是核心操作。str(power)将数字转为字符串，sorted(...)对字符串中的字符进行排序，返回一个字符列表，''.join(...)再将列表拼接回字符串。例如power=46得到"46"，power=64也得到"46"。
4. power <<= 1: 用左移一位来实现乘以2，这是位运算，通常比直接乘法*2稍快，也更符合“2的幂”这个语境。
5. return n_signature in power_of_2_signatures: 最后一行直接返回比较结果，简洁明了。

4.2 方法二：计数数组法（更底层的实现）

class Solution: def reorderedPowerOf2(self, n: int) -> bool: def count_digits(num: int): """计算一个数字的十进制表示中，每个数字出现的次数，返回为元组""" cnt = [0] * 10 while num > 0: digit = num % 10 # 获取个位数 cnt[digit] += 1 num //= 10 # 去掉个位数 # 处理数字为0的特殊情况（虽然题目n>=1，但2的幂有1，其循环会直接跳过） if sum(cnt) == 0: # 实际上，当输入n=0时才会触发，但题目范围n>=1，此分支仅用于完整性 cnt[0] = 1 return tuple(cnt) # 预处理2的幂的数字计数 power_digit_counts = set() power = 1 while power <= 10**9: power_digit_counts.add(count_digits(power)) power <<= 1 # 计算输入n的数字计数 n_digit_count = count_digits(n) # 判断 return n_digit_count in power_digit_counts

代码解析：

1. count_digits函数：通过不断取模（% 10）和整除（// 10）来分解数字，统计每位数字。这种方式比先转字符串再遍历，在极致的性能追求下可能有一丝优势，但代码稍复杂。
2. 返回tuple(cnt)：将列表转换为元组，使其可哈希（hashable），才能放入set中。
3. 主逻辑与方法一完全一致，只是比较的对象从排序后的字符串变成了数字计数元组。

实操心得：在面试或竞赛中，方法一（排序字符串法）通常是首选。它实现简单，不易出错，可读性极高，并且性能完全满足要求。只有在面试官明确追问“能否不用排序”时，再引出方法二。先给出最清晰、最可靠的解法，永远是上策。

5. 复杂度分析与算法评价

• 时间复杂度：设n的十进制位数为L，2的幂的个数为K（本题中K=30）。
  • 预处理阶段：需要计算K个数字的签名，每个计算成本为O(L_i log L_i)（排序）或O(L_i)（计数），其中L_i是每个幂的位数。由于K很小且固定，这部分是O(1)常数时间。
  • 对输入n的处理：计算签名，成本为O(L log L)或O(L)。
  • 集合查找：O(1)。
  • 因此，总时间复杂度为O(L log L)或O(L)，这取决于签名计算方式。这比暴力排列的O(L!)高效无数倍。
• 空间复杂度：主要存储K个签名，每个签名大小与数字位数成正比，因此是O(K * L_avg)，由于K和L_avg都是常数，所以空间复杂度也是O(1)。

算法评价：这是一个典型的空间换时间和预处理思想的优秀案例。通过预先计算并存储所有可能目标的“特征”（签名），将每次查询的代价降到最低。这种思想在解决很多“匹配”或“存在性判断”问题时非常有用，例如判断一个单词是否由某些字母组成（字母异位词）、判断一个数是否在某个已知集合的变形中等等。

6. 常见问题与排查技巧实录

在实际编码和调试过程中，可能会遇到以下几个典型问题：

问题1：为什么我用递归生成所有排列的方法，对于大数字会超时或栈溢出？原因：这就是我们一开始就分析的复杂度问题。排列的数量是阶乘级的，对于10位数字，有三百多万种排列，逐个检查是否为2的幂，计算量巨大，必然超时。解决：立即放弃暴力排列的思路，转向基于“签名”或“特征”的匹配方法。这是本题考察的核心能力——识别并避免低效算法。

问题2：我用了排序字符串法，但觉得对于每个n都排序一次，会不会慢？能不能进一步优化？思考：这是一个很好的进阶思考。对于单次查询，O(L log L)的排序已经足够快。但如果是在一个需要频繁调用此函数的场景（例如作为某个服务的API），我们可以考虑对输入n也进行预处理吗？实际上，由于n每次都可能不同，无法像2的幂那样一次性预处理。但是，我们可以将计算签名的函数写得尽可能高效。此外，可以探讨一个更极致的优化：能否用位运算或一个整数来表示数字签名？进阶思路：我们可以用一个32位整数的低30位（或10个3位组）来分别表示数字0-9出现的次数（因为2^29<10^9，所以每位数字最多出现9次，3位二进制足够表示0-7，但9需要4位）。这样，每个签名就是一个整数，比较两个签名是否相等就是比较两个整数，速度极快。但这属于过度优化（Over-optimization），在面试中除非面试官引导，否则不必主动提出，因为它牺牲了代码的可读性。

问题3：我的代码在处理像n=1这样的简单用例时是对的，但提交后有些测试用例失败。排查步骤：

1. 检查预处理范围：确认你的循环条件是否正确包含了所有<=10^9的2的幂。最容易出错的是循环条件写成power < 10**9，这会导致536870912(2^29) 被漏掉。
2. 检查签名计算函数：特别是边界情况。对于n=0（虽然题目规定n>=1，但自己测试时可能用到），你的count_digits函数或字符串处理是否能正确返回？例如，在计数数组法中，while num > 0的循环对于num=0会直接跳过，导致返回全0的元组，这与2^0=1的签名(1,0,0,...)不同。这就是为什么我在方法二的代码中加了if sum(cnt)==0的判断（尽管题目用不到）。对于排序字符串法，str(0)得到"0"，排序后是"0"，没有问题。
3. 使用内置调试或打印日志：对于出错的特定测试用例，将输入的n、计算出的n_signature以及power_of_2_signatures集合的内容打印出来，进行肉眼比对。这是最直接的调试方法。

问题4：在Java/C++等语言中，如何表示“签名”作为集合的键？解答：

• 排序字符串法：通用性最好。将整数转为字符串（String/std::string），排序后作为键。在Java中，可以使用HashSet<String>；在C++中，可以使用std::unordered_set<std::string>。
• 计数数组法：需要将数组转换为可哈希的类型。
  • 在Java中，可以将数组转换为用特定分隔符连接的字符串（如Arrays.toString(count)），或者使用一个自定义对象并重写hashCode()和equals()方法，但前者更简单。
  • 在C++中，可以将数组std::array<int, 10>作为键，因为它支持比较运算符，可用于std::set或std::unordered_set（需要自定义哈希函数）。

7. 从本题延伸的算法思维训练

解完这道题，不应止步于此。我们可以从中提炼出更通用的算法思维模式：

1. 特征提取与匹配：当问题涉及到“是否可以通过重组/变换得到目标”时，思考能否提取一个与顺序无关的、唯一的特征（指纹）。字符串的字母计数（用于变位词判断）、图的同构判断（使用度数序列等）都运用了类似思想。
2. 预处理与缓存：当目标集合是有限的、已知的时，提前计算并缓存它们的特征，可以将每次查询的复杂度从与目标集大小相关降低到常数时间。这是提高系统响应速度的常见手段。
3. 暴力法的替代方案：面对排列、组合类问题，如果暴力枚举不可行，立即思考：
   • 问题是否有特殊约束（如本题的“2的幂”）？
   • 能否从结果反推条件？
   • 能否将问题转化为等价的、更易解决的形式（如将重排判断转化为特征相等判断）？

我个人在刷题和教学过程中发现，很多同学卡在中等难度题，不是因为不知道数据结构，而是缺乏这种问题转化的能力。这道869题就是一个绝佳的练手题，它用不复杂的场景，深刻地训练了这种核心思维。下次遇到类似“重新排列”、“能否组成”这类题目时，不妨先停下来想想：我能不能为它们定义一个“指纹”？