89. 格雷編碼：

n 位格雷碼序列 是一個(gè)由 2ⁿ 個(gè)整數(shù)組成的序列，其中：

• 每個(gè)整數(shù)都在范圍 [0, 2ⁿ - 1] 內(nèi)（含 0 和 2ⁿ - 1）
• 第一個(gè)整數(shù)是 0
• 一個(gè)整數(shù)在序列中出現(xiàn) 不超過一次
• 每對(duì) 相鄰 整數(shù)的二進(jìn)制表示 恰好一位不同 ，且
• 第一個(gè) 和 最后一個(gè) 整數(shù)的二進(jìn)制表示 恰好一位不同

給你一個(gè)整數(shù) n ，返回任一有效的 n 位格雷碼序列 。

樣例 1：

輸入：
	
	n = 2
	
輸出：
	
	[0,1,3,2]
	
解釋：

	[0,1,3,2] 的二進(jìn)制表示是 [00,01,11,10] 。
	- 00 和 01 有一位不同
	- 01 和 11 有一位不同
	- 11 和 10 有一位不同
	- 10 和 00 有一位不同
	[0,2,3,1] 也是一個(gè)有效的格雷碼序列，其二進(jìn)制表示是 [00,10,11,01] 。
	- 00 和 10 有一位不同
	- 10 和 11 有一位不同
	- 11 和 01 有一位不同
	- 01 和 00 有一位不同

樣例 2：

輸入：
	
	n = 1
	
輸出：
	
	[0,1]

提示：

• 1 <= n <= 16

分析：

• 面對(duì)這道算法題目，二當(dāng)家的再次陷入了沉思。
• 先看看什么是格雷碼：

典型的二進(jìn)制格雷碼（Binary Gray Code）簡(jiǎn)稱格雷碼，因1953年公開的弗蘭克·格雷（Frank Gray，18870913-19690523）專利“Pulse Code Communication”而得名，當(dāng)初是為了通信，現(xiàn)在則常用于模擬－數(shù)字轉(zhuǎn)換和位置－數(shù)字轉(zhuǎn)換中。法國(guó)電訊工程師波特（Jean-Maurice-émile Baudot，18450911-19030328）在1880年曾用過的波特碼相當(dāng)于它的一種變形。1941年George Stibitz設(shè)計(jì)的一種8元二進(jìn)制機(jī)械計(jì)數(shù)器正好符合格雷碼計(jì)數(shù)器的計(jì)數(shù)規(guī)律。
在一組數(shù)的編碼中，若任意兩個(gè)相鄰的代碼只有一位二進(jìn)制數(shù)不同，則稱這種編碼為格雷碼（Gray Code），另外由于最大數(shù)與最小數(shù)之間也僅一位數(shù)不同，即“首尾相連”，因此又稱循環(huán)碼或反射碼。
在數(shù)字系統(tǒng)中，常要求代碼按一定順序變化。例如，按自然數(shù)遞增計(jì)數(shù)，若采用8421碼，則數(shù)0111變到1000時(shí)四位均要變化，而在實(shí)際電路中，4位的變化不可能絕對(duì)同時(shí)發(fā)生，則計(jì)數(shù)中可能出現(xiàn)短暫的其它代碼（1100、1111等）。在特定情況下可能導(dǎo)致電路狀態(tài)錯(cuò)誤或輸入錯(cuò)誤。使用格雷碼可以避免這種錯(cuò)誤。格雷碼有多種編碼形式。
格雷碼（Gray Code）曾用過Grey Code、葛萊碼、格萊碼、戈萊碼、循環(huán)碼、反射二進(jìn)制碼、最小差錯(cuò)碼等名字，它們有的不對(duì)，有的易與其它名稱混淆，建議不要再使用這些曾用名。

• 重點(diǎn)是相鄰的碼只能有一位不同。
• 這題我姑且說它是經(jīng)驗(yàn)題或者是腦筋急轉(zhuǎn)彎吧，模擬就可以了。
• 前人根據(jù)規(guī)律給出了公式 g_i? = i ^ (i / 2)，這樣可以輕松保證相鄰兩個(gè)碼只有一位不同。

題解：

rust：

impl Solution {
    pub fn gray_code(n: i32) -> Vec<i32> {
        (0..1 << n).map(|i| {
            (i >> 1) ^ i
        }).collect()
    }
}

go：

func grayCode(n int) []int {
    ans := make([]int, 1<<n)
	for i := range ans {
		ans[i] = (i >> 1) ^ i
	}
	return ans
}

c++：

class Solution {
public:
    vector<int> grayCode(int n) {
        vector<int> ans(1 << n);
        for (int i = 0; i < ans.size(); ++i) {
            ans[i] = (i >> 1) ^ i;
        }
        return ans;
    }
};

python：

class Solution:
    def grayCode(self, n: int) -> List[int]:
        ans = [0] * (1 << n)
        for i in range(1 << n):
            ans[i] = (i >> 1) ^ i
        return ans

java：

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < 1 << n; ++i) {
            ans.add((i >> 1) ^ i);
        }
        return ans;
    }
}

非常感謝你閱讀本文~
歡迎【點(diǎn)贊】【收藏】【評(píng)論】三連走一波~
放棄不難，但堅(jiān)持一定很酷~
希望我們大家都能每天進(jìn)步一點(diǎn)點(diǎn)~
本文由 二當(dāng)家的白帽子：https://le-yi.blog.csdn.net/ 博客原創(chuàng)~文章來源地址http://www.zghlxwxcb.cn/news/detail-758042.html

到了這里，關(guān)于算法leetcode｜89. 格雷編碼（rust重拳出擊）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！