[LintCode] Gray Code

cocopeak 發布于2019-08-14 15:15 / 2839人閱讀

摘要：參考了的算法，簡化了一下每個循環更新對應最高位是第位，就增加個數為倒序循環次，會鏡像提取上一次循環產生的結果鏡像鏡像鏡像

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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