子寒的博客
0%

leetcode89 Gray Code 解题报告

发表于 分类于

英文原题

An n-bit gray code sequence is a sequence of 2n integers where:

Every integer is in the inclusive range [0, 2n - 1], The first integer is 0, An integer appears no more than once in the sequence, The binary representation of every pair of adjacent integers differs by exactly one bit, and The binary representation of the first and last integers differs by exactly one bit. Given an integer n, return any valid n-bit gray code sequence.

Example

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: n = 2
Output: [0,1,3,2]
Explanation:
The binary representation of [0,1,3,2] is [00,01,11,10].
- 00 and 01 differ by one bit
- 01 and 11 differ by one bit
- 11 and 10 differ by one bit
- 10 and 00 differ by one bit
[0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01].
- 00 and 10 differ by one bit
- 10 and 11 differ by one bit
- 11 and 01 differ by one bit
- 01 and 00 differ by one bit

分析

    gray code这个东西其实就是一个找规律题，对于第n+1个gray code 来说，他的前2n个数是第n个gray code 的全部，后2n个是第n个gray code 倒序加2**n 。

python 代码

1
2
3
4
5
6
7
8
9
10
class Solution:
    def grayCode(self, n: int) -> List[int]:
        grayCode = []
        grayCode.append([0, 1])
        
        for i in range(1, n):
            newCode = grayCode[i-1] + [code + 2 ** i for code in grayCode[i-1]][::-1]
            grayCode.append(newCode)
            
        return grayCode[-1]