LC 869. 重新排序得到 2 的幂

题目描述

这是 LeetCode 上的 869. 重新排序得到 2 的幂 ，难度为 中等。

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

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

示例 1：

输入：1

输出：true

示例 2：

输入：10

输出：false

示例 3：

输入：16

输出：true

示例 4：

输入：24

输出：false

示例 5：

输入：46

输出：true

提示：
$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(\log{n})$；重排的复杂度为 $O((\log{n})!)$，判断是否为 $2$ 的幂的复杂度为 $O(1)$。整体复杂度为 $O((\log{n})!)$。
• 空间复杂度：$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$。

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.869 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。