题目描述
题目链接:89. Gray Code
An n-bit gray code sequence is a sequence of
2^n
integers where:
- Every integer is in the inclusive range
[0, 2^n - 1]
,- The first integer is
0
,- An integer appears no more than once in the sequence,
- The binary representation of every pair of adjacent integers differs by exactly one bit, and
- The binary representation of the first and last integers differs by exactly one bit.
Given an integer
n
, return any valid n-bit gray code sequence.
例子
例子 1
Input:
n = 2
Output:[0,1,3,2]
Explanation: The binary representation of[0,1,3,2]
is[00,01,11,10]
.
00
and01
differ by one bit01
and11
differ by one bit11
and10
differ by one bit10
and00
differ by one bit[0,2,3,1]
is also a valid gray code sequence, whose binary representation is[00,10,11,01]
.00
and10
differ by one bit10
and11
differ by one bit11
and01
differ by one bit01
and00
differ by one bit
例子 2
Input:
n = 1
Output:[0,1]
Constraints
1 <= n <= 16
解题思路
通过观察 n = 2
的两组可行答案和 n = 1
的答案,可以发现一个规律:
n = 2
的第二组的后两个元素和前两个元素(除了最高位)互为镜像,区别是后两个元素的最高位是1
,可以看成是n = 1
的答案后面从后往前遍历,并最高位加个1形成一组答案;n = 2
的第二组答案也是类似,区别是不是在最高位而是再低位加1
根据这个规律,代码如下:
#include <vector>
class Solution {
public:
std::vector<int> grayCode(int n) {
int num = (1 << n);
std::vector<int> ans(num, 0);
int current_bits = 0;
for (int i = 1; i < num; ++i) {
// mirror_line = (2 ^ current_bits) - 1, diff = (i - 2 ^ current_bits)
int idx = (1 << current_bits) - 1 - (i - (1 << current_bits));
ans[i] = ((1 << current_bits) | ans[idx]);
if (i == ((1 << (current_bits + 1)) - 1)) {
current_bits++;
}
}
return ans;
}
};
- 时间复杂度:
(2^n)
- 空间复杂度:
(2^n)
GitHub 代码同步地址: 89.GrayCode.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions