不含连续1的非负整数
难度:
标签:
题目描述
代码结果
运行时间: 26 ms, 内存: 16.5 MB
/*
* 思路：
* 使用Java Stream可以更简洁地遍历和过滤0到n之间的整数。
* 我们可以使用IntStream来生成范围内的所有整数，并且使用filter方法来过滤掉不符合条件的整数。
*/
import java.util.stream.IntStream;
public class SolutionStream {
public long findIntegers(int n) {
return IntStream.rangeClosed(0, n)
.filter(this::hasNoConsecutiveOnes)
.count();
}
private boolean hasNoConsecutiveOnes(int num) {
int prev_bit = 0;
while (num > 0) {
int current_bit = num & 1;
if (prev_bit == 1 && current_bit == 1) {
return false;
}
prev_bit = current_bit;
num >>= 1;
}
return true;
}
}解释
方法:
题解使用了深度优先搜索（DFS）和动态规划的方法，结合位操作和记忆化来解决问题。核心思路是递归地构建符合条件的整数，同时确保不会超过给定的上限 n。递归函数 dfs(i, isOne, isLimit) 考虑当前正在处理的比特位索引 i，isOne 表示前一个比特位是否是1，isLimit 表示当前位是否受到 n 的限制。如果当前位 i 等于二进制表示的长度，说明已构建完成一个有效的整数，返回1。函数中，up 变量根据 isLimit 决定当前位能取的最大值。当上一位不是1且当前位可取1时，会继续递归探索。使用 @cache 装饰器对递归结果进行缓存，以避免重复计算。
时间复杂度:
O(log n)
空间复杂度:
O(log n)
代码细节讲解
🦆
在递归调用dfs时，参数isLimit和isOne的具体作用是什么？如何影响递归过程中的决策？
▷🦆
为什么在处理每个比特位时，只有当上一个比特位不是1时，我们才考虑将当前比特位设置为1？
▷🦆
在确定变量up的值时，为什么当isLimit为true时，up取值为s[i]，而当isLimit为false时，up恒定为'1'？这种设计的逻辑依据是什么？
▷🦆
在递归函数dfs中，返回值是如何累计的，特别是在处理不同比特位时，如何确保不重复计数符合条件的整数？
▷相关问题
打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2] 输出：3 解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1] 输出：4 解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [1,2,3] 输出：3
提示：
1 <= nums.length <= 1000 <= nums[i] <= 1000
一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例 1：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：
输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
提示：
1 <= strs.length <= 6001 <= strs[i].length <= 100strs[i]仅由'0'和'1'组成1 <= m, n <= 100