[Leetcode] Gray Code 格雷碼

Code4App 發(fā)布于2019-08-14 12:31 / 2468人閱讀

摘要：找規(guī)律復(fù)雜度時(shí)間空間思路仔細(xì)觀察格雷碼當(dāng)時(shí)當(dāng)時(shí)當(dāng)時(shí)可以發(fā)現(xiàn)，的格雷碼，就是的格雷碼，再加上它們的逆序前面多一個(gè)。

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.

找規(guī)律 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

仔細(xì)觀察格雷碼
當(dāng)n=1時(shí)

1
0

當(dāng)n=2時(shí)

當(dāng)n=3時(shí)

可以發(fā)現(xiàn)，n的格雷碼，就是n-1的格雷碼，再加上它們的逆序前面多一個(gè)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();
            // 逆序添加上一輪里出現(xiàn)的數(shù)，不過(guò)開(kāi)頭加上這一輪的最高位
            for(int j = size - 1; j >= 0; j--){
                int num = res.get(j);
                num += highestBit;
                res.add(num);
            }
        }
        return res;
    }
}

公式法 復(fù)雜度

時(shí)間 O(N) 空間 O(N)

思路

工業(yè)中的第i個(gè)格雷碼是這么生成的：(i>>1)^i
i是指下標(biāo)，從0開(kāi)始，對(duì)于n的格雷碼序列，一共有2^n個(gè)數(shù)

代碼

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;
    }
}