Skip to content

Latest commit

 

History

History
107 lines (78 loc) · 2.52 KB

0089._gray_code.md

File metadata and controls

107 lines (78 loc) · 2.52 KB

89. Gray Code

难度: Medium

刷题内容

原题连接

内容描述

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].

解题方案

思路 1 - 时间复杂度: O(2^N)- 空间复杂度: O(2^N)******

几分钟找到了规律，然后实现，AC了。

规律就是n从1开始，每次的结果都是三部分的叠加，part1就是n-1返回的值f(n-1)，part2就是f(n-1)的前半部分每一个元素加上3*pow(2, n-2), part3就是f(n-1)的后半部分每一个元素加上pow(2, n-2)

      3  1  6  6  2  2  12  12  12  12  4   4   4  4     (这一行就是要加上的数字)
0  1  3  2  6  7  5  4  12  13  15  14  10  11  9  8

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n == 0:
            return [0]
        if n == 1:
            return [0, 1]
        part1 = self.grayCode(n-1)
        part2 = [i + 3 * pow(2, n-2) for i in part1[:len(part1)//2]]
        part3 = [i + pow(2, n-2) for i in part1[len(part1)//2:]]
        return part1 + part2 + part3

思路 2 - 时间复杂度: O(2^N)- 空间复杂度: O(2^N)******

AC了以后好自豪哦，看了下 discuss，然后居然有这个东西，我一口老血，我宛若一个智障

The main problem is we need to convert binary code B to Gray code G.
For the i th bit of binary code:
if i==0: G[i]=B[i]
else: G[i] = B[i] XOR B[i-1]

The above part can be simply expressed by G = B^(B>>1).

https://en.wikipedia.org/wiki/Gray_code

服气，这个待研究

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        res = [(i>>1)^i for i in range(pow(2,n))]
        return res