[Leetcode] Gray Code 格雷码

Code4App 发布于2019-08-14 12:31 / 2467人阅读

摘要：找规律复杂度时间空间思路仔细观察格雷码当时当时当时可以发现，的格雷码，就是的格雷码，再加上它们的逆序前面多一个。

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 representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.
For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:
00 - 0
01 - 1
11 - 3
10 - 2

Note: For a given n, a gray code sequence is not uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.
For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

找规律 复杂度

时间 O(N) 空间 O(N)

思路

仔细观察格雷码
当n=1时

1
0

当n=2时

当n=3时

可以发现，n的格雷码，就是n-1的格雷码，再加上它们的逆序前面多一个1。

代码

public class Solution {
    public List grayCode(int n) {
        List res = new ArrayList();
        // 加入初始值0
        res.add(0);
        for(int i = 0; i < n; i++){
            // 每一轮的最高位
            int highestBit = 1 << i;
            int size = res.size();
            // 逆序添加上一轮里出现的数，不过开头加上这一轮的最高位
            for(int j = size - 1; j >= 0; j--){
                int num = res.get(j);
                num += highestBit;
                res.add(num);
            }
        }
        return res;
    }
}

公式法 复杂度

时间 O(N) 空间 O(N)

思路

工业中的第i个格雷码是这么生成的：(i>>1)^i
i是指下标，从0开始，对于n的格雷码序列，一共有2^n个数

代码

public class Solution {
    public List grayCode(int n) {
        List res = new ArrayList();
        for(int i = 0; i < 1 << n; i++) res.add((i >> 1)^i);
        return res;
    }
}

GPU云服务器云服务器 Gray 格雷 LeetCode LeetCode_String

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

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

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

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

Youngs 2019-08-26 13:47 评论0 收藏0
LeetCode 89: GrayCode (Java)

摘要：位的格雷码是在位的格雷码前面加或。由上图可以发现，位的格雷码后一位是镜像对称位的格雷码后位是镜像对称位的格雷码后位是镜像对称。规律就是为格雷码是在位格雷码的基础上，先将位镜像对称然后前一半首位添，后一般首位添而得到。 google电面第一轮碰到的题. GrayCode:给定位数n，按规律生成一组二进制代码，直接上例子。 showImg(https://segmentfault.com/...

xiguadada 2019-08-14 15:51 评论0 收藏0
微信小程序中图片上传阿里云Oss

摘要：微信小程序图片上传阿里云服务器也折腾了蛮久才解决的，所以特意去记录一下。上传失败第四步源码在这里如果觉得这面文章对你有帮助的话，可给我点个这里，谢谢最后，希望这篇文章对你有所帮助，真真确确是可以在微信小程序中上传图片到阿里云的。本人今年6月份毕业，最近刚在上海一家小公司实习，做微信小程序开发。最近工作遇到一个小问题。微信小程序图片上传阿里云服务器Oss也折腾了蛮久才解决的，所以特意...

Yang_River 2019-08-29 15:35 评论0 收藏0
微信小程序中图片上传阿里云Oss

摘要：微信小程序图片上传阿里云服务器也折腾了蛮久才解决的，所以特意去记录一下。上传失败第四步源码在这里如果觉得这面文章对你有帮助的话，可给我点个这里，谢谢最后，希望这篇文章对你有所帮助，真真确确是可以在微信小程序中上传图片到阿里云的。本人今年6月份毕业，最近刚在上海一家小公司实习，做微信小程序开发。最近工作遇到一个小问题。微信小程序图片上传阿里云服务器Oss也折腾了蛮久才解决的，所以特意...

netmou 2019-08-26 11:57 评论0 收藏0