LeetCode 89. 格雷编码 Python 一行代码解法_arry_lee的博客-程序员宝宝

技术标签: LeetCode  

题目:

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

给定一个代表编码总位数的非负整数 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位的格雷码获得

一位格雷码:0,1

两位格雷码:00,01;11,10

三位格雷码:000,001,011,010;110,111,101,100

四位格雷码:0000,0001,0011,0010,0110,0111,0101,0100; 1100,1101,1111,1110,1010,1011,1001,1000

通过上面的枚举可以发现,格雷码的实现其实是一个递归过程

例如三位格雷码的前四位是把两位格雷码按从左到右的顺序在每一个格雷码前面加0实现的,后面四位是把两位格雷码按照从右到左的顺序在每一位格雷码前面加一实现的,大家按照这个方法推一下格雷码,应该能理解这段话的意思。

此外在前面加0,格雷码对应的值不会改变,前面加一会让各类码的值增加2^(n-1),n为格雷码的位数

代码

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """ 
        return [0] if n == 0 else self.grayCode(n-1) + [x+(1<<(n-1)) for x in reversed(self.grayCode(n-1))]
                
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Arry_Lee/article/details/83795447

智能推荐

太全了!学Java项目,上这个网站就够了_Java小咖秀的博客-程序员宝宝

你有多久没好好学习一个开源项目了?你是否经常为找不到好的开源项目而烦恼?你是否为不知道怎么入手去看一个开源项目?你是否想看别人的项目学习笔记?你是否想跟着别人的项目搭建过程一步一步跟着做...

树莓派之RFID_藏锋于鞘的博客-程序员宝宝

RFID这个原理我就不讲了,详细的自己去看网蜂科技的RFID讲的很详细 主要讲一讲如何区使用mfrc522去区分复制卡(UID卡和M1卡) UID卡可以完美复制M1卡,所以区分UID卡和M1卡的时候,只能根据UID卡可以更改卡号的这个特性去判断UID卡和MI卡Sent bits: 26 (7 bits) //寻卡 0x26 / 0x52 都可以 Received bits: 04 00 ...

调换磁盘0和磁盘1_sticker_start_tag的博客-程序员宝宝_磁盘0和磁盘1换顺序

问题描述:我的笔记本是固态+机械(固态是.m接口,机械是sata接口),昨天安装双系统后,装系统的固态硬盘变成了磁盘1,而机械硬盘变成了磁盘0解决办法:在“设备管理器”里,点开“磁盘驱动器”,将你的非启动盘禁用,重启电脑后,系统盘就是默认磁盘0了,内然后再进入设备管理器将非启动盘启用即可,因为系统盘已经占用磁盘0,所以非启动盘只能向后排序。即使以后重启了,顺序也不会失效。除非你的非启动盘上也装了系统,并且从非启动盘进入过系统,这容样才会再次打乱磁盘顺序。...

UART详解_sternlycore的博客-程序员宝宝_uart

UART通用异步收发传输器(Universal Asynchronous Receiver/Transmitter,通常称作UART) 是一种串行异步收发协议,应用十分广泛。UART工作原理是将数据的二进制位一位一位的进行传输。在UART通讯协议中信号线上的状态位高电平代表’1’低电平代表’0’。当然两个设备使用UART串口通讯时,必须先约定好传输速率和一些数据位。硬件连接硬件连接比较简...

Java 内存模型-基础概念_2.wa的博客-程序员宝宝

该专栏源文件与 java-concurrency 同步,源码与 github-java-concurrency 同步。在线阅读基础概念原子性:即一个操作或者多个操作 要么全部执行并且执行的过程不会被任何因素打断,要么就都不执行可见性:指当多个线程访问同一个变量时,一个线程修改了这个变量的值,其他线程能够立即看得到修改的值有序性:即程序执行的顺序按照代码的先后顺序执行内存模型结构...

Visual Studio下C++第三方库的配置方法总结_goulei2010的博客-程序员宝宝

对于任何一种编程语言来说,其提供的标准库以及第三方库都是一个值得我们关注的内容,因为这样可以使我们站在巨人的肩膀上做事,从而更方便快捷地完成我们想要做的事情。对于C++这种语言来说,标准库在引用正确的头文件后,便可以使用其提供的相关功能了;而对于第三方库来讲,可能还需要花一点点时间做一些配置,才能正常的使用这些库。下面对于在Visual Studio平台下的第三方库的配置方法进行一些总结。

随便推点

Android学习笔记4--XmlPullParser的使用_analysefang的博客-程序员宝宝_.equals(parser.nextrecord().get(0))

xml文件的解析器XmlPullParser,解析一个xml文件 1.获取解析器对象 2.设置解析器的参数 3.获取解析的事件类型 4.判断事件类型进行解析的逻辑public static List<Channel> parserXml(InputStream in) throws Exception{ //[0]声明集合对象

常用功能自动化测试工具汇总_中国软件测试质量协会的博客-程序员宝宝_以下属于功能自动化测试工具的是

话说自动化测试方面的工具还是非常的多的,不可能也没有必要查看了所有的测试工具;个人觉得当学习众多同类知识或相关主题时,分几步走:1、学习所有同类知识的共同理论、原理部分【此为共性】2、学习所有同类知识的独有特性、技巧部分【此为个性】3、根据具体的实际场景,适当的运用所学知识的【即运用知识的个性部分去解决特定的问题】学习自动化测试工具也是这样的,之前不愿意学习太多是怕混淆视听,现在对原有知识...

记录一下:解决URLDownloadToFile缓存问题的两种方法_三杨的博客-程序员宝宝_urldownloadtofile

URLDownloadToFile下载文件前先在本地的缓存中查找此文件如果缓存有则不会再去网上抓最新的文件,所以我们还要解决URLDownloadToFile缓存的问题。方法 1:我们可以对URL进行改动,让它每次访问不同的URL但指向相同的页面,例如在URL结尾添加一些无意义的参数:"http://www.dtapp.cn?abc=1"这里的 ?abc=1 可以随机实现,下次下载则改成 ?abc=2 因为URL不同,所以不会在缓存中找到。最后程序改成:/**************.

数据结构PTA习题:进阶实验4-3.1 家谱处理 (30分)_5?li的博客-程序员宝宝

进阶实验4-3.1 家谱处理 (30分)人类学研究对于家族很感兴趣,于是研究人员搜集了一些家族的家谱进行研究。实验中,使用计算机处理家谱。为了实现这个目的,研究人员将家谱转换为文本文件。下面为家谱文本文件的实例:JohnRobertFrankAndrewNancyDavid家谱文本文件中,每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代,而他...

python 迭代器生成器_Python生成器简介_cumei1658的博客-程序员宝宝

python 迭代器生成器Generators are functions that can be paused and resumed on the fly, returning an object that can be iterated over. Unlike lists, they are lazy and thus produce items one at a time and onl...

React组件设计实践总结05 - 状态管理_weixin_34357436的博客-程序员宝宝

今天是 520,这是本系列最后一篇文章,主要涵盖 React 状态管理的相关方案。前几篇文章在掘金首发基本石沉大海, 没什么阅读量. 可能是文章篇幅太长了?掘金值太低了? 还是错别字太多了? 后面静下心来想想,写作对我来说是一种学习和积累的过程, 让我学习更全面更系统性去描述一个事物. 但是写作确实是一件非常耗时的事情, 文章的每句话都要细细推敲, 还要避免主观性太强避免误导了别人.所以模仿&...

推荐文章

热门文章

相关标签