Gray Code 411

Question

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, find the sequence of gray code. A gray code sequence must begin with 0 and with cover all 2n integers.

Notice

For a given n, a gray code sequence is not uniquely defined.

[0,2,3,1] is also a valid gray code sequence according to the above definition.

Example

Given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0 01 - 1 11 - 3 10 - 2

Challenge

O(2n) time.

Solution

第一种方法：参考维基百科上关于格雷码的性质，有一条是说镜面排列的，n位元的格雷码可以从n-1位元的格雷码以上下镜射后加上新位元的方式快速的得到，如下图所示一般。

根据这条性质，求n位的gray code，可以根据n－1位的gray code来求。只要将n－1位的gray code的答案在前面加一位0以及n－1位的gray code的答案reverse之后全部在前面加一位1即可。

第二种方法：用set来保存已经产生的结果，我们从0开始，遍历其二进制每一位，对其取反，然后看其是否在set中出现过，如果没有，我们将其加入set和结果res中，然后再对这个数的每一位进行遍历，以此类推就可以找出所有的格雷码了。

其他更多方法（比如非递归）见：grap code

代码如下：

mirror version

public class Solution {
    /**
     * @param n a number
     * @return Gray code
     */
    public ArrayList<Integer> grayCode(int n) {
        // Write your code here
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(n <= 1){
            for(int i = 0; i <= n; i++){
                res.add(i);
            }
            return res;
        }
        // res = grayCode(n - 1);
        // ArrayList<Integer> reversedRes = reverse(res);
        // //只考虑增加新的一位为1时的情况，因为新的一位为0时不改变值所以不用加
        // int x = 1 << (n - 1);
        // for(int i = 0; i < reversedRes.size(); i++){
        //     res.add(reversedRes.get(i) + x);
        // }
        // return res;

        //set version
    }

    private ArrayList<Integer> reverse(ArrayList<Integer> res){
        ArrayList<Integer> reversed = new ArrayList<Integer>();
        for(int i = res.size() - 1; i >= 0; i--){
            reversed.add(res.get(i));
        }
        return reversed;
    }
}

Hashset version

public class Solution {
    /**
     * @param n a number
     * @return Gray code
     */
    public ArrayList<Integer> grayCode(int n) {
        // Write your code here
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(n <= 1){
            for(int i = 0; i <= n; i++){
                res.add(i);
            }
            return res;
        }

        HashSet<Integer> set = new HashSet<Integer>();
        helper(n, set, 0, res);
        return res;
    }

    private void helper(int n, HashSet<Integer> set, int curt, ArrayList<Integer> res){
        if(!set.contains(curt)){
            set.add(curt);
            res.add(curt);
        }

        for(int i = 0; i < n; i++){
            int temp = curt;
            //如果当前位为0，则变为1
            if((temp & (1 << i)) == 0){
                temp |= 1 << i;
            }else{
            //如果当前位为1，则变为0，因为是&操作，为了保证其他位不变，必须使其他位为1
                temp &= ~(1 << i);
            }
            if(set.contains(temp)){
                continue;
            }
            helper(n, set, temp, res);
        }
    }
}