算法题--生成格雷码

image.png

0. 链接

题目链接

1. 题目

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

Example 1:

Input: 2
Output: [0,1,3,2]
Explanation:
00 - 0
01 - 1
11 - 3
10 - 2

For a given n, a gray code sequence may not be uniquely defined.
For example, [0,2,3,1] is also a valid gray code sequence.

00 - 0
10 - 2
11 - 3
01 - 1

Example 2:

Input: 0
Output: [0]
Explanation: We define the gray code sequence to begin with 0.
             A gray code sequence of n has size = 2n, which for n = 0 the size is 20 = 1.
             Therefore, for n = 0 the gray code sequence is [0].

2. 思路1：动态规划

• n = 1时

0 -> 1

• n = 2时

[00 -> 01] -> [11 -> 10]

• n = 3时

[000 -> 001 -> 011 -> 010] -> [110 -> 111 -> 101 -> 100]

可以看到，n对应的码，相当于n-1对应的码从左到右将高位增加一个0，然后再从右到左将高位增加一个1来获得

这个就可以用到动态规划了

• 重叠子问题: 再求取f(n)的时候, 需要用到f(1); 再求取f(n-1)的时候, 也需要用到f(1), 所以存在重叠子问题
• 最优子结构: 可以通过子问题的解，推出父问题的解，这个也满足
• 状态转移方程： f(n) = f(n - 1)的码从左到右高位补0 + f(n - 1)的码从右到左高位补1

3. 代码

# coding:utf8

from typing import List


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

def my_test(solution, n):
    print('input: n={}, output: {}'.format(n, solution.grayCode(n)))


solution = Solution()
my_test(solution, 1)
my_test(solution, 2)
my_test(solution, 3)

输出结果

input: n=1, output: [0, 1]
input: n=2, output: [0, 1, 3, 2]
input: n=3, output: [0, 1, 3, 2, 6, 7, 5, 4]

4. 结果

image.png