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)。注意返回值不计入空间复杂度。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)