# Gray Code ### Source - leetcode: [Gray Code | LeetCode OJ](https://leetcode.com/problems/gray-code/) - lintcode: [(411) Gray Code](http://www.lintcode.com/en/problem/gray-code/) ### Problem 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, find the sequence of gray code. A gray code sequence must begin with 0 and with cover all 2n2^n2n integers. #### 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. `[0,2,3,1]` is also a valid gray code sequence according to the above definition. #### Challenge O(2n)O(2^n)O(2n) time. ### 題解 第一次遇到這個題是在騰訊的在線筆試中，當時找到了規律，用的是遞歸，但是實現似乎有點問題... 直接從 n 位的格雷碼分析不太好分析，比如題中`n = 2`的格雷碼，我們不妨試試從小到大分析，以 `n = 1` 往后遞推。  從圖中我們可以看出n 位的格雷碼可由 n-1位的格雷碼遞推，在最高位前順序加0，逆序加1即可。實際實現時我們可以省掉在最高位加0的過程，因為其在數值上和前 n-1位格雷碼相同。另外一點則是初始化的處理，圖中為從1開始，但若從0開始可進一步簡化程序。而且根據 [格雷碼](https://zh.wikipedia.org/wiki/%E6%A0%BC%E9%9B%B7%E7%A0%81) 的定義，n=0時確實應該返回0. ### Java ~~~ public class Solution { /** * @param n a number * @return Gray code */ public ArrayList<Integer> grayCode(int n) { if (n < 0) return null; ArrayList<Integer> currGray = new ArrayList<Integer>(); currGray.add(0); for (int i = 0; i < n; i++) { int msb = 1 << i; // backward - symmetry for (int j = currGray.size() - 1; j >= 0; j--) { currGray.add(msb | currGray.get(j)); } } return currGray; } } ~~~ ### 源碼分析 加0 的那一部分已經在前一組格雷碼中出現，故只需將前一組格雷碼鏡像后在最高位加1即可。第二重 for 循環中需要注意的是`currGray.size() - 1`并不是常量，只能用于給 j 初始化。本應該使用 2n2^n2n 和上一組格雷碼相加，這里考慮到最高位為1的特殊性，使用位運算模擬加法更好。 ### 復雜度分析 生成n 位的二進制碼，時間復雜度 O(2n)O(2^n)O(2n), 使用了`msb`代表最高位的值便于后續相加，空間復雜度 O(1)O(1)O(1). ### Reference - Soulmachine 的 leetcode 題解