LeetCode 89: GrayCode (Java)

xiguadada 发布于2019-08-14 15:51 / 1802人阅读

摘要：位的格雷码是在位的格雷码前面加或。由上图可以发现，位的格雷码后一位是镜像对称位的格雷码后位是镜像对称位的格雷码后位是镜像对称。规律就是为格雷码是在位格雷码的基础上，先将位镜像对称然后前一半首位添，后一般首位添而得到。

google电面第一轮碰到的题.

GrayCode:给定位数n，按规律生成一组二进制代码，直接上例子。

1位的格雷码就是0，1。
2位的格雷码是在1位的格雷码前面加0或1。
由上图可以发现，2位的格雷码后一位是镜像对称；3位的格雷码后2位是镜像对称；4位的格雷码后3位是镜像对称。
规律就是n为格雷码是在n-1位格雷码的基础上，先将n-1位镜像对称然后前一半首位添0，后一般首位添1而得到。
如果要输出n位的格雷码就得先生成n-1位格雷码，这样自然会想到回溯的方法来编程。
具体实现要先考虑基本的case,也就是n=1的情况，应该先在list中添加0，1两个数，之后n=2的时候倒着读加上1。

public List grayCode(int n) {
    if(n == 0){
        List res = new ArrayList<>();
        res.add(0);
        return res;
    }
    
    List res = grayCode(n-1);
    
    int originSize = res.size();
    int addN = 1 << (n-1);
    
    for(int i = originSize-1;i>=0;i--)
        res.add(addN+res.get(i));
    
    return res;
}

Ref: 百度百科：格雷码

云服务器 GPU云服务器 GrayCode 89美元 LeetCode GIF89a

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66063.html

数据结构与算法-LeetCode 格雷编码(No.89)

摘要：例如，也是一个有效的格雷编码序列。示例输入输出解释我们定义格雷编码序列必须以开头。给定编码总位数为的格雷编码序列，其长度为。因此，当时，其格雷编码序列为。 LeetCode 89. 格雷编码格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。第一个数与最后一位数也只差以...

Youngs 2019-08-26 13:47 评论0 收藏0
[Leetcode] Gray Code 格雷码

摘要：找规律复杂度时间空间思路仔细观察格雷码当时当时当时可以发现，的格雷码，就是的格雷码，再加上它们的逆序前面多一个。 Grey Code The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n re...

Code4App 2019-08-14 12:31 评论0 收藏0
Leetcode PHP题解--D89 653. Two Sum IV - Input is a B

摘要：思路思路遍历的时候，先把节点存起来，并且与每一个值相加，判断是否等于所需值。用函数判断与所求数字之差是否在数组内。否则，遍历子节点。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D89 653. Two Sum IV - Input is a BST 题目链接 653. Two Sum IV - Input is a BST 题目分析给定一个二叉树以及一个目标数字，判断能不能通过...

HtmlCssJs 2019-07-01 14:01 评论0 收藏0
JavaScript数据结构与算法-Sort-(leetcode原题)

摘要：说明你可以假设数组中所有元素都是非负整数，且数值在位有符号整数范围内。提示按奇偶排序数组给定一个非负整数数组，中一半整数是奇数，一半整数是偶数。对数组进行排序，以便当为奇数时，也是奇数当为偶数时，也是偶数。原博客地址：https://finget.github.io/2019... 排序 showImg(https://segmentfault.com/img/remote/146...

Hanks10100 2019-08-23 18:08 评论0 收藏0