[daily training -- Tencent select 50] 89 Gray code (only after seeing the solution of the problem)

subject

n Bit gray code sequence It's a by 2n A sequence of integers , among ：
Every integer is in the range [0, 2n - 1] Inside （ contain 0 and 2n - 1）
The first integer is 0
An integer appears in the sequence Not more than once
Each pair adjacent Binary representation of integers Just a different , And
first and the last one Binary representation of integers Just a 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

Code

package tencent50;

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

public class leetcode89 {
    
    //  I feel like reciting the answer ...
    //  The key is to understand the generation process of gray code  G(i) = i ^ (i / 2)
    public List<Integer> grayCode(int n) {
    
        List<Integer> ansList = new ArrayList<>();
        //  The interval is [0,2^n)
        for (int i = 0; i < 1<<n; i++){
    
            ansList.add(i ^ i>>1);
        }
        return ansList;
    }

    public static void main(String[] args) {
    
        leetcode89 obj = new leetcode89();
        System.out.println(obj.grayCode(2));
    }

}