AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

LeetCode 868. Binary Gap    原题链接    简单

作者: 作者的头像   wzc1995 ,  2019-01-15 11:51:31 ,  所有人可见 ,  阅读 1021


0


题目描述

给定一个正整数 N,找到并返回 N 的二进制表示中两个连续的 1 之间的最长距离。

如果没有两个连续的 1,返回 0 。

样例

输入:22
输出:2
解释:
22 的二进制是 0b10110。
在 22 的二进制表示中,有三个 1,组成两对连续的 1。
第一对连续的 1 中,两个 1 之间的距离为 2。
第二对连续的 1 中,两个 1 之间的距离为 1。
答案取两个距离之中最大的,也就是 2。
输入:5
输出:2
解释:
5 的二进制是 0b101。
输入:6
输出:1
解释:
6 的二进制是 0b110。
输入:8
输出:0
解释:
8 的二进制是 0b1000。
在 8 的二进制表示中没有连续的 1,所以返回 0。

注意

  • 1 <= N <= 10^9

算法

(模拟) $O(\log n)$
  • 直接将 N 变成二进制表示,如果当前位为 1,且上一个 1 存在,则更新答案即可。

时间复杂度

  • 仅需要将 N 分解为二进制,故时间复杂度为 $O(\log n)$。

空间复杂度

  • 由于可以直接开变量记录上一个 1 的位置,所以只需要常数的空间。

C++ 代码

class Solution {
public:
    int binaryGap(int N) {
        int ans = 0, last = -1, c = 0;
        for (; N; N >>= 1, c++) {
            if (N & 1) {
                if (last != -1)
                    ans = max(ans, c - last);
                last = c;
            }
        }
        return ans;
    }
};

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息