格雷编码

leetcode 89

Posted by songjiu on March 24, 2019

一道很有意思的题目
来自https://leetcode-cn.com/problems/gray-code/

题目描述

解体思想

百度一下格雷码的生成规则,其实就是:把一个数字转换为二进制数后,从右往左每一位都和前一位做异或,最后保留第一位。

代码

def grayCode(self, n: int) -> List[int]:
        return [i ^ i >> 1  for i in range(2 ** n)]

这个代码就十分精髓,首先生成了2的n次方以内的数字i,也就题目要求的上限以内,然后对i和右移一位后的i这两个数进行异或操作,之前有说到格雷码就是从右往左每一位和前一位做异或,所以有这个移位操作。至于如何保持首位不变,移位后的首位一定是0,0与任何数字异或均为他本身,所以当首位是1时,格雷编码的结果首位仍然是1,0则亦然,可以说相当精髓了!!