LeetCode89 格雷编码

发表于 | 分类于 |
字数统计: 373 | 阅读时长 ≈ 1

链接： https://leetcode.cn/problems/gray-code/

题意

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

解法

观察不同n的格雷序列
n = 1: [0, 1]
n = 2: [0, 1, 3, 2]
n = 3: [0, 1, 3, 2, 6, 7, 5, 4]

可以发现第n个序列前半部分和n - 1是一样的，后半部分是前半部分对称 再加上 n - 1的长度
就可以构成新的格雷序列
用这种思路可以很顺利的写出代码

当然还有一种就是格雷序列的正统生成方式
每次i 和 (i / 2) 进行异或得到的结果就是格雷序列

代码

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret({0, 1});
        while(ret.size() < (1 << n)) {
            int siz = ret.size();
            for (int i = 0; i < siz; i++) {
                ret.push_back(ret[siz - i - 1] + siz);
            }
        }
        return ret;

    }
};

解法二

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ret;
        for (int i = 0; i < (1 << n); i++) {
            ret.push_back(i ^ (i >> 1));
        }
        return ret;
    }
};