算法leetcode｜89. 格雷编码（rust重拳出击）

---

---

89. 格雷编码：

n 位格雷码序列 是一个由 2ⁿ 个整数组成的序列，其中：

• 每个整数都在范围 [0, 2ⁿ - 1] 内（含 0 和 2ⁿ - 1）
• 第一个整数是 0
• 一个整数在序列中出现 不超过一次
• 每对 相邻 整数的二进制表示 恰好一位不同 ，且
• 第一个 和 最后一个 整数的二进制表示 恰好一位不同

给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

样例 1：

输入：
	
	n = 2
	
输出：
	
	[0,1,3,2]
	
解释：

	[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
	- 00 和 01 有一位不同
	- 01 和 11 有一位不同
	- 11 和 10 有一位不同
	- 10 和 00 有一位不同
	[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
	- 00 和 10 有一位不同
	- 10 和 11 有一位不同
	- 11 和 01 有一位不同
	- 01 和 00 有一位不同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

样例 2：

输入：
	
	n = 1
	
输出：
	
	[0,1]
1
2
3
4
5
6
7

提示：

• 1 <= n <= 16

---

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 先看看什么是格雷码：

典型的二进制格雷码（Binary Gray Code）简称格雷码，因1953年公开的弗兰克·格雷（Frank Gray，18870913-19690523）专利“Pulse Code Communication”而得名，当初是为了通信，现在则常用于模拟－数字转换和位置－数字转换中。法国电讯工程师波特（Jean-Maurice-Émile Baudot，18450911-19030328）在1880年曾用过的波特码相当于它的一种变形。1941年George Stibitz设计的一种8元二进制机械计数器正好符合格雷码计数器的计数规律。
在一组数的编码中，若任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code），另外由于最大数与最小数之间也仅一位数不同，即“首尾相连”，因此又称循环码或反射码。
在数字系统中，常要求代码按一定顺序变化。例如，按自然数递增计数，若采用8421码，则数0111变到1000时四位均要变化，而在实际电路中，4位的变化不可能绝对同时发生，则计数中可能出现短暂的其它代码（1100、1111等）。在特定情况下可能导致电路状态错误或输入错误。使用格雷码可以避免这种错误。格雷码有多种编码形式。
格雷码（Gray Code）曾用过Grey Code、葛莱码、格莱码、戈莱码、循环码、反射二进制码、最小差错码等名字，它们有的不对，有的易与其它名称混淆，建议不要再使用这些曾用名。

• 重点是相邻的码只能有一位不同。
• 这题我姑且说它是经验题或者是脑筋急转弯吧，模拟就可以了。
• 前人根据规律给出了公式 g_i​ = i ^ (i / 2)，这样可以轻松保证相邻两个码只有一位不同。

---

题解：

rust：

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

---

go：

func grayCode(n int) []int {
    ans := make([]int, 1<<n)
	for i := range ans {
		ans[i] = (i >> 1) ^ i
	}
	return ans
}
1
2
3
4
5
6
7

---

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;
    }
};
1
2
3
4
5
6
7
8
9
10

---

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

1
2
3
4
5
6
7

---

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;
    }
}
1
2
3
4
5
6
7
8
9

---

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~

---