89.md

#89. Gray Code 题目链接

首先理解格雷码的概念

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> arr = new ArrayList<>();
        // 添加第一个数
        arr.add(0);
        for (int i = 0; i < n; i++) {
            // 将已经添加好的数组以相反的顺序，加上2的i次方，添加到数组中
            for (int j = arr.size() - 1; j >= 0; j--) {
                arr.add(arr.get(j) + (int)Math.pow(2, i));
            }
        }
        return arr;
    }
}

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new LinkedList<>();
        /*
        1<<n ,将1左移n位，表示格雷码的数目
        i ^ i >> 1，G(i) = i^ (i/2)，这是计算公式
         */
        for (int i = 0; i < 1<<n; i++) result.add(i ^ i>>1);
        return result;
    }
}