89. Gray Code

1.問題

2.想法

• 提問

  • 確認題意: 相鄰的element只會差異一個bit, 因此如果DFS的方式順序不對

• function header, parameter

• test input

• 說明想法

  • 每次double容器中的元素, 因此n回後, 容器的元素數目為2 ^ n

  • 每回合會反向改變固定bit的值

• 測試計算複雜度

3.程式碼

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> res;
        //2的次方為1, n=0時, res也會有一個element
        res.push_back(0);
        
        //每次讓res中elememt的元素double
        for (int i = 0; i < n; i++) {
            int size = res.size();
            //同一回合中, 對每個res中的element都只改變同一個bit
            for (int j = size - 1; j >= 0; j--) {
                res.push_back(res[j] | 1 << i);
            }
        }
        
        return res;
    }
};