0%

[Leetcode]89. Gray Code(C++)

题目描述

题目链接: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 and 01 differ by one bit
  • 01 and 11 differ by one bit
  • 11 and 10 differ by one bit
  • 10 and 00 differ by one bit
    [0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
  • 00 and 10 differ by one bit
  • 10 and 11 differ by one bit
  • 11 and 01 differ by one bit
  • 01 and 00 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

根据这个规律,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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