这道题目可以用普通的循环来做,也可以用动态规划来做,相比起来动态规划的思路更加清晰,代码逻辑更加紧密。
当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; } };