jaryue
2023/05/20阅读:10主题:默认主题
leetcode 868. 二进制间距
题目描述
-
二进制间距
给定一个正整数 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
解题思路
法1
位操作+模拟\
将数字右移i位然后与1进行与操作,如果得到结果为1,则证明数字的第i位为1
否则说明第i位为0
这样我们就可以判断第i位的0/1了
用两个变量储存1的位置,再用一个变量储存最大的两个1的位置差
遍历数字取两个1距离最长的进行输出
-
时间复杂度(O(n)) -
空间复杂度(O(1))
执行结果
法1
maxDist和dist变量为0,prevBit变量为-1。maxDist用于记录最大距离,dist用于临时存储两个相邻1之间的距离,prevBit用于记录上一个为1的位的索引。
通过对整数进行右移位操作,我们可以逐个检查每一位是否为1。如果某位为1,则表示找到了一个1。我们可以计算当前位的索引与上一个为1的位的索引之间的距离,并将其与之前记录的最大距离进行比较和更新。
最后,我们返回最大距离作为结果。
func binaryGap(n int) int {
maxDist := 0
dist := 0
prevBit := -1
for i := 0; i < 32; i++ {
if (n>>i)&1 == 1 {
if prevBit != -1 {
dist = i - prevBit
if dist > maxDist {
maxDist = dist
}
}
prevBit = i
}
}
return maxDist
}
执行结果: 通过 显示详情 查看示例代码 添加备注
执行用时: 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗: 1.8 MB , 在所有 Go 提交中击败了 54.55% 的用户 通过测试用例: 261 / 261 炫耀一下:
作者介绍