Gray Code

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.

Naive Way: 有这样一个想法，从0000开始，先做镜像（倒着取），得到0000，然后第一位与mask=1或运算，就是0001，然后加入list中。不断从list中倒着取，然后和新的mask取或，每次把mask进一位。

算法复杂度O(2^n)

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> list = new ArrayList<Integer>();
        int mask = 1, i = 1;
        list.add(0);
        while(i <= n){
            int k = list.size();
            for(int j = k-1;j >=0;j--){
                int t = list.get(j) | mask;
                list.add(t);
            }
            mask <<= 1;
            i++;
        }
        return list;
    }
}


还有一个方法，是我第一次做的方法，相当于用数学运算求镜像。

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> lst= new ArrayList<Integer>();
        // base case
        lst.add(0);
        
        // iteration
        for(int i = 1;i < Math.pow(2,n);i++){
            int level = (int)Math.floor(Math.log(i)/Math.log(2));
            int cur_index = (int)Math.pow(2,level)+lst.get((int)Math.pow(2,level+1)-1-i);
            lst.add(cur_index);
        }
        return lst;
    }
}

 

Improved Way: 最厉害的方法，G(i) = i^(i/2)。来自leetcode 用户 jinrf 

wiki上的说法是G(i) = i ^ (i >> 1)



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