LeetCode-Gray Code

悠悠 2022-08-04 09:19 91阅读 0赞

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return `[0,1,3,2]`. Its gray code sequence is:

00 - 0
    01 - 1
    11 - 3
    10 - 2

Note:  
For a given n, a gray code sequence is not uniquely defined.

For example, `[0,2,3,1]` is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

如果知道gray code的人，可以用很简介的代码搞定，并且关于wiki也有这方面的介绍。但是对于首次接触到gray code的人来说，其实我们只需要归纳总结，发现规律，然后解决之。最简单的办法就是从n=1开始试。

我罗列几个，如下：

n = 1

0  
1

n=2

00  
01  
11  
10

n=3

00 0  
00 1  
01 1  
01 0  
1 1 0  
1 1 1  
1 0 1  
1 0 0

对于n = 2，其实就是在n=1的基础上，加前缀，前半部门为0，后半部分为1，另外低位是对称的，红色的和非红色的。每一半正好是n=1比如，0-1-1-0.

同样的规律可以发现，在n=3时，也同样是n=2的基础上加前缀，低两位是对称的，由此我们就可以层层迭代了。代码如下：

public List<Integer> grayCode(int n) {
            List<Integer> list = new ArrayList<Integer>();
        	list.add(0);
            for (int i = 0; i < n; i++) {
            	int size = list.size();
            	for (int j = 0; j < (1 << i); j++) {
            		list.add(list.get(size-j-1) + (1 << i));
            	}
            }
            return list;
        }

当然如果知道gray code，可以写出更简单的，如 [Gray Code Wiki][]

public List<Integer> grayCode(int n) {
            List<Integer> result = new ArrayList<Integer>();
            for(int i = 0;i < (1<<n); i++) result.add(i^i>>1);
            return result;
        }

[Gray Code Wiki]: https://en.wikipedia.org/wiki/Gray_code#Converting_to_and_from_Gray_code