头脑风暴:翻转数位
站长
· 阅读数 20
题目
给定一个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): 只使用了几个变量
我是杰少,如果您觉的我写的不错,那请给我 点赞+评论+收藏 后再走哦!
往期文章:
请你喝杯 ☕️ 点赞 + 关注哦~
最后,创作不易,如果对大家有所帮助,希望大家点赞支持,有什么问题也可以在评论区里讨论😄~**
本文同步发表于我的微信公众号,扫一扫文章底部的二维码或在微信搜索 HelloWorld杰少 即可关注。