TNotes.leetcode

Appearance

0693. 交替位二进制数【简单】

0693. 交替位二进制数【简单】 ​

1. 📝 题目描述 ​

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

示例 1：

txt
输入：n = 5
输出：true
解释：5 的二进制表示是：101

示例 2：

txt
输入：n = 7
输出：false
解释：7 的二进制表示是：111.

示例 3：

txt
输入：n = 11
输出：false
解释：11 的二进制表示是：1011.

提示：

  • 1 <= n <= 2^31 - 1

2. 🫧 评价 ​

  • 提交结果：
s.1
s.2

3. 🎯 s.1 - 位运算 ​

js
/**
 * @param {number} n
 * @return {boolean}
 */
var hasAlternatingBits = function (n) {
  let prev = n & 1 // 获取最低位
  n >>= 1 // 右移一位

  while (n > 0) {
    let curr = n & 1 // 获取当前最低位
    if (prev === curr) {
      // 如果相邻两位相同，则不是交替位
      return false
    }
    prev = curr
    n >>= 1
  }

  return true
}
  • 时间复杂度：O(log⁡n)，其中 n 是输入数字，需要检查二进制表示的每一位
  • 空间复杂度：O(1)，只使用了常数个额外变量

4. 🎯 s.2 - 异或 ​

js
/**
 * @param {number} n
 * @return {boolean}
 */
var hasAlternatingBits = function (n) {
  // n 右移一位后与原数异或，如果是交替位，结果应该是全 1
  const xor = n ^ (n >> 1)

  // 检查 xor 是否为全 1（形如 111...111）
  // 全 1 的数字加 1 后会变成 1000...000，与原数按位与结果为 0
  return (xor & (xor + 1)) === 0
}
  • 时间复杂度：O(1)，只需要常数时间的位运算操作
  • 空间复杂度：O(1)，只使用了常数个额外变量

Discussions