LeetCode | Gray Code

题目

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.

在不知道格雷码编解码公式时，可以这样考虑，每增加一位，就相当于在原来数组的基础上做如下操作：将原来数组翻转并在每个数字前加1（二进制），并拼接到原数组后面（解法1）。

参考http://en.wikipedia.org/wiki/Gray_code可以知道格雷码的编解码公式，依此写出转换代码（解法2）。

解法1

import java.util.ArrayList;

public class GrayCode {
	public ArrayList<Integer> grayCode(int n) {
		ArrayList<Integer> results = new ArrayList<Integer>();
		results.add(0);
		for (int i = 1; i <= n; ++i) {
			int plus = 1 << (i - 1);
			int N = results.size();
			for (int j = N - 1; j >= 0; --j) {
				results.add(results.get(j) + plus);
			}
		}
		return results;
	}
}

import java.util.ArrayList;

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

LeetCode | Gray Code,布布扣,bubuko.com

LeetCode | Gray Code

原文：http://blog.csdn.net/perfect8886/article/details/20577909