Hard

题目描述

给定一个正整数 n，返回在范围 [0, n] 内其二进制表示不包含连续 1 的整数个数。

示例 1：

输入: n = 5
输出: 5
解释:
以下是 <= 5 的非负整数及其对应的二进制表示：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数 3 违反了规则（有两个连续的 1），其他 5 个都满足规则。

示例 2：

输入: n = 1
输出: 2

示例 3：

输入: n = 2
输出: 3

提示：

  • 1 <= n <= 10^9

解题思路

这是一个数位动态规划问题，核心思想是分析数字的二进制表示特性。

首先观察规律：不含连续1的二进制数本质上遵循斐波那契数列。设 f[i] 表示 i 位二进制数中不含连续1的数字个数，则有递推关系：

  • f[i] = f[i-1] + f[i-2]（第i位为0时接f[i-1]，第i位为1且前一位为0时接f[i-2]）

但直接用斐波那契不能解决"不超过n"的约束，需要用数位DP。

数位DP思路：

  1. 将n转换为二进制字符串，从高位向低位构造
  2. 维护状态：当前位置、是否受上界限制、前一位是否为1
  3. 对每一位，根据约束条件选择填0或1
  4. 如果前一位已经是1，当前位只能填0（避免连续1）

优化方案： 预计算斐波那契数组，然后从高位开始贪心构造。当遇到连续11时，说明超出了限制，此时统计前面所有可能的组合数。

这种方法时间复杂度更优，适合处理大数。

代码实现

class Solution {
public:
    int findIntegers(int n) {
        string s = bitset<32>(n).to_string();
        int len = s.length();
        
        // Find first '1'
        int start = 0;
        while (start < len && s[start] == '0') start++;
        if (start == len) return 1;
        
        // Precompute fibonacci numbers
        vector<int> fib(32, 0);
        fib[0] = 1; fib[1] = 2;
        for (int i = 2; i < 32; i++) {
            fib[i] = fib[i-1] + fib[i-2];
        }
        
        int result = 0;
        bool prevOne = false;
        
        for (int i = start; i < len; i++) {
            if (s[i] == '1') {
                result += fib[len - i - 1];
                if (prevOne) return result;
                prevOne = true;
            } else {
                prevOne = false;
            }
        }
        
        return result + 1;
    }
};

class Solution:
    def findIntegers(self, n: int) -> int:
        s = bin(n)[2:]
        length = len(s)
        
        # Precompute fibonacci numbers
        fib = [0] * 32
        fib[0], fib[1] = 1, 2
        for i in range(2, 32):
            fib[i] = fib[i-1] + fib[i-2]
        
        result = 0
        prev_one = False
        
        for i in range(length):
            if s[i] == '1':
                result += fib[length - i - 1]
                if prev_one:
                    return result
                prev_one = True
            else:
                prev_one = False
        
        return result + 1

public class Solution {
    public int FindIntegers(int n) {
        string s = Convert.ToString(n, 2);
        int length = s.Length;
        
        // Precompute fibonacci numbers
        int[] fib = new int[32];
        fib[0] = 1; fib[1] = 2;
        for (int i = 2; i < 32; i++) {
            fib[i] = fib[i-1] + fib[i-2];
        }
        
        int result = 0;
        bool prevOne = false;
        
        for (int i = 0; i < length; i++) {
            if (s[i] == '1') {
                result += fib[length - i - 1];
                if (prevOne) return result;
                prevOne = true;
            } else {
                prevOne = false;
            }
        }
        
        return result + 1;
    }
}

var findIntegers = function(n) {
    const s = n.toString(2);
    const length = s.length;
    
    // Precompute fibonacci numbers
    const fib = new Array(32).fill(0);
    fib[0] = 1; fib[1] = 2;
    for (let i = 2; i < 32; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }
    
    let result = 0;
    let prevOne = false;
    
    for (let i = 0; i < length; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(log n)
空间复杂度O(1)

相关题目