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

### 题目描述

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` 的第二组的后两个元素和前两个元素（除了最高位）互为镜像，区别是后两个元素的最高位是 `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

Built with Hugo
Theme Stack designed by Jimmy