Leetcode面试系列 第1天：Leetcode 89 - 格雷码

最近，打算花点时间写个 Python 解决 Leetcode 题的系列文章~

大家是否还记得电影黑客帝国中的数字雨林的场景？事实上，计算机底层数据的存储和运算都是二进制的，因而面试题环节中面试官也经常会问到二进制相关问题。

比较典型的一个问题是 Leetcode 上第 89 号问题，

Leetcode 89. Gray Code

在线提交地址: https://leetcode-cn.com/problems/gray-code/

题目描述

格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。

给定一个代表编码总位数的非负整数 n，打印格雷码序列。格雷码序列必须以 0 开头。

例如，给定 n = 2，返回 [0,1,3,2]。其格雷编码是：

  1. 　00 - 0

  2. 　01 - 1

  3. 　11 - 3

  4. 　10 - 2

说明:

对于给定的 n，其格雷编码的顺序并不唯一(因此返回结果的顺序不重要)。

例如 [0,2,3,1] 也是一个有效的格雷编码顺序。

  • 题目难度: Medium

  • 相关话题: 回溯算法

    https://leetcode-cn.com/tag/backtracking

  • 相似题目: 1比特与2比特字符

    https://leetcode-cn.com/problems/1-bit-and-2-bit-characters

解题思路:

格雷码有个相应的数学公式，整数 i 的格雷码是 i^(i/2) 。而此题并没要求返回结果中的值的严格顺序。

于是只需遍历从 0 到 2^n - 1 的所有整数 i，使用公式将其转换为格雷码，添加到 List 中即可。

已AC代码(Python 3):

  1. class Solution:

  2. def grayCode(self, n: int) -> List[int]:

  3. res = []

  4. for i in range(1 << n):

  5. res.append((i >> 1) ^ i)

  6. return res

如果需要在本地测试，需要

  • 先在代码开头引入 fromtypingimportList，

    因为 LeetCode 中的 Python 3 使用了 Python 中的静态类型检查语法，故需从包 mypy中引入相关内容。

  • 然后实例化 Solution，最后调用相应的 method 即可。

完整代码如下:

  1. from typing import List

  2. class Solution:

  3. def grayCode(self, n: int) -> List[int]:

  4. res = []

  5. for i in range(1 << n):

  6. res.append((i >> 1) ^ i)

  7. return res

  8. # 以下是测试代码

  9. obj = Solution()

  10. print(obj.grayCode(2))

运行结果:

执行用时: 48ms, 在所有 Python3 提交中击败了 87.40%的用户。

参考:

[LeetCode] Gray Code - 穆穆兔兔 - 博客园

https://www.cnblogs.com/diegodu/p/4371807.html

系列文章
赞 (0)

相关推荐