最近,打算花点时间写个 Python 解决 Leetcode 题的系列文章~
大家是否还记得电影黑客帝国中的数字雨林的场景?事实上,计算机底层数据的存储和运算都是二进制的,因而面试题环节中面试官也经常会问到二进制相关问题。
比较典型的一个问题是 Leetcode 上第 89 号问题,
Leetcode 89. Gray Code
在线提交地址: https://leetcode-cn.com/problems/gray-code/
题目描述
格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差异。
给定一个代表编码总位数的非负整数 n,打印格雷码序列。格雷码序列必须以 0 开头。
例如,给定 n = 2,返回 [0,1,3,2]。其格雷编码是:
1
2
3
4
00 - 0
01 - 1
11 - 3
10 - 2
说明:
对于给定的 n,其格雷编码的顺序并不唯一(因此返回结果的顺序不重要,可使用 Vector 或 List )。
例如 [0,2,3,1] 也是一个有效的格雷编码顺序。
解题思路:
格雷码有个相应的数学公式,整数 i 的格雷码是 i^(i/2) 。而此题并没要求返回结果中的值的严格顺序。
于是只需遍历从 0 到 2^n - 1 的所有整数 i,使用公式将其转换为格雷码,添加到 List 中即可。
已AC代码(Python 3):
1
2
3
4
5
6
class Solution:
def grayCode(self, n: int) -> List[int]:
res = []
for i in range(1 << n):
res.append((i >> 1) ^ i)
return res
如果需要在本地测试,需要先在代码开头引入from typing import List
,然后实例化 Solution
,最后调用相应的 method 即可。完整代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
from typing import List
class Solution:
def grayCode(self, n: int) -> List[int]:
res = []
for i in range(1 << n):
res.append((i >> 1) ^ i)
return res
# 以下是测试代码
obj = Solution()
print(obj.grayCode(2))
运行结果:
执行用时: 48 ms
, 在所有 Python3 提交中击败了87.40%
的用户。
示例代码: https://github.com/JustDoPython/leetcode-python/tree/master/leetcode-089
参考:
[LeetCode] Gray Code - 穆穆兔兔 - 博客园 https://www.cnblogs.com/diegodu/p/4371807.html
版权声明
- 本文作者:极客玩家大白
- 本文链接:https://geekplayers.com/python-leetcode89-gary-code.html
- 郑重声明:本文为博主原创或经授权转载的文章,欢迎转载,但转载文章之后必须在文章页面明显位置注明出处,否则保留追究法律责任的权利。如您有任何疑问或者授权方面的协商,请留言。