[Leetcode] Gray Code 格雷碼

Code4App 發布于2019-08-14 12:31 / 2477人閱讀

摘要：找規律復雜度時間空間思路仔細觀察格雷碼當時當時當時可以發現，的格雷碼，就是的格雷碼，再加上它們的逆序前面多一個。

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

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

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