当前位置:首页软件开发Java → Gray Code

Gray Code

时间:2021-06-16 00:48:46来源:互联网我要评论(0)

首先简单介绍一下什么是格雷码。在一组数的编码中,若任意两个相邻的代码只有一位二进制数不同,则称这种编码为格雷码(Gray Code),另外由于最大数与最小数之间也仅一位数不同,即“首尾相连”,因此又称循环码或反射码。有关格雷码的详细讲解请大家查阅网上其它资料,这里主要讲解格雷码是如何编码的。

我们不妨从简单例子开始进一步看一下什么是格雷码,假设n代表格雷码的位数,当n=1时,我们只有两种选择(0, 1); 当 n =2 时,格雷码为(00, 01, 11, 10); 当n = 3时,格雷码为(000, 001, 011,010, 110, 111, 101, 100);我们发现了一个规律,就是每当增加一位,新的格雷码的前半段都是在之前的格雷码前面加上一个零,红色地方代表了格雷码的前半段。而后半段就是从后面开始在前面加上1。通过这种方式就可以写出任意位数的格雷码。

leetcode中有一道题目是关于格雷码的,在这里列举一下。给定一个整数n,输出它的格雷码序列。格雷码序列不唯一,输出一种就可以。按照上面的编码规则,我们不难写出代码,代码如下:

public class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> list = new ArrayList<Integer>();
        if(n < 0) return list;
        list.add(0);
        for(int i = 1; i <= n; i++) 
            for(int j = list.size() - 1; j >= 0; j--) {
                list.add(list.get(j) + (int)Math.pow(2, i - 1));
            }
        return list;
    }
}

相关文章

网友评论

热门评论

最新评论

发表评论 查看所有评论()

昵称:
表情: 高兴 可 汗 我不要 害羞 好 下下下 送花 屎 亲亲
字数: 0/500 (您的评论需要经过审核才能显示)

关于万荚 | 联系方式 | 发展历程 | 版权声明 | 帮助(?) | 网站地图 | 友情链接

Copyright 2005-2021 16WJ.COM 〖万荚网〗 版权所有 桂ICP备18000060号 |

声明: 本站所有文章来自互联网 如有异议 请与本站联系