Lintcode411 Gray Code solution 题解
发布在刷题能手——Lintcode 题解2018年4月19日view:423
在文章任何区域双击击即可给文章添加【评注】!浮到评注点上可以查看详情。

【题目描述】

The gray 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, find the sequence of gray code. A gray code sequence must begin with 0 and with cover all 2n integers.

 Notice

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

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

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

给定一个非负整数 n ,表示该代码中所有二进制的总数,请找出其格雷编码顺序。一个格雷编码顺序必须以 0 开始,并覆盖所有的 2n 个整数。

【注】对于给定的 n,其格雷编码顺序并不唯一。

根据以上定义, [0,2,3,1] 也是一个有效的格雷编码顺序。

【题目链接】

www.lintcode.com/en/problem/gray-code/

【题目解析】

 直接从 n 位的格雷码分析不太好分析,比如题中n = 2的格雷码,我们不妨试试从小到大分析,以 n = 1 往后递推。

enter image description here

从图中我们可以看出n 位的格雷码可由 n-1位的格雷码递推,在最高位前顺序加0,逆序加1即可。实际实现时我们可以省掉在最高位加0的过程,因为其在数值上和前 n-1位格雷码相同。另外一点则是初始化的处理,图中为从1开始,但若从0开始可进一步简化程序。而且根据格雷码的定义,n=0时确实应该返回0.

【参考答案】

www.jiuzhang.com/solutions/gray-code/

著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

评论
发表评论
暂无评论
PUBLISHED IN
刷题能手——Lintcode 题解

日常更新算法刷题~

我的收藏