2021.10.28打卡

869. 重新排序得到 2 的幂

思路：預處理+哈希表

由于我們可以按任意順序對數字進行排序，是以對于兩個不同的整數a和b，如果十進制表示的字元數組，從小到大排序的結果是相同的，那麼若a能夠重排得到2的幂，那麼b也可以；若a不能重排得到2的幂，那麼b也不能。

進一步，隻要a和b的十進制表示的字元數組中，從0到9每個字元的出現次數，在a和b中都是一樣的，那麼a和b能否重排得到2的幂的結果是一樣的。

首先對1到 1 0 9 10^9 109的範圍内的2的幂記錄在哈希表中，之後對數字n處理，判斷數字n對應的字元數組是否在哈希表中。

class Solution {
public:
    unordered_set<string> mp;

    string count(int n){
        string res=string(10,0);
        while(n>0){
            res[n%10]++;
            n/=10;
        }
        return res;
    }

    bool reorderedPowerOf2(int n) {
        for(int i=1;i<=1e9;i<<=1){
            mp.insert(count(i));
        }
        return mp.count(count(n));
    }
};
           

時間複雜度 O(logn)

空間複雜度 O(1)