143 - 89 格雷编码

题目

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。

示例 1:

输入: 2 输出: [0,1,3,2] 解释: 00 - 0 01 - 1 11 - 3 10 - 2

对于给定的 n，其格雷编码序列并不唯一。 例如，[0,2,3,1] 也是一个有效的格雷编码序列。

00 - 0 10 - 2 11 - 3 01 - 1

示例 2:

输入: 0 输出: [0] 解释: 我们定义格雷编码序列必须以 0 开头。 给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 2*0 = 1。 因此，当 n = 0 时，其格雷编码序列为 [0]。

解答

这题目是完全没看懂

总之是求一个数组，每个数的二进制差一。

https://leetcode-cn.com/problems/gray-code/solution/gray-code-jing-xiang-fan-she-fa-by-jyd/

一个看不太懂的骚解法

1. 原数组前面加个零

2. 生成镜像数组，逆序拼在后面

3. 镜像数组的第一个数全变成1

class Solution:
    def grayCode(self, n: int) -> List[int]:
        res, head = [0], 1
        for _ in range(n):
            for j in range(len(res)-1, -1, -1):
                res.append(head+res[j])
            head *= 2
        return res

Runtime: 32 ms, faster than 95.89% of Python3 online submissions for Gray Code.

Memory Usage: 12.9 MB, less than 100.00% of Python3 online submissions for Gray Code.

https://leetcode-cn.com/problems/gray-code/solution/gen-ju-ge-lei-ma-de-xing-zhi-by-powcai/

更骚的解法，都不看懂

class Solution:
    def grayCode(self, n: int) -> List[int]:
        res = []
        for i in range(2**n):
            res.append((i >> 1) ^ i)
        return res

Runtime: 28 ms, faster than 98.72% of Python3 online submissions for Gray Code.

Memory Usage: 13 MB, less than 100.00% of Python3 online submissions for Gray Code.

https://leetcode-cn.com/problems/gray-code/solution/1-xing-python-by-knifezhu-2/

还有直接背公式的。。

class Solution:
    def grayCode(self, n: int) -> List[int]:
        return [i ^ i >> 1  for i in range(1 << n)]

Runtime: 28 ms, faster than 98.72% of Python3 online submissions for Gray Code.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Gray Code.

var grayCode = function(n) {
  let res = [0]
  head = 1
  for (let i = 0; i < n; i++) {
    for (let j = res.length - 1; j >= 0; j--) {
      let item = head + res[j]
      res.push(item)
    }
    head *= 2
  }
  return res
};

Runtime: 56 ms, faster than 65.32% of JavaScript online submissions for Gray Code.

Memory Usage: 34 MB, less than 100.00% of JavaScript online submissions for Gray Code.

func grayCode(n int) []int {
    res := []int{0}
    head := 1
    for i := 0; i < n; i++ {
        for j := len(res) - 1; j >= 0; j-- {
            res = append(res, head+res[j])
        }
        head *= 2
    }
    return res
}

Runtime: 4 ms, faster than 75.64% of Go online submissions for Gray Code.

Memory Usage: 7.7 MB, less than 100.00% of Go online submissions for Gray Code.