p89

发表于 | 分类于 |

LeetCode p89 Gray Code 题解

1.题目：

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

题意：

输入一个数字，就给你这么多位的空间。每位上放上0或者1，组成一个二进制数。相邻两个二进制数中间只能有一个位置上的数不同。从0开始，按顺序输出所有的书。
以2为例的话应该是00 01 11 10 对应的数是0 1 3 2

2.解题思路:

每次只能动一个位置，则当n从2变为3时，就多了一个最高位为1.即 00 01 11 10 先化成 000 001 011 010 值不变再加上 100 101 111 110
又按照规则，应该采用一种对称排列的策略：000 001 011 010 （对称轴） 110 111 101 100
可以发现以对称轴为中心每个值都比它的对称点多2的（n-1)次方。这就是递归的规律。

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<Integer>();
		if (n == 0) {
			ans.add(0);
			return ans;
		}
		if (n == 1) {
			ans.add(0);
			ans.add(1);
			return ans;
		}
		ans = grayCode(n - 1);
		int len = ans.size();
		for (int i = len - 1; i > -1; i--) {
			ans.add((int) (ans.get(i) + Math.pow(2, n - 1)));
		}
		return ans;
    }
}

4.一些总结：