0089. Gray Code - kumaeki/LeetCode GitHub Wiki

0089. Gray Code

An n-bit gray code sequence is a sequence of 2n integers where:

  • Every integer is in the inclusive range [0, 2n - 1],
  • The first integer is 0,
  • An integer appears no more than once in the sequence,
  • The binary representation of every pair of adjacent integers differs by exactly one bit, and
  • The binary representation of the first and last integers differs by exactly one bit. Given an integer n, return any valid n-bit gray code sequence.

Example 1:

Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

Example 2:

Input: n = 1
Output: [0,1]

Constraints:

  • 1 <= n <= 16

解法1

关键在于找到规律.

n = 1
0, 1

n = 2
(0)0, (0)1, (1)1, (1)0

n = 3
(0)00, (0)01, (0)11, (0)10, (1)10, (1)11, (1)01, (1)00

从上面可以看到, 至少有一种排列方式是满足以下形式.

  1. 除开最左一位, 剩下的数字是左右对称的.
  2. 对称部分的左侧, 正好就是n - 1 的结果.

于是可以通过递归得到结果.

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> list = new ArrayList<>();
        helper(list, n);
        return list;
    }
    
    private void helper(List<Integer> list, int n){
        if(n == 0){
            list.add(0);
            return;
        }
        
        // 计算n-1的结果
        helper(list, n - 1);
        
        // 将n-1的list倒序遍历, 最前面加1之后加入list中
        int k = 1<<(n - 1);
        for(int i = list.size() - 1; i >= 0; i--)
            list.add(list.get(i) | k);
        
    }
}

解法2

也可以不用递归, 直接用循环.

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        result.add(0);

        for (int i = 1; i <= n; i++) {
            int preLen= result.size();
            int mask = 1 << (i - 1);
            for (int j = preLen- 1; j >= 0; j--) {
                result.add(mask + result.get(j));
            }
        }
        return result;
    }
}

解法3

另一种排列的规律, 有点类似于二叉树的中序遍历. 以 n = 3 为例.

(0)00, (0)01, (0)11, (0)10, (1)10, (1)11, (1)01, (1)00

对于第k层的节点, 把左节点的第k-1位翻转得到右节点

class Solution {
    int nextNum = 0;

    public List<Integer> grayCode(int n) {
        List<Integer> result = new ArrayList<>();
        helper(result, n);
        return result;
    }

    private void helper(List<Integer> result, int n) {
        if (n == 0) {
            result.add(nextNum);
            return;
        }
        helper(result, n - 1);
        // 翻转第n - 1位
        nextNum = nextNum ^ (1 << (n - 1));
        helper(result, n - 1);

    }
}
⚠️ **GitHub.com Fallback** ⚠️