LeetCode 0089 - Gray Code
# Hints
思维
格雷码
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
The gray code is a binary numeral system where two successive values differ in only one bit.
Given a non-negative integer representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with .
Example 1:
Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2
For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.
00 - 0
10 - 2
11 - 3
01 - 1
Example 2:
Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
A gray code sequence of n has size = 2^n, which for n = 0 the size is 2^0 = 1.
Therefore, for n = 0 the gray code sequence is [0].
# 题意
给定一个正整数 ,要求将所有 位二进制数按特定顺序排列,使得每两个相邻数之间只有一个二进制位不同。求出任意一种合法解即可。
# 题解
方法1:
列举 和 的情况不难发现一种合法解的对称性质。
对于 的情况:
000 0
001 1
011 2+1
010 2+0
110 4+2
111 4+3
101 4+1
100 4+0
对于 的情况:
0000 0 0
0001 1 1
0011 2+1 3
0010 2+0 2
0110 4+2 6
0111 4+3 7
0101 4+1 5
0100 4+0 4
1100 8+4
1101 8+5
1111 8+7
1110 8+6
1010 8+2
1011 8+3
1001 8+1
1000 8+0
根据规律进行镜像生成即可,时间复杂度为 。
方法2:
本题事实上是要求生成 位格雷码,若对格雷码有所了解,根据由二进制码生成格雷码的公式即可直接求解,时间复杂度为 。
格雷码:https://www.cnblogs.com/zhuruibi/p/8988044.html
# AC代码(思维)
class Solution {
public:
vector<int> grayCode(int n) {
// 生成
vector<int> res;
res.push_back(0);
for (int t = 1; t < (1 << n); t <<= 1) {
for (int i = 1, j = t - 1; i <= t; i ++, j --) {
res.push_back(t + res[j]);
}
}
// 返回
return res;
}
};
# AC代码(格雷码)
class Solution {
public:
vector<int> grayCode(int n) {
// 生成
vector<int> res(1 << n);
for (int i = 0; i < (1 << n); i ++) {
res[i] = i ^ (i >> 1);
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01