题目描述

给一个数，问他每位上的数重新排序后是否可以为2的幂 (无前导零)

样例

46
Output: true

算法1

(哈希hash) $O(n)$

由于数据范围是0 ~ 10^9. 最多有8个重复，所以可以哈希直接数数(如果>10^9就要用哈希表存了)。如果是2的幂，0 1 2 3 4 5 6 7 8 9数量就会一一对应.
范围大概是0~ 2^32。等式两边同时取hash: 哈希规则定义: 数数字出现的次数。
counter(1 << i) == counter(N)

C++ 代码

class Solution {
public:
    // 逻辑是哈希hash N和 2^n。 在N比10位小的时候一一对应成立.
    bool reorderedPowerOf2(int N) {
        long c = counter(N);
        for (int i = 0; i < 32; i ++)
            if (counter(1 << i) == c) return true;
        // counter(1<<i)即counter(power of 2), 从2^0 比到2^32位中对应10进制的0 1 2 3 4 5 6 7 8 9的数量
        return false;
    }
    // 数0 1 2 3 4 5 6 7 8 9的个数
    long counter(int N){
        long res = 0;
        for (; N; N /= 10)
            res += pow(10, N % 10);
        return res;
    }
};

Python

def reorderedPowerOf2(self, N: int) -> bool:
    c = collections.Counter(str(N))
    return any(c == collections.Counter(str(1 << i)) for i in range(32))

或

return sorted(str(N)) in [sorted(str(1 << i)) for i in range(30)]

The key is to convert the number into sorted string. Since there are only 32 power of 2 in the given range, we just need to put them in a hash map and do the string match.

把数放进按顺序排好序的string里。 看范围只需2^32，(2进制里32位)所以只需要把这32位放入哈希表中，然后看是否和string匹配。(匹配就是说可以是2的幂)
因为两边都是按同种规则改变顺序的，所以逆离散(?逆运算构造10进制（既然10进制可以那其他正整数进制也一样，复数没分析过，不过应该不需要考虑）时)时，值的等价关系也是一致的(继承).