当前位置：首页 > article >正文

LeetCode题练习与总结：不含连续1的非负整数--600

article 2025/2/2 1:13:42

一、题目描述

给定一个正整数 n ，请你统计在 [0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1 。

示例 1:

输入: n = 5
输出: 5
解释: 
下面列出范围在 [0, 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

二、解题思路

这个问题可以通过动态规划（DP）和位操作来解决。以下是解题思路：

动态规划思路：
- 定义 dp[i] 表示长度为 i 的二进制数中，满足条件（没有连续的 1）的数的个数。
- 考虑长度为 i 的二进制数，它的最高位（第 i 位）可以是 0 或 1。
  - 如果最高位是 0，那么剩下的 i-1 位可以任意排列，所以这种情况下的数目等于 dp[i-1]。
  - 如果最高位是 1，那么第二高位（第 i-1 位）必须是 0，剩下的 i-2 位可以任意排列，所以这种情况下的数目等于 dp[i-2]。
- 因此，状态转移方程为：dp[i] = dp[i-1] + dp[i-2]，初始条件为 dp[0] = 1 和 dp[1] = 2。
位操作思路：
- 对于给定的 n，我们需要统计从 0 到 n 中满足条件的数的个数。
- 从最高位开始检查，如果当前位和下一位都是 1，则我们需要跳过所有以这两个 1 开头的数，因为它们不满足条件。

三、具体代码

class Solution {
    public int findIntegers(int n) {
        // 初始化dp数组
        int[] dp = new int[32];
        dp[0] = 1;
        dp[1] = 2;
        
        // 填充dp数组
        for (int i = 2; i < 32; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        
        // 从最高位开始检查
        int ans = 0, prev_bit = 0;
        for (int i = 30; i >= 0; i--) {
            // 如果第i位是1
            if ((n & (1 << i)) != 0) {
                // 累加dp[i]
                ans += dp[i];
                // 如果前一位也是1，则停止循环
                if (prev_bit == 1) {
                    break;
                }
                // 更新prev_bit
                prev_bit = 1;
            } else {
                prev_bit = 0;
            }
        }
        
        // 加上0和n本身
        return ans + 1;
    }
}

这段代码首先使用动态规划计算出所有长度小于等于 31 的二进制数中满足条件的数的个数，然后从最高位开始检查给定的 n，使用位操作来确定需要跳过的数的范围，并累加满足条件的数的个数。最后，返回累加的结果加上 0 和 n 本身。

四、时间复杂度和空间复杂度

1. 时间复杂度

初始化 dp 数组：
- dp 数组的大小是固定的，为 32（因为题目中提到 n 的最大值为 10^9，在二进制表示中最多有 31 位）。
- 初始化 dp[0] 和 dp[1] 的操作是常数时间，即 O(1)。
填充 dp 数组：
- 我们有一个循环，它从 2 运行到 31（包含 31），因此循环的次数是固定的，为 30。
- 每次循环中的操作是常数时间，即 O(1)。
- 因此，填充 dp 数组的总时间复杂度是 O(1)，因为它是固定大小的数组。
检查给定 n 的二进制表示：
- 我们有一个循环，它从 30 运行到 0（包含 0），因此循环的次数是固定的，为 31。
- 每次循环中的操作（包括位操作和累加操作）都是常数时间，即 O(1)。
- 因此，检查 n 的二进制表示的总时间复杂度是 O(1)。

综上所述，整个函数的时间复杂度是 O(1)，因为所有操作都是常数时间的。

2. 空间复杂度

dp 数组：
- dp 数组的大小是固定的，为 32。
- 因此，dp 数组的空间复杂度是 O(1)。
其他变量：
- ans 和 prev_bit 是单个整数变量，它们的空间复杂度是 O(1)。

综上所述，整个函数的空间复杂度是 O(1)，因为所有使用的额外空间都是固定大小的。

五、总结知识点

数组初始化：
- 使用 new int[32] 创建一个固定大小的整型数组 dp，并初始化前两个元素。
动态规划（Dynamic Programming）：
- 使用 dp 数组来存储不同长度的二进制数中满足条件的数的个数。
- 状态转移方程 dp[i] = dp[i-1] + dp[i-2] 用于填充 dp 数组。
位操作：
- 使用位与操作 & 和左移操作 << 来检查数字 n 的特定位是否为 1。
- 例如，(n & (1 << i)) != 0 检查第 i 位是否为 1。
循环与条件判断：
- 使用 for 循环来填充 dp 数组。
- 使用 for 循环从最高位开始检查数字 n 的二进制表示。
- 使用 if 语句来执行条件判断，并根据条件更新变量。
变量更新：
- 使用变量 ans 来累加满足条件的数的个数。
- 使用变量 prev_bit 来记录前一位的状态（是否为 1）。
整型运算：
- 在 dp 数组中执行加法运算来计算满足条件的数的个数。
- 在返回结果时，将 ans 加 1 来包含数字 0 和 n 本身。
递减循环：
- 使用递减的 for 循环从 30 运行到 0，以从最高位开始检查二进制表示。
函数返回值：
- 使用 return 语句返回最终计算的结果。