題目描述:格雷編碼是一個二進制數字系統,在該系統中,兩個連續的數值僅有一個位數的差異。給定一個代表編碼總位數的非負整數 n,列印其格雷編碼序列。格雷編碼序列必須以 0 開頭。
示例 1:示例 2:輸入: 2 輸出: [0,1,3,2] 解釋: 00 - 0 01 - 1 11 - 3 10 - 2 對于給定的 n,其格雷編碼序列并不唯一。例如,[0,2,3,1]也是一個有效的格雷編碼序列。 00 - 0 10 - 2 11 - 3 01 - 1
輸入: 0 輸出: [0] 解釋: 我們定義格雷編碼序列必須以 0 開頭。給定編碼總位數為n 的格雷編碼序列,其長度為 2n。當 n = 0 時,長度為 20 = 1。是以,當 n = 0 時,其格雷編碼序列為 [0]。
解法1。查到格雷碼和二進制數之間的轉換關系就行了,然後根據輸入n的值,知道輸出應該為2^n個,如下
class Solution(object):
def grayCode(self, n):
"""
:type n: int
:rtype: List[int]
"""
if n <= 0:
return [0]
res = []
for i in range(2**n):
res.append((i>>1)^i)
return res
解法2。i每加1,其實就是在i-1的結果逆序後高位添1,如下圖所示,親測結果也是。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnLnZ3cu42bpR3Y1JHdz52bj9VZk92YflXYyd0XkVGdjVGbmVmctknch5WaC1CewBTNy8CXnZ3cu42bpR3Y1JHdz52bj9VZk92YflXYyd0XkVGdjVGbmVmctknch5WaC9CXxM2LcN2LcJWb1hGdvw1cu9Wbt92YvwVYpRWZwl2apd3Lcdmcv5SYpRWZtl2apdnLkF2bsBXdvw1LcpDc0RHaiojIsJye.png)
class Solution(object):
def grayCode(self, n):
"""
:type n: int
:rtype: List[int]
"""
if n <= 0:
return [0]
res = [0]
for i in range(n):
m = len(res)
for j in range(m-1, -1, -1):
res.append((res[j] | (1<<i)))
return res
參考連結:http://www.cnblogs.com/grandyang/p/4315649.html