lintcode:格雷编码

格雷编码

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个二进制的差异。

给定一个非负整数 n ，表示该代码中所有二进制的总数，请找出其格雷编码顺序。一个格雷编码顺序必须以 0 开始，并覆盖所有的 2^n 个整数。

 注意事项

对于给定的 n，其格雷编码顺序并不唯一。

根据以上定义， [0,2,3,1] 也是一个有效的格雷编码顺序。

样例

给定 n = 2， 返回 [0,1,3,2]。其格雷编码顺序为：

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

解题
腾讯笔试生成格雷编码

n位的二进制格雷编码，是由 n-1位格雷编码生成的

1.n-1位格雷编码正序，每个编码前 增加一位 0 ，这里是二进制，转换成十进制没有影响

2.n-1为格雷编码逆序，每个编码前 增加一位 1 ，转换成十进制，相当于加上 2^{n-1}

public class Solution {
    /**
     * @param n a number
     * @return Gray code
     */
    public ArrayList<Integer> grayCode(int n) {
        // Write your code here
        ArrayList<Integer> list = new ArrayList<Integer>();
        if( n==0){
            list.add(0);
            return list;
        }
        if( n == 1){
            list.add(0);
            list.add(1);
            return list;
        }
        list = grayCode(n-1);
        ArrayList<Integer> tmp = list;
        // 正序 前 加 0 ，前面加0对于 十进制数组是没有影响的 
        for(int i = 0;i<tmp.size();i++){
            list.set(i,tmp.get(i));
        }
        // 逆序 前 加 1 ，前面加 1 相等于加了一个 2^{n-1}
        for(int i = tmp.size() -1 ;i >=0;i--){
            list.add((int)Math.pow(2,n-1)+tmp.get(i));
        }
        
            
        return list;
    }
}