跳转至

3950. 恰好一对连续置位

题目描述

给你一个整数 n 。

如果其二进制表示中 恰好 仅包含 一对 连续的置位 ，则返回 true ，否则返回 false 。

整数中的 置位 是指其 二进制 表示中的 1 。

 

示例 1：

输入： nums = 6

输出： true

解释：

  • 6 的二进制表示为 110 。
  • 恰好存在一对连续的置位（"11"）。因此，答案为 true 。

示例 2：

输入： nums = 5

输出： false

解释：

  • 5 的二进制表示为 101 。
  • 不存在连续的置位。因此，答案为 false 。

 

提示：

  • 0 <= n <= 105

解法

方法一：模拟

我们用一个变量 \(\textit{pre}\) 记录上一个位的数字，初始时 \(\textit{pre} = 0\)，用另一个变量 \(\textit{vis}\) 记录是否已经找到一对连续置位，初始时 \(\textit{vis} = \text{false}\)。

遍历 \(n\) 的每个二进制位，记当前二进制位为 \(\textit{cur}\)。如果 \(\textit{pre} = \textit{cur} = 1\)，此时如果 \(\textit{vis} = \text{true}\)，说明存在多对连续置位，直接返回 \(\text{false}\)，否则我们将 \(\textit{vis}\) 置为 \(\text{true}\)。然后我们更新 \(\textit{pre} = \textit{cur}\)，继续遍历下个二进制位。

遍历结束后，如果 \(\textit{vis} = \text{true}\)，返回 \(\text{true}\)，否则返回 \(\text{false}\)。

时间复杂度 \(O(\log n)\)，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def consecutiveSetBits(self, n: int) -> bool:
        pre = 0
        vis = False
        while n:
            cur = n & 1
            if pre == cur == 1:
                if vis:
                    return False
                vis = True
            pre = cur
            n = n >> 1
        return vis

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public boolean consecutiveSetBits(int n) {
        boolean vis = false;
        for (int pre = 0; n > 0; n >>= 1) {
            int cur = n & 1;
            if (pre == cur && cur == 1) {
                if (vis) {
                    return false;
                }
                vis = true;
            }
            pre = cur;
        }
        return vis;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool consecutiveSetBits(int n) {
        bool vis = false;
        for (int pre = 0; n > 0; n >>= 1) {
            int cur = n & 1;
            if (pre == cur && cur == 1) {
                if (vis) {
                    return false;
                }
                vis = true;
            }
            pre = cur;
        }
        return vis;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func consecutiveSetBits(n int) bool {
    vis := false
    for pre := 0; n > 0; n >>= 1 {
        cur := n & 1
        if pre == cur && cur == 1 {
            if vis {
                return false
            }
            vis = true
        }
        pre = cur
    }
    return vis
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function consecutiveSetBits(n: number): boolean {
    let vis = false;
    for (let pre = 0; n > 0; n >>= 1) {
        const cur = n & 1;
        if (pre === cur && cur === 1) {
            if (vis) {
                return false;
            }
            vis = true;
        }
        pre = cur;
    }
    return vis;
}

评论