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
00 - 0 [0,1,3,2]
. Its gray code sequence is:01 - 1
11 - 3
10 - 2
解题思路:
F(n) = F(n-1) + (F(n-1) in reverse order) + 1<<(n-1)
n个数的greycode等于 n-1的greycode再加上把greycode反序各自在第1位加个1
public ListgrayCode(int n) { List res = new ArrayList (); res.add(0); for(int i = 1; i <= n; i++){ int j = res.size(); int k = 1<<(i-1); while(j > 0){ res.add(res.get(j-1) + k); j--; } } return res; }
No comments:
Post a Comment