Leetcode - 89. 格雷编码

class Solution {

    // 当n分别为 1, 2, 3 时，其格雷码分别如下所示：
    //    1     2       3           |
    //  --------------------        |
    //    0    0 0    0 0 0         |        我们发现，n = i的图像可以通过n = i - 1的图像推导出来
    //    1    0 1    0 0 1         |        1. 先将n = i - 1的图像以底边为轴进行翻转
    //         1 1    0 1 1         |        2. 然后原来图像的各个格雷码之前加上数字0
    //         1 0    0 1 0         |        3. 翻转后的图像的各个格雷码之前加上数字1
    //                1 1 0         |        4. 就得到了n = i时的所有格雷码
    //                1 1 1         |
    //                1 0 1         |
    //                1 0 0         |
    public List<Integer> grayCode(int n) {
        int[] arr = new int[1 << n];
        int length = 1;
        
        // 对arr迭代n次后即可得到最终结果
        while (n-- > 0) {
            iterate(arr, length);
            length <<= 1;
        }

        return toList(arr);
    }

    private static void iterate(int[] arr, int length) {
        int left = length - 1, right = length;
        while (left >= 0) {
            arr[right++] = arr[left--] + length;
        }
    }

    private static List<Integer> toList(int[] arr) {
        List<Integer> list = new ArrayList<>(arr.length);
        for (int i : arr) list.add(i);
        return list;
    }
}