869. Reordered Power of 2

好不容易總算等到一題不會複雜到懶得寫，又不會簡單到不屑寫的題目了。不知道為什麼難度被歸在medium，好吧我承認一開始有誤會題意導致第一個submit被WA，下次看到簡單的題目真的不要腦衝，把題意看清楚再動手，戒之慎之

題目要求輸入任意數n，n的每一位數可以任意排列(除了把0放在首位)，如果n可以成為2的指數返回true，否則返回false

很直覺的想法就是把所有可能範圍內的2的指數和輸入的n拆解成array存到set裡，然後比對一下就行了

拆解的方法就是把數字除以10取餘數，除到商數為零即可，因為最後要放到set裡，如果vector裡的數字順序不一樣可能會被視為不同的key，所以先對vector的內容進行排序

1
2
3
4
5
6
7

vector<int> disect(int i) {
    vector<int> res;
    for (int j = i; j > 0; j /= 10)
        res.push_back(j % 10);
    sort(res.begin(), res.end());
    return res;
}

因為題目限制輸入的n值範圍為 \( 1 <= n <= 10^9 \)，所以對範圍內所有2的指數建立set，i <<= 1 其實就是 i *= 2 的意思，老梗。最後用 std::set 的 find() 尋找相同位數的vector，找得到就 true，反之 false，收工

1
2
3
4
5
6
7

set<vector<int>> pool;
bool reorderedPowerOf2(int n) {
    for (int i = 1; i < 1e9; i <<= 1)
        pool.insert(disect(i));

    return pool.find(disect(n)) != pool.end();
}

這code如果直接submit，測完時間大概在10ms上下，直覺應該是disect()直接返回vector<int>的緣故，如果修改為

1
2
3
4
5

void disect(int i, vector<int>& v) {
    for (int j = i; j > 0; j /= 10)
        v.push_back(j % 10);
    sort(v.begin(), v.end());
}

則一舉降為3ms，物件拷貝真的是代價不斐，翻了一下Discuss發現好多宣稱0ms，結果作法大同小異，leetcode的judge真的很謎啊