89. Gray Code
n 位的格雷碼序列是一個長度為 2^n 的整數序列，其中：
每個整數都在 [0, 2^n - 1] 的範圍內， 第一個整數是 0， 每個整數在序列中不超過一次， 每對相鄰整數的二進制表示形式僅差一位，並且 第一個和最後一個整數的二進制表示形式僅差一位。 給定一個整數 n，返回任意有效的 n 位格雷碼序列。
範例 1：
輸入：n = 2 輸出：[0,1,3,2] 解釋： [0,1,3,2] 的二進制表示形式是 [00,01,11,10]。00 和 01 只差一位
01 和 11 只差一位
11 和 10 只差一位
10 和 00 只差一位 [0,2,3,1] 也是一個有效的格雷碼序列，其二進制表示形式是 [00,10,11,01]。
00 和 10 只差一位
10 和 11 只差一位
11 和 01 只差一位
01 和 00 只差一位
Python
from typing import List
class Solution:
def grayCode(self, n: int) -> List[int]:
result = [0]
for i in range(n):
# Reflect the existing sequence
reflected = [x | (1 << i) for x in reversed(result)]
# Append the reflected sequence to the original
result.extend(reflected)
return result
23.67MB, 70ms
C++
#include <vector>
using namespace std;
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> result = {0};
for (int i = 0; i < n; ++i) {
int currentSize = result.size();
for (int j = currentSize - 1; j >= 0; --j) {
result.push_back(result[j] | (1 << i));
}
}
return result;
}
};
13.01MB, 9ms
Javascript
/**
* @param {number} n
* @return {number[]}
*/
var grayCode = function(n) {
let result = [0];
for (let i = 0; i < n; i++) {
const currentSize = result.length;
for (let j = currentSize - 1; j >= 0; j--) {
result.push(result[j] | (1 << i));
}
}
return result;
};
60.51MB, 84ms
