首页 > 代码库 > 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 解题报告