1780. Check if Number is a Sum of Powers of Three

雙周賽複盤

這題我一開始整個卡死, 能想過的我都是過一輪了, 然後用dp錯誤的方式卡了好久, 最後在靈機一動的情況下, 想到我們可以去紀錄0 … n, 然後用backtrace的方式走訪所有可能, 一旦找到一個true變回傳

class Solution {
public:
    bool dfs(vector<int> cur, int i, int target){
        int res = 0;
        for(int k = 0; k < cur.size(); k++){
            res += pow(3, cur[k]);
        }
        if(res == target) return true;
        for(int j = i; j < target;j++){
            cur.push_back(j);
            if(pow(3, j) > target) return false;
            if(dfs(cur, j + 1, target)){
                return true;
            }
            cur.pop_back();
        }
        return false;
    }
    bool checkPowersOfThree(int n) {
        vector<int> cur;
        bool res = dfs(cur, 0, n);
        return res;
    }
};

但這做法做太久了, 看完討論, 發現有一種我完全不知道怎麼想出來的方法

`  bool checkPowersOfThree(int n) {
       while (n > 0) {         
            if (n % 3 == 2)
                return false;   
            n /= 3;            
        }
        return true;
    }

把n換成3進位,

然後位數的長度為1-k

每個位數可以為0, 代表3^k 這個不在

也可以等於1, 代表3 ^k 有一個存在

不能等於2, 因為我們只容許一個3 ^k的存在, 大於就是錯的

用while迴圈, 每次確定完就right shift

這是鬼吧XD