LeetCode_格雷编码_中等_89.格雷编码

喜欢ヅ旅行 2023-10-06 23:16 18阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

n 位格雷码序列是一个由 2n 个整数组成的序列，其中：  
① 每个整数都在范围 \[0, 2n \- 1\] 内（含 0 和 2n \- 1）  
② 第一个整数是 0  
③ 一个整数在序列中出现不超过一次  
④ 每对相邻整数的二进制表示恰好一位不同 ，且第一个和最后一个整数的二进制表示恰好一位不同

**给你一个整数 n ，返回任一有效的 n 位格雷码序列 。**

**示例 1：**  
输入：n = 2  
输出：\[0,1,3,2\]  
解释：  
\[0,1,3,2\] 的二进制表示是 \[00,01,11,10\] 。

*  00 和 01 有一位不同
 *  01 和 11 有一位不同
 *  11 和 10 有一位不同
 *  10 和 00 有一位不同

\[0,2,3,1\] 也是一个有效的格雷码序列，其二进制表示是 \[00,10,11,01\] 。

*  00 和 10 有一位不同
 *  10 和 11 有一位不同
 *  11 和 01 有一位不同
 *  01 和 00 有一位不同

**示例 2：**  
输入：n = 1  
输出：\[0,1\]

**提示：**  
1 <= n <= 16

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/gray-code  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 2.思路 ##

思路参考[本题官方题解][Link 1]。  
（1）对称生成

（2）二进制数转格雷码

## 3.代码实现（Java） ##

//思路1————对称生成
    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;
        }
    }

//思路2————二进制数转格雷码
    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;
        }
    }

[Link 1]: https://leetcode.cn/problems/gray-code/solution/ge-lei-bian-ma-by-leetcode-solution-cqi7/