每日一题leetcode89.格雷编码

题目:
n 位格雷码序列 是一个由 2^n 个整数组成的序列,其中:

  • 每个整数都在范围 [0, 2^(n - 1)] 内(含 0 和 2^(n - 1))
  • 第一个整数是 0
  • 一个整数在序列中出现 不超过一次
  • 每对 相邻 整数的二进制表示 恰好一位不同 ,且
  • 第一个 和 最后一个 整数的二进制表示 恰好一位不同
    给你一个整数 n ,返回任一有效的 n 位格雷码序列 。
    每日一题leetcode89.格雷编码
    思路:
    对称生成:每日一题leetcode89.格雷编码

解答:
方法一:官方解答

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

方法二:个人解答

ans为n=0时的结果

class Solution:
    def grayCode(self, n: int) -> List[int]:
        ans = [0]
        for i in range(1, n + 1):
            #对数组进行反转,再加上2^(i-1)
            for j in range(len(ans) - 1, -1, -1):
                ans.append(ans[j]+ 2**(i - 1))
        return ans

ans为n=1时的结果

class Solution:
    def grayCode(self, n: int) -> List[int]:
        ans = [0,1]
        for i in range(2, n + 1):
            #对数组进行反转,再加上2^(i-1)
            for j in range(len(ans) - 1, -1, -1):
                ans.append(ans[j]+ 2**(i - 1))
        return ans
上一篇:最长回文字符串


下一篇:循环基本语法