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

文章目录

89. 格雷编码：

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

• 每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 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

分析：

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

典型的二进制格雷码（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、葛莱码、格莱码、戈莱码、循环码、反射二进制码、最小差错码等名字，它们有的不对，有的易与其它名称混淆，建议不要再使用这些曾用名。

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

题解：

rust：

implSolution{pubfngray_code(n:i32)->Vec<i32>{(0..1<< n).map(|i|{(i >>1)^ i
        }).collect()}}

go：

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

c++：

classSolution{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：

classSolution:defgrayCode(self, n:int)-> List[int]:
        ans =[0]*(1<< n)for i inrange(1<< n):
            ans[i]=(i >>1)^ i
        return ans

java：

classSolution{publicList<Integer>grayCode(int n){List<Integer> ans =newArrayList<Integer>();for(int i =0; i <1<< n;++i){
            ans.add((i >>1)^ i);}return ans;}}

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