格雷编码

[louzhedong]

习题

出处：LeetCode 算法第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 时，长度为 20 = 1。
     因此，当 n = 0 时，其格雷编码序列为 [0]。

思路

首先找格雷编码的规律，n个数的编码可以通过n-1个数的编码得到，比如：

n = 1时，编码为[0,1]

n = 2时，编码为[00,10,11,10]

首先倒序遍历[0,1]，将每个编码项加1然后存入新列表的后面，然后加0存入新列表的前面

首先是1，操作后产生[10,11]

接下来是0，操作后产生[00,10,11,01]

最后生成的就是n=2时的格雷编码

思路

/**
 * @param {number} n
 * @return {number[]}
 */
var grayCode = function (n) {
  var result = helper(n);
  for (var i = 0; i < result.length; i++) {
    result[i] = parseInt(result[i], 2);
  }
  return result;
};

var helper = function (n) {
  if (n == 0) return [0];
  if (n == 1) return [0, 1];

  var res = [];
  var prevRes = helper(n - 1);
  var len = prevRes.length;
  for (var i = len - 1; i >= 0; i--) {
    res.push(prevRes[i] + '1');
    res.unshift(prevRes[i] + '0');
  }

  return res;
}