leetcode 89：格雷编码(python)

╰半夏微凉° 2024-04-19 13:20 53阅读 0赞

# 题目 #

格雷编码是一个**二进制数字系统**，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表**编码总位数**的非负整数 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\]。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/gray-code  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

# 解法一（2位循环添加） #

*  思路  
    对每两个二进制位进行处理  
    将上一次循环留下的数按位移2位，再依次加上\[0,1,3,2\]  
    （为了使每4个数连接时无1个以上数字变化，必须以正反正反的方式扩大数组）  
    如：  
    n=2 ——>\[0,1,3,2\] (00,01,11,10)  
    n=4 ——>  
    \[0,1,3,2,2,3,1,0,0,1,3,2,2,3,1,0\]<<2  
    \+  
    \[0,0,0,0,1,1,1,1,3,3,3,3,2,2,2,2\]  
    (00 00+00即00 00=0  
    01 00即01 00=4  
    11 00+00即11 00=12  
    10 00+00即10 00=8  
    10 00+01即10 01=9  
    ……  
    11 00+10即11 10=14  
    00 00+10即00 10=2)
 *  代码

class Solution:
        def grayCode(self, n: int) -> List[int]:
            if n<2:
                return [num for num in range(n+1)]
            res=k=[0,1,3,2]
            i,lens=4,2**n
            while(i*4<=lens):
                res=res+res[::-1]
                res=res*2
                for j in range(i*4):
                    res[j]=(res[j]<<2)+k[j//i]
                i*=4
            if i!=lens:
                res=res+res[::-1]
                k=1<<(n-1)
                for j in range(i):
                    res[-j-1]+=k
            return res

*  结果  
    ![在这里插入图片描述][20190920183323657.png]

# 解法二（逐位循环添加） #

*  思路  
    将上一次循环留下的数逆序，再按位移1位，最后在二进制最前的一位前再加上1<<（n-2），将所得新数组接到原数组后面。  
    n=1 ——>\[0,1\] (0,1)  
    n=2 ——>\[0,2,3,1\]  
    1<<（2-2）=1  
    \[0,1,1,0\]<<1  
    \+  
    \[0,0,1,1\]  
    (00 0+0即00 0=0  
    01 0+0即01 0=2  
    01 0+1即01 1=3  
    00 0+1即00 1=1)
 *  代码

class Solution:
        def grayCode(self, n: int) -> List[int]:
            res=[0]
            i=0
            while(i<n):
                rres=res[::-1]
                k=1<<i
                for j in range(len(rres)):
                    rres[j]+=k
                res+=rres
                i+=1
            return res

*  结果  
    ![在这里插入图片描述][20190920185647246.png]

[20190920183323657.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/44c1551cc6554afc91062d5faa69b3cb.png
[20190920185647246.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/0dfb16bdfc404832bf7a904cb11aa122.png