LeetCode 题解工作台
重新排序得到 2 的幂
给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。 如果我们可以通过上述方式得到 2 的幂，返回 true ；否则，返回 false 。 示例 1： 输入： n = 1 输出： true 示例 2： 输入： n = 10 输出： false 提示： 1 9
5
题型
6
代码语言
3
相关题
当前训练重点
中等 · 哈希·数学
答案摘要
我们可以在 $[1, 10^9]$ 的范围内枚举所有的 的幂，判断它们的数字组成是否与给定的数字相同。 定义一个函数 ，表示数字 的数字组成。我们可以将数字 转换为一个长度为 的数组，或者一个按数字大小排序的字符串。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·数学 题型思路
题目描述
给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例 1：
输入：n = 1 输出：true
示例 2：
输入：n = 10 输出：false
提示：
1 <= n <= 109
解题思路
方法一：枚举
我们可以在 的范围内枚举所有的 的幂，判断它们的数字组成是否与给定的数字相同。
定义一个函数 ，表示数字 的数字组成。我们可以将数字 转换为一个长度为 的数组，或者一个按数字大小排序的字符串。
首先，我们计算给定数字 的数字组成 。然后，我们枚举 从 1 开始，每次将 左移一位（相当于乘以 ），直到 超过 。对于每个 ，我们计算它的数字组成，并与 进行比较。如果相同，则返回 ；如果枚举结束仍未找到相同的数字组成，则返回 。
时间复杂度 ，空间复杂度 。其中 是本题的输入范围上限 。
class Solution:
def reorderedPowerOf2(self, n: int) -> bool:
def f(x: int) -> List[int]:
cnt = [0] * 10
while x:
x, v = divmod(x, 10)
cnt[v] += 1
return cnt
target = f(n)
i = 1
while i <= 10**9:
if f(i) == target:
return True
i <<= 1
return False
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of powers of two up to 10^9 and comparing digit counts, roughly O(log n). Space complexity is O(log n) for storing precomputed hash sets of digit counts. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ask if brute-force permutations are required or if a counting method is possible.
- question_mark
Check if candidate optimizations use digit frequency maps rather than full sorting or permutation generation.
- question_mark
Probe understanding of why hashing digit counts improves performance over naive checking.
常见陷阱
外企场景- error
Failing to precompute powers of two and checking all permutations leads to timeouts.
- error
Ignoring leading zero constraints results in incorrect matches.
- error
Not comparing digit counts properly can cause false negatives even if a valid rearrangement exists.
进阶变体
外企场景- arrow_right_alt
Determine if digits can form any perfect square instead of a power of two.
- arrow_right_alt
Return all powers of two that can be formed by rearranging the digits of n.
- arrow_right_alt
Check the same property for numbers with a fixed number of digits rather than the input's length.