问题描述
https://leetcode.com/problems/gray-code/
解决思路
https://leetcode-cn.com/problems/gray-code/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by–12/
代码
class Solution {
public List<Integer> grayCode(int n) {
List<Integer> gray = new ArrayList<>();
//initialize the list
gray.add(0);
for(int i = 0; i < n; i++){
int addNum = 1 << i;
//traverse the list reversely
for(int j = gray.size() - 1; j >= 0; j--){
gray.add(gray.get(j) + addNum);
}
}
return gray;
}
}
复杂度分析
- 时间复杂度：O(2^n)
- 空间复杂度：O(n)
