LeetCode刷题【89】格雷编码

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：

• 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同 ，且
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

 

示例 1：

输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

示例 2：

输入：n = 1
输出：[0,1]

 

提示：

• 1 <= n <= 16

找规律想方法，找到对称关系

试着先从头开始写几行数据看下吧

   0
   0    1
  00   01   11   10
 000  001  011  010  110  111  101  100
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

1. 只有0的时候，不明显，继续往下看，只有第二行也一样
2. 第三行，我们先把数字都扩充到2位，之前的变成00, 01，那么剩下的只有11, 10 了此时只有 00 01 11 10这个顺序了，其他的组合情况暂不考虑
3. 第三行依旧扩充到3位000 001 011 010 ，下一个数字要和010只有一位不同的话只能选择110了，再下一位依旧只能111，这样 101 100
4. 开始总结规律，可以看到后半部分都是1xx这样的数据了，且如果户管最高位的话，和前面的内容是对称的，即，下标i和下标n - i对应，且下标i的值加1xx(二进制数)等于下标n - i 的值，那么我们基本就总结出规律了
5. 看第四行，原本前8位数字整体原封不动的保留，同时对应后面对称位置的值为当前位置的值加1000(二进制数)

稍微总结下

这个怎么来理解关系呢？我们来缕下 假设数组长度为 2n，（n不等于0，指实际位置从1开始，不是指从0开始的下标）

1. 从对称的最中间两位开始看，也就是第 n和n+1位，这两个数字后面部分是完全一样的，只有头部第一位一个是1 一个是0的区别，相差一位
2. 再看n-1 和n+2这两个对称位置，拿上面的第四行数据中间部分来说明
   0101 0100 1100 1101
   对应数字为0101和 1101, 因为0101和后面一位0100相差一位，所以同样对称部分的1100和1101如果忽略头部的1的话和这边其实是一致的也是相差一位，而又因为这两者头部都是加的1是相同的，所以这两者是必然相差一位的即n+1与n+2相差的一位是和n-1与n相差的一位是一样的
3. 再往后更多的对称部分和这一步也一样可以推断出是相差一位的

代码

class Solution {
    public List<Integer> grayCode(int n) {
        int i = 0;
        int[] list1 = new int[1];
        int[] list2 = new int[2];
        while (++i <=n){
            list2 = new int[1<<i];
            int lastIdx = list1.length * 2 - 1;
            int plus = 1 << (i-1);
            for (int idx = 0; idx < list1.length; idx++) {
                list2[idx] = list1[idx];
                list2[lastIdx - idx] =  list1[idx] | plus ;
            }
            list1 = list2;
        }
        List<Integer> r = new ArrayList<>();
        for (int i1 : list2) {
            r.add(i1);
        }
        return r;
    }
}