重排为2的幂

reordered power of 2

词频统计

统计十进制下每个数字，判断是否与某一2的幂次一样即可。

class Solution {
public:
    bool check(vector<int> &num, long n) {
        vector<int> v(10);
        while(n > 0) {
            v[n % 10]++;
            n /= 10;
        }
        for(int i = 0; i < 10; i++) {
            if(v[i] != num[i]) return false;
        }
        return true;
    }

    bool reorderedPowerOf2(int n) {
        vector<int> num(10);
        while(n > 0) {
            num[n % 10]++;
            n /= 10;
        }
        for(int i = 0; i < 30; i++) {
            if(check(num, (1l << i))) return true;
        }
        return false;
    }
};

排列组合

按照题意对所有排列依次检查。

• c++风格的排列：remain数组不要用substr等，可以用vis数组。
• 是否为二的幂次，二进制表示下只有一个1：(n & (n-1)) == 0

class Solution {
public:
    bool check(int n) {
        return (n & (n - 1)) == 0;
    }

    bool reorderedPowerOf2(int n) {
        string s = to_string(n);
        vector<int> v(s.size(), 0);
        bool flag = false;
        function<void(int, int)> perm = [&](int i, int x){
            if (flag) return;
            else if (i == s.size()) {
                flag = check(x);
            } else {
                for (int j = 0; j < s.size(); j++) {
                    if (v[j] == 0) {
                        if (x == 0 && s[j] == '0') continue;
                        v[j] = 1;
                        perm(i + 1, x * 10 + s[j] - '0');
                        v[j] = 0;
                    }
                }
            }
        };
        perm(0, 0);
        return flag;
    }
};