生成格雷码

[编程题]生成格雷码

热度指数：23025 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码(Gray Code)，请编写一个函数，使用递归的方法生成N位的格雷码。

给定一个整数n，请返回n位的格雷码，顺序为从0开始。

测试样例：

返回：["0","1"]

算法知识视频讲解

Python

离疏

class GrayCode:
    def getGray(self, n):
        if n==1:#1位格雷码有两个码字
            gray=["0","1"]
        else:#n+1位格雷码的集合 = n位格雷码集合(顺序)加前缀0 + n位格雷码集合(逆序)加前缀1
            gray=[("0"+i) for i in self.getGray(n-1)]+[("1"+i) for i in self.getGray(n-1)[::-1]]
        return gray

发表于 2018-07-18 14:51:21 回复(0)

Python

华科平凡

python解法，仅需一行！！！

class GrayCode:
    def getGray(self, n):
        return [bin((i>>1)^i).replace("0b","").rjust(n,"0") for i in range(2**n)]

若不信，运行之。

发表于 2017-11-07 17:39:27 回复(2)

Python

牛客4454924号

# -*- coding:utf-8 -*-
# 思路：n位gray code由n-1为gray code从前置位添加0，并逆序后前置位填1组成，返回的list大小为2^n次方
class GrayCode:
    def getGray(self, n):
        # write code here
        if n == 1:
            return ["0", "1"]
        else:
            return map(lambda x: "0" + x, self.getGray(n-1)) + map(lambda x: "1" + x, self.getGray(n-1)[::-1])

发表于 2017-03-24 15:02:09 回复(0)

Python

牛客8524519号

递归的实现方式就是要找到n和n-1之间的关系：

# -*- coding:utf-8 -*-

class GrayCode:
    def getGray(self, n):
        # write code here
        if n == 1:
            return ['0','1']
        pre = self.getGray(n-1)
        pre0 = ['0'+i for i in pre]
        pre1 = ['1'+i for i in pre]
        pre1.reverse()
        return pre0+pre1

编辑于 2017-03-07 21:45:50 回复(0)