【LeetCode】Day33-格雷编码-位运算

89.格雷编码

n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
        每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
        第一个整数是 0
        一个整数在序列中出现 不超过一次
        每对 相邻 整数的二进制表示 恰好一位不同 ，且第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。

python位运算符：链接

本题解释见：leetcode官方 

解答：

class Solution:
    def grayCode(self, n: int) -> List[int]:
        ans = [0]
        for i in range(1, n + 1):
            for j in range(len(ans) - 1, -1, -1):
                ans.append(ans[j] | (1 << (i - 1)))
        return ans


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

复杂度：

时间复杂度：O(2^n)；

空间复杂度：O(1)。注意返回值不计入空间复杂度。