No89. 格雷編碼
題目
格雷編碼是一個二進制數字系統，在該系統中，兩個連續的數值僅有一個位數的差異，
給定一個代表編碼總位數的非負整數 n，列印其格雷編碼序列，即使有多個不同答案，你也只需要回傳其中一種，
格雷編碼序列必須以 0 開頭，
示例1
- 輸入: 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
示例2
- 輸入: 0
- 輸出: [0]
- 解釋: 我們定義格雷編碼序列必須以 0 開頭，
給定編碼總位數為 n 的格雷編碼序列，其長度為 2n，當 n = 0 時，長度為 20 = 1，
因此，當 n = 0 時，其格雷編碼序列為 [0]，
思路：
G ( n ) = n ⊕ ? n 2 ? G(n) = n \oplus \left \lfloor \frac{n}{2} \right \rfloor G(n)=n⊕?2n??
利用上面的公式，很容易進行求解，簡單理解一下：
當n的二進制表示形式為1000時，n>>1為0100，異或結果為1100
此時n+1為1001，n>>1為0100，異或結果為1101
以此類推，由于n的不同所以可以保證異或結果不同，由G(n+1)和G(n)的遞推關系可以保證相鄰兩個格雷編碼的有效性，
解題代碼(Python3)
class Solution:
def grayCode(self, n: int) -> List[int]:
return [i^(i>>1) for i in range(1<<n)]
復雜度分析：
- 時間復雜度 O(n)
- 空間復雜度 O(2*n)
運行結果：
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/257711.html
標籤：其他
上一篇：沒有ipad上架怎么截屏
下一篇：Jekyll安裝與本地構建