力扣每日一题2024.8.5

600.不含连续1的非负整数（困难）

给定一个正整数 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⁹

思路：

刚开始便是想到了暴力破解，但是想想这是困难题，看了看数据范围果然不简单。之后只能考虑用数位dp的方法进行解决。具体思路便是:

1. 将输入的整数 n 转换为二进制字符串 binary。
2. 初始化两个数组 a[] 和 b[]，长度为二进制字符串长度 length，并且初始化 a[0] = 1 和 b[0] = 1。
3. 循环处理每一位，根据动态规划的状态转移方程计算 a[] 和 b[] 数组的值：
   • 对于 a[i]，如果当前位是 0，则 a[i] = a[i-1] + b[i-1]。
   • 对于 b[i]，如果当前位是 1，则 b[i] = a[i-1]。
4. 计算最终结果 result = a[length - 1] + b[length - 1]，这是在整个二进制数范围内满足条件的非负整数的个数。
5. 再次遍历二进制字符串，检查是否有连续的1，如果有连续的0（也就是连续的0不符合条件），则通过减去 b[length - i - 1] 的方式来调整最终结果。
6. 返回最终计算得到的结果 result，即在给定范围内满足条件的非负整数的个数。

总体来说，该代码使用动态规划来解决问题，通过预先计算满足条件的非负整数个数并且在遍历二进制字符串时进行调整，最终得到在给定范围内满足条件的非负整数个数。

class Solution {
    public int findIntegers(int n) {
    String binary = Integer.toBinaryString(n); // 将 n 转换为二进制字符串 
    int length = binary.length();
    
    int[] a = new int[length];  // 表示在第 i 位为0时不包含连续1的数量
    int[] b = new int[length];  // 表示在第 i 位为1时不包含连续1的数量
    
    a[0] = 1;
    b[0] = 1;
    
    for (int i = 1; i < length; i++) {
        a[i] = a[i-1] + b[i-1];//计算在第 i 位为0时不包含连续1的数量，根据动态规划的规则，
        //当前位置为0时的数量等于上一位0和上一位1的数量之和。
        b[i] = a[i-1];//计算在第 i 位为1时不包含连续1的数量，当前位置为1时的数量等于上一位0时的数量。
    }
    
    int result = a[length - 1] + b[length - 1];//计算初始结果，即所有位数的情况下的满足条件的整数数量。
    
    for (int i = 1; i < length; i++) {
        if (binary.charAt(i) == '1' && binary.charAt(i - 1) == '1') {//如果当前位和前一位都是1，
        //则存在连续的1，跳出循环。
            break;
        }
        if (binary.charAt(i) == '0' && binary.charAt(i - 1) == '0') {
            result -= b[length - i - 1];
            //如果当前位和前一位都是0，则需要减去在这种情况下的数量，因为这样的情况不满足条件。
        }
    }
    
    return result;    
    }
}