1. 项目概述从一道题看算法思维的深度今天想和大家深入聊聊LeetCode上的第869题——“重新排序得到 2 的幂”。乍一看这个标题可能很多朋友会觉得这又是一道关于数字或位运算的简单题。确实它的标签是“中等”难度题目描述也极其简洁给定一个正整数n我们可以通过重新排列其数字可以包含前导零来得到另一个数字。如果这个新数字是 2 的幂则返回true否则返回false。例如n1返回truen10返回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}。基于这个观察我们可以将原问题转化为一个模式匹配问题预处理阶段生成所有在给定数据范围内比如n是32位整数的 2 的幂。对于每个 2 的幂计算其“数字签名”Digital Signature或“数字指纹”。这个指纹就是其十进制表示中每个数字0-9出现的次数。对于输入的n同样计算其数字指纹。最后只需检查n的数字指纹是否存在于所有 2 的幂的数字指纹集合中。存在则返回true否则返回false。这种思路将问题从“排列组合幂判断”的O(L!)复杂度降低到了“计算指纹集合查找”的O(L K)复杂度K是2的幂的个数这是一个质的飞跃。2.1 方案选型背后的考量为什么选择“数字指纹”对比法而不是其他方法比如为什么不直接对n的字符数组排序然后和排序后的 2 的幂字符串比较实际上排序对比法是完全可行的也是很多解法的实现方式之一。但“数字指纹”法在概念上更清晰并且为后续可能的优化如使用位运算压缩指纹留下了空间。排序法的核心逻辑是如果两个数字是数字重排关系那么它们排序后的字符串一定相等。例如46排序后是4664排序后也是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 边界条件与特殊输入处理输入为11本身就是 2 的幂 (2^0)应返回true。我们的算法能正确处理因为1的指纹会在预处理集合中。输入包含数字0例如n1024。算法会计算“1024”的指纹包含1个‘1’1个‘0’1个‘2’1个‘4’然后与2^101024的指纹匹配返回true。包含零不会影响指纹的计算和比较。大数输入例如n9999999999个9。算法会计算其指纹9个‘9’然后与所有30个2的幂的指纹比较无一匹配返回false。这个过程是高效的。前导零问题正如之前强调的我们不需要也不应该试图生成带有前导零的重排数字。例如n10其排序后字符串是“01”对应的数字是1。我们只需检查“01”是否等于某个2的幂排序后的字符串。2^01排序后是“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代码解析power_of_2_signatures set(): 使用集合set来存储所有2的幂的签名因为集合的in操作平均时间复杂度是O(1)非常高效。while power 10**9: 循环生成所有不超过10^9的2的幂。从1(2^0) 开始。signature .join(sorted(str(power))): 这是核心操作。str(power)将数字转为字符串sorted(...)对字符串中的字符进行排序返回一个字符列表.join(...)再将列表拼接回字符串。例如power46得到46power64也得到46。power 1: 用左移一位来实现乘以2这是位运算通常比直接乘法*2稍快也更符合“2的幂”这个语境。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的特殊情况虽然题目n1但2的幂有1其循环会直接跳过 if sum(cnt) 0: # 实际上当输入n0时才会触发但题目范围n1此分支仅用于完整性 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代码解析count_digits函数通过不断取模% 10和整除// 10来分解数字统计每位数字。这种方式比先转字符串再遍历在极致的性能追求下可能有一丝优势但代码稍复杂。返回tuple(cnt)将列表转换为元组使其可哈希hashable才能放入set中。主逻辑与方法一完全一致只是比较的对象从排序后的字符串变成了数字计数元组。实操心得在面试或竞赛中方法一排序字符串法通常是首选。它实现简单不易出错可读性极高并且性能完全满足要求。只有在面试官明确追问“能否不用排序”时再引出方法二。先给出最清晰、最可靠的解法永远是上策。5. 复杂度分析与算法评价时间复杂度设n的十进制位数为L2的幂的个数为K本题中K30。预处理阶段需要计算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^2910^9所以每位数字最多出现9次3位二进制足够表示0-7但9需要4位。这样每个签名就是一个整数比较两个签名是否相等就是比较两个整数速度极快。但这属于过度优化Over-optimization在面试中除非面试官引导否则不必主动提出因为它牺牲了代码的可读性。问题3我的代码在处理像n1这样的简单用例时是对的但提交后有些测试用例失败。排查步骤检查预处理范围确认你的循环条件是否正确包含了所有10^9的2的幂。最容易出错的是循环条件写成power 10**9这会导致536870912(2^29) 被漏掉。检查签名计算函数特别是边界情况。对于n0虽然题目规定n1但自己测试时可能用到你的count_digits函数或字符串处理是否能正确返回例如在计数数组法中while num 0的循环对于num0会直接跳过导致返回全0的元组这与2^01的签名(1,0,0,...)不同。这就是为什么我在方法二的代码中加了if sum(cnt)0的判断尽管题目用不到。对于排序字符串法str(0)得到0排序后是0没有问题。使用内置调试或打印日志对于出错的特定测试用例将输入的n、计算出的n_signature以及power_of_2_signatures集合的内容打印出来进行肉眼比对。这是最直接的调试方法。问题4在Java/C等语言中如何表示“签名”作为集合的键解答排序字符串法通用性最好。将整数转为字符串String/std::string排序后作为键。在Java中可以使用HashSetString在C中可以使用std::unordered_setstd::string。计数数组法需要将数组转换为可哈希的类型。在Java中可以将数组转换为用特定分隔符连接的字符串如Arrays.toString(count)或者使用一个自定义对象并重写hashCode()和equals()方法但前者更简单。在C中可以将数组std::arrayint, 10作为键因为它支持比较运算符可用于std::set或std::unordered_set需要自定义哈希函数。7. 从本题延伸的算法思维训练解完这道题不应止步于此。我们可以从中提炼出更通用的算法思维模式特征提取与匹配当问题涉及到“是否可以通过重组/变换得到目标”时思考能否提取一个与顺序无关的、唯一的特征指纹。字符串的字母计数用于变位词判断、图的同构判断使用度数序列等都运用了类似思想。预处理与缓存当目标集合是有限的、已知的时提前计算并缓存它们的特征可以将每次查询的复杂度从与目标集大小相关降低到常数时间。这是提高系统响应速度的常见手段。暴力法的替代方案面对排列、组合类问题如果暴力枚举不可行立即思考问题是否有特殊约束如本题的“2的幂”能否从结果反推条件能否将问题转化为等价的、更易解决的形式如将重排判断转化为特征相等判断我个人在刷题和教学过程中发现很多同学卡在中等难度题不是因为不知道数据结构而是缺乏这种问题转化的能力。这道869题就是一个绝佳的练手题它用不复杂的场景深刻地训练了这种核心思维。下次遇到类似“重新排列”、“能否组成”这类题目时不妨先停下来想想我能不能为它们定义一个“指纹”