869.重新排序得到2的幂

题目：869.重新排序得到2的幂

给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

示例：

输入：1
输出：true

输入：10
输出：false

输入：16
输出：true

输入：24
输出：false

输入：46
输出：true

题解：

今天这道题自己没做出来，coding的问题，思路是对的，但是不知道怎么写（就是不会），最后看了三叶姐的题解看明白了，我一开始是想把每个排序都排出来，之后挨个检验是否是2的幂，三叶姐的解法一也是这么做的。
解法一：打表+DFS
首先把所有2的幂，放到set中，之后通过dfs找到所有n的序列，判断该序列在不在set中，如果在就说明有2的幂，如果都不在说明没有，返回false；

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;
    }
}

解法二：打表+词频统计
通过解法一，我们发现复杂度的上届取决于对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;
    }
}

最后附上原题解的链接：宫水三叶