原文链接: https://leetcode-cn.com/problems/reordered-power-of-2

英文原文

You are given an integer n. We reorder the digits in any order (including the original order) such that the leading digit is not zero.

Return true if and only if we can do this so that the resulting number is a power of two.

 

Example 1:

Input: n = 1
Output: true

Example 2:

Input: n = 10
Output: false

Example 3:

Input: n = 16
Output: true

Example 4:

Input: n = 24
Output: false

Example 5:

Input: n = 46
Output: true

 

Constraints:

• 1 <= n <= 109

中文题目

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

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

 

示例 1：

输入：1
输出：true

示例 2：

输入：10
输出：false

示例 3：

输入：16
输出：true

示例 4：

输入：24
输出：false

示例 5：

输入：46
输出：true

 

提示：

1. 1 <= N <= 10^9

通过代码

高赞题解

打表 + DFS

一个朴素的做法是对 $n$ 进行重排，然后检查重排后的数值是否属于 $2$ 的幂。

由于 $2$ 的幂数固定，我们可以先通过「打表」将范围落在 $[1, 1e9]$ 以内的 $2$ 的幂预处理出来，这样我们可以在 $O(1)$ 的复杂度内判断某个数是否为 $2$ 的幂。

重排的过程则是 DFS 实现。

代码：

[]
class Solution {
    static Set<Integer> set = new HashSet<>();
    static {
        for (int i = 1; i < (int)1e9+10; i *= 2) set.add(i);
    }
    int m;
    int[] cnts = new int[10];
    public boolean reorderedPowerOf2(int n) {
        while (n != 0) {
            cnts[n % 10]++;
            n /= 10;
            m++;
        }
        return dfs(0, 0);
    }
    boolean dfs(int u, int cur) {
        if (u == m) return set.contains(cur);
        for (int i = 0; i < 10; i++) {
            if (cnts[i] != 0) {
                cnts[i]--;
                if ((i != 0 || cur != 0) && dfs(u + 1, cur * 10 + i)) return true;
                cnts[i]++;
            }
        }
        return false;
    }
}

• 时间复杂度：打表预处理所有 $2$ 的幂放到本地运行为 $O(1)$，放到 $OJ$ 运行则是 $O(C)$，$C$ 为常数，约为 $30$。处理出 $cnts$ 数组的复杂度为 $O(\left \lfloor \log_{10}{n} \right \rfloor + 1)$；重排的复杂度为 $O((\left \lfloor \log_{10}{n} \right \rfloor + 1)!)$，判断是否为 $2$ 的幂的复杂度为 $O(1)$。整体复杂度为 $O((\left \lfloor \log_{10}{n} \right \rfloor + 1)!)$。
• 空间复杂度：$O(C)$，其中 $C$ 为常数，约为 $40$。

---

打表 + 词频统计

解法一，我们发现复杂度上界取决于对 $n$ 的重排，同时数据范围内的 $2$ 的幂数量很少。

因此有效降低复杂度（避免重排）的做法是，直接枚举所有的 $2$ 的幂 $x$，检查 $x$ 的词频是否与 $n$ 相同。

代码：

[]
class Solution {
    static Set<Integer> set = new HashSet<>();
    static {
        for (int i = 1; i < (int)1e9+10; i *= 2) set.add(i);
    }
    public boolean reorderedPowerOf2(int n) {
        int[] cnts = new int[10];
        while (n != 0) {
            cnts[n % 10]++;
            n /= 10;
        }
        int[] cur = new int[10];
        out:for (int x : set) {
            Arrays.fill(cur, 0);
            while (x != 0) {
                cur[x % 10]++;
                x /= 10;
            }
            for (int i = 0; i < 10; i++) {
                if (cur[i] != cnts[i]) continue out;
            }
            return true;
        }
        return false;
    }
}

• 时间复杂度：打表预处理所有 $2$ 的幂放到本地运行为 $O(1)$，放到 $OJ$ 运行则是 $O(C)$，$C$ 为常数，约为 $30$。检查所有 $2$ 的幂的词频是否与 $n$ 词频相同复杂度为 $O(C * \log{n})$。整体复杂度为 $O(C * \log{n})$。
• 空间复杂度：$O(C)$，其中 $C$ 为常数，约为 $40$。

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
32663	50813	64.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言