題意：提供一個數字n，代表二進制的個數，那么就有2的n次方個可能性了，從0到2^n-1。將其轉成格雷碼，再直接將二進制的格雷碼按二進制的讀法變成整數，裝在vector容器中返回，要有序（否則你直接將0～2^n-1返回算了）。

?

思路：咋一看！什么是格雷碼？假設有1個整數，是二進制形式的，將其最高位的1提出來，其他的每一位等于該位上的數字與該數字的前一位之異或。

　　好像很復雜的樣子？舉例： 整數 21 = 0001 0101 二進制 ，格雷碼前4位是這樣的0001，這就是將二進制的最高位的1提出來啦，那么格雷碼的后4位呢？從左數，格雷碼的第5位 = 二進制的第5位0 異或^ 二進制的第4位1 = 1,此時格雷碼第5位出現了，格雷碼變成0001 1了。第6位呢？從左數，格雷碼的第6位 = 二進制的第6位1 異或^ 二進制的第5位0 = 1，格雷碼為0001 11了，后幾位相信你都會算了。結果格雷碼就是0001 1111。

　　上面的方法在計算機中怎么實現？按規律，反正二進制的每個位上的數字都要和前一位異或，即使最高位，因為最高位肯定是1（出位整數0），而該1之前全是0，那么1和0的異或仍是1啦。這樣的話，直接將我們的整數右移一位，再與原來整數異或的結果，就是我們要的格雷碼，雖然它讀出來不再是原來的整數，但是它的二進制形式就是該整數對應的格雷碼了。 假如有一個整數a=7，二進制是0000 0111，改成格雷碼是0000 0100，這個格雷碼按整數的二進制讀法將其翻譯成整數是4，這就是vector[7]=4。簡單吧？

?

1 class Solution { 2 public: 3 vector<int> grayCode(int n) { 4 vector<int> ans; 5 int m = (1<<n) ; //一共有m個數要返回 6 ans.resize(m); //先把m個數字置為0，還幫你一次性設好內存，多方便！ 7 int count = 0; 8 for(int i=1; i<m ;i++ ) //對第i個數字的處理 9 { 10 count++; 11 ans[i] = ( count >> 1 ) ^ count; 12 } 13 return ans; 14 } 15 }; grayCode

?

轉載于:https://www.cnblogs.com/xcw0754/p/4379560.html

總結

以上是生活随笔為你收集整理的LeetCode Gray Code 格雷码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。