89.格雷编码

链接：89.格雷编码
难度：Medium
标签：位运算、数学、回溯
简介：给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。

题解 1 - typescript

• 编辑时间：2021-11-07
• 执行用时：140ms
• 内存消耗：54.1MB
• 编程语言：typescript
• 解法介绍：dfs。

function grayCode(n: number): number[] {
  if (n === 0) return [0];
  const set = new Set<number>([0]);
  const ans: number[] = [0];
  dfs();
  return ans;
  function dfs(num = 0): boolean {
    if (set.size === 2 ** n) {
      return true;
    }
    for (let i = 0; i <= n; i++) {
      const bit = 1 << i;
      const nextNum = num & bit ? num & ~bit : num | bit;
      if (set.has(nextNum)) continue;
      set.add(nextNum);
      ans.push(nextNum);
      if (dfs(nextNum)) return true;
      ans.pop();
      set.delete(nextNum);
    }
    return false;
  }
}

题解 2 - typescript

• 编辑时间：2021-11-07
• 执行用时：108ms
• 内存消耗：50.3MB
• 编程语言：typescript
• 解法介绍：后半部分逆序输出。

function grayCode(n: number): number[] {
  const ans = [0];
  if (n === 0) return ans;
  while (n--) {
    ans.push(
      ...Array.from(ans)
        .reverse()
        .map(v => v | (1 << n))
    );
  }
  return ans;
}

题解 3 - cpp

• 编辑时间：2022-01-08
• 执行用时：8ms
• 内存消耗：11.5MB
• 编程语言：cpp
• 解法介绍：每次反向覆盖。

class Solution {
   public:
    vector<int> grayCode(int n) {
        vector<int> ans(2, 0);
        ans[1] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = ans.size() - 1; j >= 0; j--) {
                ans.push_back(ans[j] | 1 << i);
            }
        }
        return ans;
    }
};