[LintCode] Gray Code

cocopeak 发布于2019-08-14 15:15 / 2544人阅读

摘要：参考了的算法，简化了一下每个循环更新对应最高位是第位，就增加个数为倒序循环次，会镜像提取上一次循环产生的结果镜像镜像镜像

Problem

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.
http://mathworld.wolfram.com/...

Example

Given n = 2, return [0,1,3,2]. Its gray code sequence is:

Solution

其实就是找规律，0-01-0132－01326754这样，每个循环(i)：

增加当前res.size()个新数；

新的循环先在2进制的第(i+1)位加1，同时与之前res所存的数字倒序相加产生新数；

存入新数，进入下一个循环后更新size。

参考了codesolutiony的算法，简化了一下：

public class Solution {
    public ArrayList grayCode(int n) {
        ArrayList res = new ArrayList();
        res.add(0);
        for (int i = 0; i < n; i++) {
            //每个循环更新size: 1, 3, 7...
            int size = res.size() - 1;
            //i对应最高位是第i+1位，res就增加2^(i+1)个数：(1<= 0; j--) {
                res.add((1<
Recursion
public class Solution {
    public List grayCode(int n) {
        List res = new ArrayList();
        if (n == 0) {
            res.add(0);
            return res;
        }
        res = grayCode(n-1);
        for (int i = res.size()-1; i >= 0; i--) {
            int num = res.get(i);
            res.add(num+(1<<(n-1)));
        }
        return res;
    }
}
Using XOR
public class Solution {
    public List grayCode(int n) {
        List res = new ArrayList();
        for(int i = 0; i < Math.pow(2,n); i++) res.add(i >> 1 ^ i);
        return res;
    }
}

GPU服务器私有云 Gray LintCode LintCode134_LRU Code

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

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

[LeetCode/LintCode] First Bad Version

摘要：分析最后一次循环的时刻当与相差小于时，总是那么如果是，下一次直接跳出循环，返回当与相差大于时，是，变成，如果是，循环结束的条件将是循环结束，返回 Problem The code base version is an integer start from 1 to n. One day, someone committed a bad version in the code case,...

lowett 2019-08-15 15:46 评论0 收藏0
[LintCode/LeetCode] Word Break

Problem Given a string s and a dictionary of words dict, determine if s can be break into a space-separated sequence of one or more dictionary words. Example Given s = lintcode, dict = [lint, code]. R...

dunizb 2019-08-14 15:30 评论0 收藏0
[LintCode] Coins in a Line I & Coins in a Line

摘要：第一个游戏者永远拿不到第枚硬币，所以在硬币总数不能被整除的情况下，都可以赢。做法，设为第一个游戏者从第枚硬币到能获得硬币价值的最大值。主要参考这篇文章的解释 Coins in a Line I Solution 第一个游戏者永远拿不到第3n枚硬币，所以在硬币总数不能被3整除的情况下，都可以赢。 public class Solution { public boolean fi...

xzavier 2019-08-14 15:14 评论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
[LintCode] Nuts & Bolts Problem

Problem Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Comparison of a nut to another nut or a bolt to another bolt is not ...

tuomao 2019-08-14 15:15 评论0 收藏0