【Leetcode】89. Gray Code

题目地址：

https://leetcode.com/problems/gray-code/

生成$n$n位的格雷码。$n$n位格雷码是个int的数组，其每相邻的两个数的二进制表示只有一位不同，并且首尾也满足这个条件。

主要思路是这样：如果我们已经得到了$k$k位格雷码，那么$k+1$k+1位格雷码可以这样生成：先将得到的$k$k位格雷码反序，然后每个数字都加上$1<<k=2^k$1<<k=2k即可。这有点像逆序的层序遍历二叉树。代码如下：

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<>();
        res.add(0);
    
        for (int i = 0; i < n; i++) {
            int size = res.size();
            for (int j = size - 1; j >= 0; j--) {
                res.add(res.get(j) + (1 << i));
            }
        }
        
        return res;
    }
}

时间复杂度$O(2^n)$O(2n)。

算法正确性证明。当$n=1$n=1时显然成立。假设当$n=k$n=k时，上述算法可以正确地产生格雷码。那么对于这个格雷码$a_1,...,a_{2^k}$a1​,...,a2k​，最先加到末尾的数是$a_{2^k}+2^k$a2k​+2k，这个数与$a_{2^k}$a2k​只有最高位不同，所以至少当前这一步是可行的。接下来由归纳假设，后面加的数字与前一位也只有一位不同，这样一直加到了末尾。很显然$a_1$a1​与$a_1+2^k$a1​+2k也只有最高位不同。所以这样生成的新的序列仍然是格雷码。由数学归纳法，算法正确。