头脑风暴：翻转数位

2022 年 8 月 27 日
江苏
本文字数：539 字
阅读完需：约 2 分钟

题目

给定一个 32 位整数 num，你可以将一个数位从 0 变为 1。请编写一个程序，找出你能够获得的最长的一串 1 的长度。

示例 1：

输入: num = 1775(11011101111)输出: 8

复制代码

示例 2：

输入: num = 7(0111)输出: 4

复制代码

解题思路

根据题目给出的示例分析，我们可以通过右移去判断每一位是否为 "1"，从而去计算最长一串 1 的长度；

通过每次去维护三个变量：

cur：当前位置为止连续 1 的个数，遇到 0 归零，遇到 1 加 1；

insert：在当前位置变成 1，往前数连续 1 的最大个数，遇到 0 变为 cur+1，遇到 1 加 1；

res:保存 insert 的最大值即可；

代码实现

class Solution {    public int reverseBits(int num) {        int cur = 0;        int insert = 0;        int res = 1;        for(int i = 0; i < 32; i++){            if((num & (1 << i)) != 0){                cur += 1;                insert += 1;            }else{                insert = cur + 1;                cur = 0;            }            res = Math.max(res , insert);        }        return res;    }}

复制代码

最后

时间复杂度 O(32): 只需要遍历一遍每一位即可
空间复杂度 O(1): 只使用了几个变量

最后，创作不易，如果对大家有所帮助，希望大家点赞支持，有什么问题也可以在评论区里讨论😄～**

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/a90160bc4e8692e29af2e2428】。文章转载请联系作者。

HelloWorld杰少

关注

佛系编码 2019.05.13 加入

红鲤鱼与绿鲤鱼与驴。

发布

暂无评论

创作场景

头脑风暴：翻转数位

题目

解题思路

代码实现

最后

HelloWorld杰少

评论