这道题目可以用普通的循环来做,也可以用动态规划来做,相比起来动态规划的思路更加清晰,代码逻辑更加紧密。

当n为1时,输出0,1,n为2时,输出00,01,11,10,当n为3时,输出00,01,11,10,110,111,101,100

规律:11,10是在1,0高位上+1得到;110,111,101,100是在10,11,01,00高位上+1得到,代码如下:

//
// Created by jt on 2020/8/25.
//
class Solution {
public:
    /**
     *
     * @param n int整型
     * @return int整型vector
     */
    vector<int> grayCode(int n) {
        // write code here
        vector<int> res(1, 0);
        for (int i = 0; i < n; ++i) {
            int topBit = 1 << i;
            for (int j = res.size() - 1; j >= 0; --j) {
                res.push_back(topBit | res[j]);
            }
        }
        return res;
    }
};