Easy

题目描述

给定一个整数 n。

如果一个整数的二进制表示中所有位都相同，则称该整数为单调位整数。

返回范围 [0, n]（含边界）内单调位整数的个数。

示例 1:

输入: n = 1
输出: 2
解释: 
范围 [0, 1] 中的整数有二进制表示 "0" 和 "1"。
每个表示都由相同的位组成。因此答案是 2。

示例 2:

输入: n = 4
输出: 3
解释:
范围 [0, 4] 中的整数包括二进制 "0"、"1"、"10"、"11" 和 "100"。
只有 0、1 和 3 满足单调位条件。因此答案是 3。

约束条件:

  • 0 <= n <= 1000

提示:

  • 遍历范围 [0, n] 中的所有整数并统计单调位整数

解题思路

解题思路

这道题要求统计范围 [0, n] 内的单调位整数。单调位整数指的是二进制表示中所有位都相同的数，即要么全是0，要么全是1。

方法一：直接枚举（推荐）

最直观的方法是遍历 [0, n] 范围内的每个数，检查其二进制表示是否为单调位。对于每个数，我们可以通过位操作来判断：

  • 如果数字是0，直接算作单调位
  • 对于其他数字，检查是否等于 2^k - 1 的形式（即所有位都是1）

方法二：数学方法

我们可以分析单调位数的规律：

  • 0 是单调位数（全0）
  • 1, 3, 7, 15, 31, … 是单调位数（分别是 2^1-1, 2^2-1, 2^3-1, …）

因此我们只需要找出不超过 n 的所有形如 2^k - 1 的数，再加上 0。

这里采用第一种方法，代码简洁易懂，对于约束条件 n ≤ 1000 完全足够。

代码实现

class Solution {
public:
    int countMonobit(int n) {
        int count = 0;
        for (int i = 0; i <= n; i++) {
            if (isMonobit(i)) {
                count++;
            }
        }
        return count;
    }
    
private:
    bool isMonobit(int num) {
        if (num == 0) return true;
        
        // 检查是否为 2^k - 1 的形式（所有位都是1）
        return (num & (num + 1)) == 0;
    }
};

class Solution:
    def countMonobit(self, n: int) -> int:
        count = 0
        for i in range(n + 1):
            if self.is_monobit(i):
                count += 1
        return count
    
    def is_monobit(self, num: int) -> bool:
        if num == 0:
            return True
        
        # 检查是否为 2^k - 1 的形式（所有位都是1）
        return (num & (num + 1)) == 0

public class Solution {
    public int CountMonobit(int n) {
        int count = 0;
        for (int i = 0; i <= n; i++) {
            if (IsMonobit(i)) {
                count++;
            }
        }
        return count;
    }
    
    private bool IsMonobit(int num) {
        if (num == 0) return true;
        
        // 检查是否为 2^k - 1 的形式（所有位都是1）
        return (num & (num + 1)) == 0;
    }
}

var countMonobit = function(n) {
    let count = 0;
    
    for (let i = 0; i <= n; i++) {
        let binary = i.toString(2);
        let firstBit = binary[0];
        let isMonobit = true;
        
        for (let j = 1; j < binary.length; j++) {
            if (binary[j] !== firstBit) {
                isMonobit = false;
                break;
            }
        }
        
        if (isMonobit) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历 [0, n] 范围内的所有数字，每次检查是 O(1)
空间复杂度O(1)只使用了常数级别的额外空间