今天小編給大家分享一下C++怎么解決格雷碼問題的相關知識點,內容詳細,邏輯清晰,相信大部分人都還太了解這方面的知識,所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來了解一下吧。
成都創新互聯公司是一家專業提供長洲企業網站建設,專注與做網站、成都網站建設、H5響應式網站、小程序制作等業務。10年已為長洲眾多企業、政府機構等服務。創新互聯專業網站制作公司優惠進行中。
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.
這道題是關于格雷碼的,猛地一看感覺完全沒接觸過格雷碼,但是看了維基百科后,隱約的感覺原來好像哪門可提到過,哎全還給老師了。這道題如果不了解格雷碼,還真不太好做,幸虧腦補了維基百科,上面說格雷碼是一種循環二進制單位距離碼,主要特點是兩個相鄰數的代碼只有一位二進制數不同的編碼,格雷碼的處理主要是位操作 Bit Operation,LeetCode中關于位操作的題也挺常見,比如 Repeated DNA Sequences 求重復的DNA序列, Single Number 單獨的數字, 和 Single Number II 單獨的數字之二 等等。三位的格雷碼和二進制數如下:
Int Grey Code Binary
0 000 000
1 001 001
2 011 010
3 010 011
4 110 100
5 111 101
6 101 110
7 100 111
其實這道題還有多種解法。首先來看一種最簡單的,是用到格雷碼和二進制數之間的相互轉化,可參見我之前的博客 Convertion of grey code and binary 格雷碼和二進制數之間的轉換 ,明白了轉換方法后,這道題完全沒有難度,代碼如下:
解法一:
// Binary to grey code class Solution { public: vector<int> grayCode(int n) { vector<int> res; for (int i = 0; i < pow(2,n); ++i) { res.push_back((i >> 1) ^ i); } return res; } };
然后我們來看看其他的解法,參考維基百科上關于格雷碼的性質,有一條是說鏡面排列的,n位元的格雷碼可以從n-1位元的格雷碼以上下鏡射后加上新位元的方式快速的得到,如下圖所示一般。
有了這條性質,我們很容易的寫出代碼如下:
解法二:
// Mirror arrangement class Solution { public: vector<int> grayCode(int n) { vector<int> res{0}; for (int i = 0; i < n; ++i) { int size = res.size(); for (int j = size - 1; j >= 0; --j) { res.push_back(res[j] | (1 << i)); } } return res; } };
維基百科上還有一條格雷碼的性質是直接排列,以二進制為0值的格雷碼為第零項,第一項改變最右邊的位元,第二項改變右起第一個為1的位元的左邊位元,第三、四項方法同第一、二項,如此反復,即可排列出n個位元的格雷碼。根據這條性質也可以寫出代碼,不過相比前面的略微復雜,代碼如下:
0 0 0
0 0 1
0 1 1
0 1 0
1 1 0
1 1 1
1 0 1
1 0 0
解法三:
// Direct arrangement class Solution { public: vector<int> grayCode(int n) { vector<int> res{0}; int len = pow(2, n); for (int i = 1; i < len; ++i) { int pre = res.back(); if (i % 2 == 1) { pre = (pre & (len - 2)) | ((~pre) & 1); } else { int cnt = 1, t = pre; while ((t & 1) != 1) { ++cnt; t >>= 1; } if ((pre & (1 << cnt)) == 0) pre |= (1 << cnt); else pre &= ~(1 << cnt); } res.push_back(pre); } return res; } };
上面三種解法都需要事先了解格雷碼及其性質,假如我們之前并沒有接觸過格雷碼,那么我們其實也可以用比較笨的方法來找出結果,比如下面這種方法用到了一個set來保存已經產生的結果,我們從0開始,遍歷其二進制每一位,對其取反,然后看其是否在set中出現過,如果沒有,我們將其加入set和結果res中,然后再對這個數的每一位進行遍歷,以此類推就可以找出所有的格雷碼了,參見代碼如下:
解法四:
class Solution { public: vector<int> grayCode(int n) { vector<int> res; unordered_set<int> s; helper(n, s, 0, res); return res; } void helper(int n, unordered_set<int>& s, int out, vector<int>& res) { if (!s.count(out)) { s.insert(out); res.push_back(out); } for (int i = 0; i < n; ++i) { int t = out; if ((t & (1 << i)) == 0) t |= (1 << i); else t &= ~(1 << i); if (s.count(t)) continue; helper(n, s, t, res); break; } } };
既然遞歸方法可以實現,那么就有對應的迭代的寫法,當然需要用stack來輔助,參見代碼如下:
解法五:
class Solution { public: vector<int> grayCode(int n) { vector<int> res{0}; unordered_set<int> s; stack<int> st; st.push(0); s.insert(0); while (!st.empty()) { int t = st.top(); st.pop(); for (int i = 0; i < n; ++i) { int k = t; if ((k & (1 << i)) == 0) k |= (1 << i); else k &= ~(1 << i); if (s.count(k)) continue; s.insert(k); st.push(k); res.push_back(k); break; } } return res; } };
以上就是“C++怎么解決格雷碼問題”這篇文章的所有內容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會為大家更新不同的知識,如果還想學習更多的知識,請關注創新互聯行業資訊頻道。
分享標題:C++怎么解決格雷碼問題
URL分享:http://m.newbst.com/article22/pgcejc.html
成都網站建設公司_創新互聯,為您提供品牌網站設計、面包屑導航、營銷型網站建設、企業建站、網站制作、做網站
聲明:本網站發布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網站立場,如需處理請聯系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創新互聯