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

---

文章目录

• 89. 格雷编码：
• 分析：
• 题解：

---

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 有一位不同

样例 2：

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

提示：

• 1 <= n <= 16

---

分析：

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

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

---

题解：

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;
    }
}

---

---