Leetcode89格雷编码

题目:

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

给定一个代表编码总位数的非负整数 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 = 2 的解,然后考虑怎么得到 n = 3 的解。

n = 2 的解

00 - 0

10 - 2

11 - 3

01 - 1

如果再增加一位,无非是在最高位增加 0 或者 1,考虑先增加 0。由于加的是 0,其实数值并没有变化。

n = 3 的解,最高位是 0

000 - 0

010 - 2

011 - 3

001 - 1   

再考虑增加 1,在 n = 2 的解基础上在最高位把 1 丢过去?

n = 3 的解

000 - 0

010 - 2

011 - 3

001 - 1 

------------- 下面的是新增的

100 - 4

110 - 6

111 - 7

101 - 5 

似乎没这么简单哈哈,第 4 行 001 和新增的第 5 行 100,有 3 个 bit 位不同了,当然不可以了。怎么解决呢?

很简单,第 5 行新增的数据最高位由之前的第 4 行的 0 变成了 1,所以其它位就不要变化了,直接把第 4 行的其它位拉过来,也就是 101。

接下来,为了使得第 6 行和第 5 行只有一位不同,由于第 5 行拉的第 4 行的低位,而第 4 行和第 3 行只有一位不同。所以第 6 行可以把第 3 行的低位拿过来。其他行同理,如下图。


蓝色部分由于最高位加的是 0 ,所以它的数值和 n = 2 的所有解的情况一样。而橙色部分由于最高位加了 1,所以值的话,就是在其对应的值上加 4,也就是 2^2,即2^(3-1)。所以我们的算法可以用迭代求出来了。

所以如果知道了 n = 2 的解的话,如果是 { 0, 1, 3, 2},那么 n = 3 的解就是 { 0, 1, 3, 2, 2 + 4, 3 + 4, 1 + 4, 0 + 4 },即 { 0 1 3 2 6 7 5 4 }。之前的解直接照搬过来,然后倒序把每个数加上2^(3-1) 添加到结果中即可。


代码实现


©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 219,427评论 6 508
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,551评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 165,747评论 0 356
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,939评论 1 295
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,955评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,737评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,448评论 3 420
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,352评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,834评论 1 317
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,992评论 3 338
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,133评论 1 351
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,815评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,477评论 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,022评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,147评论 1 272
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,398评论 3 373
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,077评论 2 355

推荐阅读更多精彩内容

  • 国家电网公司企业标准(Q/GDW)- 面向对象的用电信息数据交换协议 - 报批稿:20170802 前言: 排版 ...
    庭说阅读 10,990评论 6 13
  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 3,345评论 0 2
  • 我是慷慨大度的 一切属于我的 我都赠予你 我赠你微风 我赠你一树风中的绿叶 即使每天在你耳边絮语 ——“我也想把这...
    王小雪的秘密花园阅读 167评论 0 1
  • 你一定也有这样的时候:刚走入职场,一切还不熟悉;部门调整进入新团队;部门又开发了新项目......都难免会遇...
    吕小夏阅读 628评论 1 4
  • 今天是什么日子: 日出时间: 日落时间: 起床时间: 昨晚就寝时间: 郑州气温:-2晴 清晨...
    BOHNONE阅读 137评论 0 0