LeetCode-868. 二进制间距【快慢指针,位运算,十进制转二进制】
2023-09-14 09:01:27 时间
题目描述:
给定一个正整数 n,找到并返回 n 的二进制表示中两个 相邻 1 之间的 最长距离 。如果不存在两个相邻的 1,返回 0 。
如果只有 0 将两个 1 分隔开(可能不存在 0 ),则认为这两个 1 彼此 相邻 。两个 1 之间的距离是它们的二进制表示中位置的绝对差。例如,“1001” 中的两个 1 的距离为 3 。
示例 1:
输入:n = 22
输出:2
解释:22 的二进制是 “10110” 。
在 22 的二进制表示中,有三个 1,组成两对相邻的 1 。
第一对相邻的 1 中,两个 1 之间的距离为 2 。
第二对相邻的 1 中,两个 1 之间的距离为 1 。
答案取两个距离之中最大的,也就是 2 。
示例 2:
输入:n = 8
输出:0
解释:8 的二进制是 “1000” 。
在 8 的二进制表示中没有相邻的两个 1,所以返回 0 。
示例 3:
输入:n = 5
输出:2
解释:5 的二进制是 “101” 。
提示:
1 <= n <= 109
解题思路一:先转化为二进制,然后用快慢指针计算最大间距
class Solution {
public:
int binaryGap(int n) {
string s="0123456789abcdef";
string res= "";
while(n){
res=s[n%2]+res;
n/=2;
}//得到二进制字符串
if(res[0]=='0') return 0;//如果第一位是0,说明n==0,直接返回0
int ans = 0;
for(int left=0,right=0;right<res.size();++right){
if(res[right]=='1'){
ans=max(right-left,ans);
left=right;
}
}
return ans;
}
};
解题思路二:位运算,利用n&1得到n的最低位,用i记录当前1的位置,last记录上一个1的位置。n>>=1表示n右移一位。
class Solution {
public:
int binaryGap(int n) {
int last = -1, ans = 0;
for (int i = 0; n; ++i) {
if (n & 1) {
if (last != -1) {
ans = max(ans, i - last);
}
last = i;
}
n >>= 1;
}
return ans;
}
};
复杂度分析
时间复杂度:O(logn)。循环中的每一步 n 会减少一半,因此需要O(logn) 次循环。
空间复杂度:O(1)。
相关文章
- [LeetCode] Count Primes - 素数系列问题
- Java实现 LeetCode 771 宝石与石头(这是真暴力)
- Java实现 LeetCode 762 二进制表示中质数个计算置位(位运算+JDK的方法)
- Java实现 LeetCode 762 二进制表示中质数个计算置位(位运算+JDK的方法)
- Java实现 LeetCode 728 自除数(暴力)
- Java实现 LeetCode 696 计数二进制子串(暴力)
- Java实现 LeetCode 693 交替位二进制数(位运算)
- Java实现 LeetCode 654 最大二叉树(递归)
- Java实现 LeetCode 643 子数组最大平均数 I(滑动窗口)
- Java实现 LeetCode 621 任务调度器(暴力大法)
- Java实现 LeetCode 479 最大回文数乘积
- Java实现 LeetCode 399 除法求值
- Java实现 LeetCode 377 组合总和 Ⅳ
- Java实现 LeetCode 220 存在重复元素 III(三)
- Java实现 LeetCode 214 最短回文串
- Java实现 LeetCode 179 最大数
- Java实现 LeetCode 83 删除排序链表中的重复元素
- Java实现 LeetCode 67 二进制求和
- Java实现 LeetCode 56 合并区间
- (LeetCode 141/142)Linked List Cycle
- LeetCode(67):二进制求和
- LeetCode(1):两数之和
- 每日一道 LeetCode (43):翻转二进制数
- 每日一道 LeetCode (15):二进制求和
- LeetCode-1758. 生成交替二进制字符串的最少操作数【字符串,三行代码!】
- LeetCode-908. 最小差值 I【max(min)_element,数组,数学】
- LeetCode - 122 买卖股票的最佳时机 II
- Leetcode 11. 盛最多水的容器(终于解决)
- Leetcode 696. 计数二进制子串(有待解决)
- Leetcode 1582. 二进制矩阵中的特殊位置
- leetcode 101. 对称二叉树 js实现
- LeetCode Populating Next Right Pointers in Each Node
- 【LeetCode】718. 最长重复子数组
- 【LeetCode】494. 目标和