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

题解： 想到了一个好方案，就是预处理出2的30次方以内每个数中各个数字的个数，然后将输入的值进行比较。这里使用了multiset，其实map也是可以搞定的。

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        if(n == 1) return true;
        multiset<int> now;
        //处理输入的数字
        while(n > 0){
            //cout<<n % 10<<endl;
            now.insert(n % 10);
            n /= 10;
        }
        
        //预处理出2^30以内的2的幂中包含的数字
        long long cheng = 1;
        for(int i = 0; i < 30; i++){
            cheng *= 2;
            long long tmp = cheng;
            multiset<int> ind;
            while(tmp > 0){
                ind.insert(tmp % 10);
                tmp /= 10;
            }
            if(now == ind) return true;
        }

        return false;
    }
};

还有一种方案是采用搜索回溯+位运算。

class Solution {
    vector<int> vis;

    bool isPowerOfTwo(int n) {
        return (n & (n - 1)) == 0;
    }

    bool backtrack(string &nums, int idx, int num) {
        if (idx == nums.length()) {
            return isPowerOfTwo(num);
        }
        for (int i = 0; i < nums.length(); ++i) {
            // 不能有前导零
            if ((num == 0 && nums[i] == '0') || vis[i] || (i > 0 && !vis[i - 1] && nums[i] == nums[i - 1])) {
                continue;
            }
            vis[i] = 1;
            if (backtrack(nums, idx + 1, num * 10 + nums[i] - '0')) {
                return true;
            }
            vis[i] = 0;
        }
        return false;
    }

public:
    bool reorderedPowerOf2(int n) {
        string nums = to_string(n);
        sort(nums.begin(), nums.end());
        vis.resize(nums.length());
        return backtrack(nums, 0, 0);
    }
};