leetcode89.格雷编码题解

ksqqorz

思路：
格雷码在通信和IC数据跨时钟域经常使用，其将0-2^n的数据按照每两个数只变化一个bit位的顺序排列。

本题考查如何生成一个格雷排列(n不超过16)。

这里是类似递归的一种处理，如果使用暴力处理，需要极大的空间和试错。
我们考虑从n为i的格雷码生成i+1的格雷码的方法


这里从i到i+1会增加一倍的数，我们这里0 -- 2^i-1的生成已经完成，这里最高位一直是0，
即 0{xxxx0} -> 0{xxxxx}。
这里从2^i -- 2^(i+1)-1的数据要根据前面的数据生成，最高位必须为1，而且第一个数据已经确定为第2^i-1个数据将最高bit为调为1得到。
0{00000} （第0个） -> 0{xxxxx}（第2^i -1个）-> 1{xxxx}  (第2^i个)。
这里我们按照第0->(2^i -1)的bit位变化方法，不过由于不是从0开始，所以需要考虑如何从0转换到1{xxxx}；这里考虑到这里0->1的bit翻转方式，我们可以知道异或的操作对于该方式是(兼容)的，即将0->(2^i -1)均异或上1{xxxx}这个数据，那么即可以完成后面2^i个数据的生成。

这里我们即可以根据n来递归实现。
python实现：

[Python] 纯文本查看 复制代码

class Solution:
    def grayCode(self, n: int) -> List[int]:
        if n>1:
            M = self.grayCode(n-1)[-1]+(1<<(n-1))
            return self.grayCode(n-1) + [(a^M) for a in self.grayCode(n-1)]
        else:
            return [0,1] 

代码写的快，跑起来结果当然比较慢：

尾记：
思路应该OK，要提速就要从list的生成出发，这里list反复调用加减是很费时的操作，直接拉一个list，在里面操作数据肯定会加速很多。
这里懒得折腾了。。。

阳光肥肥

其实提速也没太麻烦
直接在函数头上加一句@cache就行了 就是把之前结果缓存一下
耗时36ms击败百分之93.....

[Python] 纯文本查看 复制代码

class Solution:
    @cache
    def grayCode(self, n: int) -> List[int]:
        if n>1:
            M = self.grayCode(n-1)[-1]+(1<<(n-1))
            return self.grayCode(n-1) + [(a^M) for a in self.grayCode(n-1)]
        else:
            return [0,1]

不过这个题还是建议看题解区第一个，k神的题解

ksqqorz

阳光肥肥 发表于 2021-11-20 18:58
其实提速也没太麻烦
直接在函数头上加一句@cache就行了 就是把之前结果缓存一下
耗时36ms击败百分之93... ...

确实，尽可能减少计算以及计算复杂度，复用现有数据，以及这个cache。学到了。