Thursday, September 27, 2012

[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

解题思路:
F(n) = F(n-1) + (F(n-1) in reverse order) + 1<<(n-1)

n个数的greycode等于 n-1的greycode再加上把greycode反序各自在第1位加个1





 public List grayCode(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