LeetCode 题解:89. 格雷编码,归纳法,详细注释
原题链接:https://leetcode.cn/problems/gray-code/
解题思路:
该题要求返回格雷编码序列,我们并不需要思考编码的生成方法,只要实现百科中提供的思路即可
假设我们已经知道了
n - 1
的序列,那么n
位的序列就等于已有的n - 1
序列,再加上逆序书写的n - 1
序列,在逆序数列的前面加上 1 即可。举个例子:
在
n = 3
时,n - 1
即 2 位的序列为[00, 01, 11, 10]
3 位序列就等于 2 位的序列
[00, 01, 11, 10]
前面加前缀0
,得到[000, 001, 011, 010]
再依次拼接上:
10
加前缀 1,得到110
11
加前缀 1,得到111
01
加前缀 1,得到101
00
加前缀 1,得到100
最后的结果为
[000, 001, 011, 010, 110, 111, 101, 100]
如何实现拼接前缀 1, 以
10
为例:先将
1
向左移动 2 位,得到100
将
10
与100
进行“或”位运算,即10 | 100 = 110
复制代码
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/d189f5742bc2e3615f96965ff】。文章转载请联系作者。
评论