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

一、题目描述

给定一个正整数 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位是1if ((n & (1 << i)) != 0) {// 累加dp[i]ans += dp[i];// 如果前一位也是1，则停止循环if (prev_bit == 1) {break;}// 更新prev_bitprev_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 语句返回最终计算的结果。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。