难度: Medium
给定正整数 n ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
示例 1：
输入：n = 1 输出：true
示例 2：
输入：n = 10 输出：false
提示：
1 <= n <= 109
Submission
运行时间: 27 ms
内存: 16.0 MB
class Solution:
def reorderedPowerOf2(self, n: int) -> bool:
# Convert n to string and sort its characters
n_str = str(n)
n_sorted = sorted(n_str)
# Generate all powers of 2 up to 2^30 and sort their characters
powers_of_2 = [str(2**i) for i in range(31)]
powers_sorted = [sorted(pow_str) for pow_str in powers_of_2]
# Check if the sorted characters of n match any sorted power of 2
return n_sorted in powers_sorted
Explain
该题解的思路是将给定的整数 n 转换为字符串，并对其字符进行排序。然后生成从 2^0 到 2^30 的所有 2 的幂，并对每个幂的字符进行排序。最后，检查排序后的 n 的字符是否与任何排序后的 2 的幂的字符相匹配。如果匹配，则返回 True，否则返回 False。
时间复杂度: O(m log m)，其中 m 是整数 n 的位数。
空间复杂度: O(1)
class Solution:
def reorderedPowerOf2(self, n: int) -> bool:
# 将整数 n 转换为字符串并对其字符进行排序
n_str = str(n)
n_sorted = sorted(n_str)
# 生成从 2^0 到 2^30 的所有 2 的幂，并对每个幂的字符进行排序
powers_of_2 = [str(2**i) for i in range(31)]
powers_sorted = [sorted(pow_str) for pow_str in powers_of_2]
# 检查排序后的 n 的字符是否与任何排序后的 2 的幂的字符相匹配
return n_sorted in powers_sorted
Explore
选择2^0到2^30的范围是因为这个范围足以覆盖所有32位整数的可能值。2^30是1073741824，略大于10^9，而32位整数的最大值是2147483647。因此，这个范围确保了所有可能的10位数或更少位数的数字都被覆盖。这个范围确实覆盖了所有可能的n值，因为在这个范围内的2的幂已经包括了所有位数可能的排列形式。
在这个算法中，通过对数字的字符进行排序来比较，实际上已经考虑了数字重复导致的多种排列情况。排序操作将数字的所有字符按照字典序排列，因此不同的排列方式如果拥有相同的字符集合，则排序后的结果将是相同的。这意味着即使数字中的某些字符重复，排序后的相等性检查仍然有效。
使用字符串排序的方法是因为它简单且易于实现。这种方法通过将数字转换为字符串，然后对字符进行排序，可以直接比较两个数字是否具有相同的字符组合，而不必考虑它们的原始顺序。这种方法避免了需要考虑所有可能的字符排列组合，从而提高了算法的效率。其他方法如生成所有可能的排列则计算量大得多，效率较低。
在这个算法中，输入数字首先被转换为字符串，如果数字中包含前导零（例如格式化或某些形式的输入错误），这些零会在转换为字符串后存在。然而，由于算法涉及到对字符串的字符进行排序，排序操作会将所有字符（包括零）按照字典序重新排列。因此，前导零在排序后的结果中不会以前导形式出现，从而不影响最终的比较。例如，'100'排序后变为'001'，进一步排序变为'010'，这与'2^3=8'（排序后为'008'或'080'或'800'）不匹配。