Leetcode題解 Gray Code

點擊上方「程式設計師大白」，選擇「星標」公眾號

重磅乾貨，第一時間送達

題目分析：

給出數字N,要求生成位數不大於N的格雷碼序列。  

格雷碼：在一組數的編碼中，若任意兩個相鄰的代碼只有一位二進位數不同，則稱這種編碼為格雷碼（Gray Code）

解題思路:  

簡單的模擬生成題，由于格雷碼要求相鄰的數字有且僅有一位不同，先考慮如果當前已經有不大於N-1位的合法格雷碼序列  如現在已經有不大於2位的合法格雷碼序列——000、001、011、010    

最簡單直接的方式便是將上述序列複製一遍，將其第N位全置為1。則在上述所得到的副本內部，彼此之前滿足相鄰數字有且僅有一位不同的要求。而後考慮將副本與原先的進行拼接，發現副本最尾端的是由原序列最尾端的數字派生出來。因此，將副本翻轉順序後和原序列拼接即可獲得不大於N的合法格雷碼序列。  算法過程如下：

初始化序列，將0加入其中,i=1。

生成不大於i位的序列，從原序列尾端往前依次取出一數字x，令y = x | (1<<i);，後將y加入答案序列之中。

i = i+1，若i>N則結束，否則回到過程2。  

整體而言，生成每個格雷碼僅需要一次運算，因此時間複雜度為O(2^N).

CPP代碼

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans;
        ans.push_back(0);
        if(n==0) return ans;
        ans.push_back(1);
        int down=1;
        for(int T=1; T<n; T++)
        {
            for(int i=down; i!= -1; i--)
            {
                int x = ans[i] | (1<<T);//產生新的數字
                ans.push_back(x);
            }
                down = ans.size();//重新確定當前的下界
        }
        return ans;
    }
};
重磅！程式設計師大白交流群-學術微信交流群已成立
額外贈送福利資源！邱錫鵬深度學習與神經網絡，pytorch官方中文教程，利用Python進行數據分析，機器學習學習筆記，pandas官方文檔中文版，effective java（中文版）等20項福利資源
獲取方式：進入群後點開群公告即可領取下載連結
昨晚拉人小助手出了問題，最近不能使用，請大家加入微信2群
注意：請大家添加時修改備註為 [學校/公司 + 姓名 + 方向]
例如 —— 哈工大+張三+對話系統。
號主，微商請自覺繞道。謝謝！
推薦閱讀
Leetcode題解 SimplifyPath
Leetcode題解 InsertInterval
Leetcode題解 MergeIntervals
Leetcode題解 JumpGame
Leetcode題解 N-Queens
Leetcode題解 Trapping Rain Water
關於程式設計師大白
程式設計師大白是一群哈工大，東北大學，西湖大學和上海交通大學的碩士博士運營維護的號，大家樂於分享高質量文章，喜歡總結知識，歡迎關注[程式設計師大白]，大家一起學習進步！