LeetCode_ Gray code_ Medium_ 89. Gray code

1. subject

n Bit gray code sequence is a sequence composed of 2ⁿ A sequence of integers , among ：
① Every integer is in the range [0, 2ⁿ - 1] Inside （ contain 0 and 2ⁿ - 1）
② The first integer is 0
③ An integer does not appear more than once in the sequence
④ The binary representation of each pair of adjacent integers is exactly one bit different , And the binary representation of the first and last integers is exactly one bit different

Give you an integer n , Returns any valid n Bit gray code sequence .

Example 1：
Input ：n = 2
Output ：[0,1,3,2]
explain ：
[0,1,3,2] The binary representation of is [00,01,11,10] .

• 00 and 01 There is a difference
• 01 and 11 There is a difference
• 11 and 10 There is a difference
• 10 and 00 There is a difference

[0,2,3,1] It is also an effective gray code sequence , Its binary representation is [00,10,11,01] .

• 00 and 10 There is a difference
• 10 and 11 There is a difference
• 11 and 01 There is a difference
• 01 and 00 There is a difference

Example 2：
Input ：n = 1
Output ：[0,1]

Tips ：
1 <= n <= 16

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/gray-code
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2. Ideas

Train of thought reference Official solution to this problem .
（1） Symmetrically generated

（2） Binary to gray code

3. Code implementation （Java）

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

// Ideas 2———— Binary to gray code 
class Solution {
    
    public List<Integer> grayCode(int n) {
    
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < (1 << n); i++) {
    
            res.add((i >> 1) ^ i);
        }
        return res;
    }
}