原题
格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。
示例 1:
输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2
对于给定的 n，其格雷编码序列并不唯一。
例如，[0,2,3,1] 也是一个有效的格雷编码序列。
00 - 0
10 - 2
11 - 3
01 - 1示例 2:
输入:?0
输出:?[0]
解释: 我们定义格雷编码序列必须以 0 开头。
? 给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
? 因此，当 n = 0 时，其格雷编码序列为 [0]。原题url：https://leetcode-cn.com/problems/gray-code/
解题
初始想法
一开始拿到这题目，我想到的是从0开始，每次从右边第一位开始改变，放入结果集中（集合），如果添加成功，就以当前数为新的起点，继续变化和添加，否则就变化下一位。
这个想法看似美好，实际有两个需要解决的难点：
- 如何保证转化出的二进制，精确修改每一位呢？如果用 for 循环的话，效率很低。
- 每次这样改变的话，很可能效率会很低，时间复杂度会很高，如何优化？
基于以上两点，我稍微尝试了一下，感觉这个方法不靠谱，决定换一个思路。
找规律
那现在我就来尝试找找规律，自己写写0位、1位、2位、3位的格雷编码：
0位：
0
1位：
0
1
2位：
00
01
11
10
3位：
000
001
011
010
110
111
101
100写完之后，应该能找到以下几个规律：
- 第 n 位格雷编码是第 n+1 位格雷编码的子集，意味着可以利用上一次的结果。
- 根据2进制来看，每多一位，其实就是在多的那一位置1即可。
- 基于第2点，需要做补充，格雷编码是需要考虑顺序的，并不能只是简单置1，应该是针对上一次的结果集倒序输出并在最高位置1。
上面3个规律，只有最后一个规律，可能比较难找，不过考虑到顺序这个特性，应该也能想出来。接下来我们看一下代码：
class Solution {
public List<Integer> grayCode(int n) {
// 动态规划，第n种情况是由：第n-1种正序各数字前加0 + 第n-1种倒序各数字前加1
// 先给出一开始的情况
LinkedList<Integer> list = new LinkedList<>();
list.add(0);
if (n == 0) {
return list;
}
LinkedList<Integer> result = new LinkedList<>();
result.add(0);
// 最高位置1，可以理解为增加
int add = 1;
for (int i = 1; i <= n; i++) {
// 倒序
Collections.reverse(list);
for (int item : list) {
result.add(item + add);
}
list = new LinkedList<>(result);
add = add << 1;
}
return result;
}
}提交OK，执行用时：3 ms，内存消耗：34.5 MB，但是用时只战胜9.59%的 java 提交记录，看来还是有优化必要的。
优化
我第一眼想到的优化是倒序，我并不需要真的将上一次的结果集真的倒置，而是只要倒序遍历即可。因为我存放的结果集是 LinkedList，可以利用它的descendingIterator，直接进行倒序遍历，其代码是：
class Solution {
public List<Integer> grayCode(int n) {
// 动态规划，第n种情况是由：第n-1种正序各数字前加0 + 第n-1种倒序各数字前加1
// 先给出一开始的情况
LinkedList<Integer> list = new LinkedList<>();
list.add(0);
if (n == 0) {
return list;
}
LinkedList<Integer> result = new LinkedList<>();
result.add(0);
int add = 1;
for (int i = 1; i <= n; i++) {
// 倒序
Iterator<Integer> descIterator = list.descendingIterator();
while (descIterator.hasNext()) {
result.add(descIterator.next() + add);
}
list = new LinkedList<>(result);
add = add << 1;
}
return result;
}
}提交OK，执行用时：2 ms，内存消耗：34.3 MB，但是用时只战胜21.07%的 java 提交记录，看来还可以继续优化。
继续优化
这次我盯上的是list = new LinkedList<>(result);，看起来是1行代码，实际内部利用了addAll方法，还是需要遍历这个结果集。而这里需要定义一个新的结果集是为了记录中间结果，是否真的有必要的呢？
如果还是利用 LinkedList 结构，还真就需要新建结果集。因为它想获取中间结果，用get(int index)这样的方法，依旧需要遍历。这时候我就想到，可以换一种数据结构ArrayList，这样无论是倒序遍历还是添加，都是只要记录上一次的总数量，就可以达到同样的效果了。接下来让我们看看代码：
class Solution {
public List<Integer> grayCode(int n) {
// 动态规划，第n种情况是由：第n-1种正序各数字前加0 + 第n-1种倒序各数字前加1
// 先给出一开始的情况
ArrayList<Integer> list = new ArrayList<>(1 << n);
list.add(0);
if (n == 0) {
return list;
}
int add = 1;
int tempCount;
for (int i = 1; i <= n; i++) {
tempCount = list.size();
// 倒序
for (int j = tempCount - 1; j >= 0; j--) {
list.add(2 * tempCount - j - 1, list.get(j) + add);
}
add = add << 1;
}
return list;
}
}提交OK，执行用时：1 ms，内存消耗：34.2 MB，用时战胜了97.89%的 java 提交记录，这下应该可以了。
总结
以上就是这道题目我的解答过程了，不知道大家是否理解了。这道题目的难点主要在于找规律以及之后的优化。
有兴趣的话可以访问我的博客或者关注我的公众号，说不定会有意外的惊喜。
https://death00.github.io/
公众号：健程之道