提交结果	执行用时	内存消耗	语言	提交时间	备注
通过	1372 ms	14.8 MB	Python3	2021/10/28 09:23

题目描述：

给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。

如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

示例 1：

输入：1
输出：true
示例 2：

输入：10
输出：false
示例 3：

输入：16
输出：true
示例 4：

输入：24
输出：false
示例 5：

输入：46
输出：true
 

提示：

1 <= N <= 10^9

解题思路：

方法一：搜索回溯 + 位运算
将 nn 的十进制表示视作一个字符数组，我们可以枚举该数组的所有排列，对每个不含前导零的排列判断其对应的整数是否为 22 的幂。

这可以拆分成两个子问题：

枚举可能包含重复字符的数组的全排列，读者可参考「47. 全排列 II」的官方题解；
判断一个整数是否为 22 的幂，读者可参考「231. 2 的幂」的官方题解。
对于本题的具体实现，我们可以在递归搜索全排列的同时，计算出当前排列的已枚举的部分所对应的整数 \textit{num}num。在我们枚举当前排列的下一个字符 \textit{ch}ch 时，将 \textit{ch}ch 加到 \textit{num}num 的末尾，即 num = num * 10 + ch - '0'，然后递归进入下一层。

def isPowerOfTwo(n: int) -> bool:
    return (n & (n - 1)) == 0

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        nums = sorted(list(str(n)))
        m = len(nums)
        vis = [False] * m

        def backtrack(idx: int, num: int) -> bool:
            if idx == m:
                return isPowerOfTwo(num)
            for i, ch in enumerate(nums):
                # 不能有前导零
                if (num == 0 and ch == '0') or vis[i] or (i > 0 and not vis[i - 1] and ch == nums[i - 1]):
                    continue
                vis[i] = True
                if backtrack(idx + 1, num * 10 + ord(ch) - ord('0')):
                    return True
                vis[i] = False
            return False

        return backtrack(0, 0)

方法二：预处理 + 哈希表
由于我们可以按任何顺序将数字重新排序，因此对于两个不同的整数 aa 和 bb，如果其十进制表示的字符数组，从小到大排序后的结果是相同的，那么若 aa 能够重排得到 22 的幂，bb 也可以；若 aa 不能重排得到 22 的幂，那么 bb 也不能。

进一步地，只要 aa 和 bb 的十进制表示的字符数组中，从 \texttt{0}0 到 \texttt{9}9 每个字符的出现次数，在 aa 和 bb 中都是一样的，那么 aa 和 bb 能否重排得到 22 的幂的结果是一样的。

def countDigits(n: int) -> Tuple[int]:
    cnt = [0] * 10
    while n:
        cnt[n % 10] += 1
        n //= 10
    return tuple(cnt)

powerOf2Digits = {countDigits(1 << i) for i in range(30)}

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        return countDigits(n) in powerOf2Digits