【LeetCode】868. Binary Gap 解题报告（Python）
2024-09-07 10:03:41
作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
题目地址：https://leetcode.com/problems/binary-gap/description/
题目描述
Given a positive integer N, find and return the longest distance between two consecutive 1’s in the binary representation of N.
If there aren’t two consecutive 1’s, return 0.
Example 1:
Input: 22
Output: 2
Explanation:
22 in binary is 0b10110.
In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
The first consecutive pair of 1's have distance 2.
The second consecutive pair of 1's have distance 1.
The answer is the largest of these two distances, which is 2.
Example 2:
Input: 5
Output: 2
Explanation:
5 in binary is 0b101.
Example 3:
Input: 6
Output: 1
Explanation:
6 in binary is 0b110.
Example 4:
Input: 8
Output: 0
Explanation:
8 in binary is 0b1000.
There aren't any consecutive pairs of 1's in the binary representation of 8, so we return 0.
Note:
- 1 <= N <= 10^9
题目大意
求一个数的二进制中，最远的两个1之间的距离。如果只有一个1，那么返回0.
解题方法
线性扫描
先求二进制，然后统计二进制中每个1离左边1的距离即可。用left保存左边1出现的位置，距离就是当前1的index减去left。然后求这个列表中的最大值即可。
题目给出的N的范围是1 <= N <= 10^9，直接求还是比较合适的。
时间复杂度是O(N)，空间复杂度是O(32).
代码如下：
class Solution(object):
def binaryGap(self, N):
"""
:type N: int
:rtype: int
"""
binary = bin(N)[2:]
dists = [0] * len(binary)
left = 0
for i, b in enumerate(binary):
if b == '1':
dists[i] = i - left
left = i
return max(dists)
可以优化空间复杂度，使用结果进行保存每个位置的最大值就行了。
class Solution:
def binaryGap(self, N):
"""
:type N: int
:rtype: int
"""
nbins = bin(N)[2:]
index = -1
res = 0
for i, b in enumerate(nbins):
if b == "1":
if index != -1:
res = max(res, i - index)
index = i
return res
日期
2018 年 7 月 17 日 —— 连天大雨，这种情况很少见，但是很舒服
2018 年 11 月 8 日 —— 项目进展缓慢
最新文章
- nio
- java反射机制一个例子
- C# 通用上传文件类
- JavaScript_解决safari浏览器window.open无法实现的问题
- asp.net学习资料，mvc学习资料
- BZOJ2492 Revenge of Fibonacci
- boa介绍文档
- JedisPool操作
- Ubuntu_16.04_Lamp
- java中的输入流（Scanner）,数据类型，运算符,switch,数组的用法
- Linux中的shell函数编写
- Extjs 树节点操作常用属性
- LAMP部署
- 基于 HTML5 WebGL 的 3D “弹力”布局
- JAVA NIO学习三：NIO 的非阻塞式网络通信
- Android开发支付集成——微信集成
- android-音量管理
- ubuntu 16.04 的IP地址变更
- MySQL往表里插入千条数据 存储过程
- Go语言执行流程