89. Gray Code 格雷编码

题目地址：https://leetcode.com/problems/gray-code/description/

题目描述

Thegray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Forexample, given n = 2, return [0,1,3,2]. Its gray code sequence is:

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

Note:

Fora given n, a gray code sequence is not uniquely defined.

Forexample, [0,2,3,1] is also a valid gray code sequence according to the above definition.

Fornow, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

题目大意

求n位的格雷码序列。格雷码是指相邻的两个数字的二进制只会有一位不同。

解题方法

这个题目是属于回溯法的题目。但是，查了一下百度百科的格雷码，根本用不到回溯啊摔！！

下面是百度百科告诉的如何求n位的格雷码的方法。

递归生成码表

这种方法基于格雷码是反射码的事实，利用递归的如下规则来构造：

1. 1位格雷码有两个码字
2. (n+1)位格雷码中的前2n个码字等于n位格雷码的码字，按顺序书写，加前缀0
3. (n+1)位格雷码中的后2n个码字等于n位格雷码的码字，按逆序书写，加前缀1
4. n+1位格雷码的集合 = n位格雷码集合(顺序)加前缀0 + n位格雷码集合(逆序)加前缀1

简言之就是递归。第（n+1）位的格雷码序列=（'0'+第n位的正序） + （'1'+第n位的逆序）

题目中说了n是非负数，当n=0的时候，返回[0]即可。

所以循环版本：

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        grays = dict()
        grays[0] = ['0']
        grays[1] = ['0', '1']
        for i in range(2, n + 1):
            n_gray = []
            for pre in grays[i - 1]:
                n_gray.append('0' + pre)
            for pre in grays[i - 1][::-1]:
                n_gray.append('1' + pre)
            grays[i] = n_gray
        return map(lambda x: int(x, 2), grays[n])

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

递归版本：

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        return map(lambda x: int(x, 2), self.bit_gray(n))
    
    def bit_gray(self, n):
        ans = None
        if n == 0:
            ans = ['0']
        elif n == 1:
            ans = ['0', '1']
        else:
            pre_gray = self.bit_gray(n - 1)
            ans = ['0' + x for x in pre_gray] + ['1' + x for x in pre_gray[::-1]]
        return ans

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

C++代码如下：

class Solution {
public:
    vector<int> grayCode(int n) {
        if (n == 0) return {0};
        if (n == 1) return {0, 1};
        vector<int> res;
        vector<int> pre = grayCode(n - 1);
        for (int p : pre) {
            res.push_back(p);
        }
        for (auto p = pre.rbegin(); p < pre.rend(); p++) {
            res.push_back((1 << (n - 1)) + *p);
        }
        return res;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发