首页 > 代码库 > LeetCode: Gray Code 解题报告

LeetCode: Gray Code 解题报告

Gray 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.

SOLUTION 1:

我们可以使用递归来做。规律是:

一部分是n-1位格雷码,再加上 1<<(n-1)和n-1位格雷码的逆序的和。

具体可以看维基的解释: http://zh.wikipedia.org/wiki/格雷码

格雷碼能避免訊號傳送錯誤的原理
傳統的二進位系統例如數字3的表示法為011,要切換為鄰近的數字4,也就是100時,裝置中的三個位元都得要轉換,因此於未完全轉換的過程時裝置會經歷短暫的,010,001,101,110,111等其中數種狀態,也就是代表著2、1、5、6、7,因此此種數字編碼方法於鄰近數字轉換時有比較大的誤差可能範圍。葛雷碼的發明即是用來將誤差之可能性縮減至最小,編碼的方式定義為每個鄰近數字都只相差一個位元,因此也稱為最小差異碼,可以使裝置做數字步進時只更動最少的位元數以提高穩定性。 數字0~7的編碼比較如下:

十進位 葛雷碼 二進位

0     000    000
1     001    001
2     011    010
3     010    011
4     110    100
5     111    101
6     101    110
7     100    111

 1 public class Solution { 2     public List<Integer> grayCode(int n) { 3         List<Integer> ret = new ArrayList<Integer>(); 4         if (n == 0) { 5             ret.add(0); 6             return ret; 7         } 8          9         ret = grayCode(n - 1);10         11         for (int i = ret.size() - 1; i >= 0; i--) {12             int num = ret.get(i);13             num += 1 << (n - 1);14             ret.add(num);15         }16         17         return ret;18     }19 }

GITHUB:

https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/recursion/GrayCode.java

 

REF:

http://blog.csdn.net/fightforyourdream/article/details/14517973

 

LeetCode: Gray Code 解题报告