【LeetCode每日一题】2024年8月第二周（上）

2024.8.5 困难

链接：600. 不含连续1的非负整数

（1）题目描述：

（2）示例

（3）分析

思路1：

题目要求的数值，是将数二进制转换后，不存在连续的1，那么我们初步分析：每一个数的最高位，由下一位来决定。第二位为0时：下一位可为0、1；而第二位为1时：下一位只为0。

于是直接进行转换，按照n转换为2进制的位数后的长度，进行递归拼接即可。最后统计，只要转换后的数字，小于等于n就行。

这种方法，虽然可行，但在10^9数据量面前，显然不够看的，运行n=10^9时，耗时5s。

思路2：

因为实际上控制大小的是n转换为2进制后的长度，我们去观察，不同长度下，它的最大结果。（即当前长度下，所包含的个数）

① 我们惊人的发现，他们的结果满足类似斐波那契数列的特点，因此我们完全可以写写出长度和个数的方程：dp[i] = dp[i - 1] + dp[i - 2]; （dp用于存储个数，i为n二进制长度）

② 而进一步发现，我们可以得到：只要当前i位(从0开始)为1，那么结果中就一定包含：dp[i]个值：

怎么理解？

1）我们将dp结果看作是：i位1的数总和，比如符合题目可存在的最大数 101010（含自身）-- 6位和1000000(不含自身) 皆对应 d[6]=d[5]+d[4] ==》d4=d3+d2 d2=d1+d0 =d1+1

2）而实际上d[6]，同时满足：d[6]=d[5]+d[3]+d[2]=d[5]+d[3]+d[1]+1 ，很显然，这是和101010的1所在位数对应的，

3）那么对101001 6位：拆分为：100000 + 001000+ 000001 首先包含5位情况下的所有个数，再比对1000，再比对1==》100000:dp[5] 001000:dp[3] 000001:dp[0]

于是乎，我们得到：可以直接由当前n的二进制转换，得到最终的结果！

（4）代码

我把两种都写上：

//思路2：
class Solution {// 动态规划的方法计算不含连续 1 的二进制数的数量public static int findIntegers(int n) {int[] dp = new int[32];//32位，最大n在此范围内dp[0] = 1;//初始化数据dp[1] = 2;// 预处理 dp 数组for (int i = 2; i < 32; i++) {dp[i] = dp[i - 1] + dp[i - 2]; //结果满足类似斐波那契数列的形式}int temp = 0;//检测最终值是否为2个1的情况int result = 0;//由上文遍历的思路，如此可以确定，只要当前i位为1，那么结果中就一定包含：dp[i]个前一位的东西// 怎么理解：//将dp结果看作是：i位1的数总和，比如可存在的最大数 101010（含自身） 6位 和1000000(不含自身) 皆对应d[6]=d[5]+d[4] ==》d4=d3+d2 d2=d1+d0 =d1+1// 而实际上d[6]，同时满足：d[6]=d[5]+d[3]+d[2]=d[5]+d[3]+d[1]+1 ，很显然，这是和101010的1所在位数对应的，// 那么对101001 6位：拆分为：100000 + 001000+ 000001 首先包含5位情况下的所有个数，再比对1000，再比对1==》// 100000:dp[5] 001000:dp[3] 000001:dp[0]// 遍历 n 的二进制表示for (int i = 31; i >= 0; i--) {if ((n & (1 << i)) != 0) {  // 当前位是 1按照上文输出// 实际上类如：11000 和10101相互等价皆为d[4]+d[3]，所以不用else了……result += dp[i];if (temp == 1) {  // 检测到连续的两个 1return result;}temp = 1;} else {temp = 0;}}return result + 1;  // 包含 n 本身}// 测试public static void main(String[] args) {long start = System.currentTimeMillis();int sum = findIntegers(1000000000);System.out.println(sum);System.out.println("time: " + (System.currentTimeMillis() - start) + "ms");}
}

//思路1：
class Solution1 {//遍历，直接超时！//思路：没有连续的1，那么每一个数的最高位：由下一位来决定。第二位为0时：可为0、1；1时：只为0.//统计时，只要大小小于就行。public static int findIntegers(int n) {int sum = 0;int len = Integer.toBinaryString(n).length();//Integer.toBinaryString：2进制转换List<String> str = Arrays.asList("0", "1");//赋初值if (n < 2) return n + 1;else {for (int i = 0; i < len; i++) {str = getS(str);}List<String> re = str.stream().sorted().filter(s -> n >= Integer.valueOf(s, 2)).collect(Collectors.toList()); sum = re.size();}return sum;}public static List<String> getS(List<String> str) {List<String> stringList = new ArrayList<>();str.stream().forEach(s -> {if (s.charAt(0) == '0') {stringList.add("0" + s);stringList.add("1" + s);} else {stringList.add("0" + s);}});return stringList;}public static void main(String[] args) {long start = System.currentTimeMillis();int sum = findIntegers(100000000);System.out.println(sum);System.out.println("time: " + (System.currentTimeMillis() - start) + "ms");}
}

（5）碎碎念

题目越短，事儿越大……一个题看了挺久的

2024.8.06 中等

链接：3129. 找出所有稳定的二进制数组 I

（1）题目描述：

（2）示例

（3）分析

题目中，limit限制着0或1的最大连续出现次数（最大为limit），我们按照顺序放0、1时，最后一位0/1是由：前一位没达到limit限制0、1添加0/1而来，转换为可以计算的，便是：不受限制（即所有）的0、1，减去不符合要求的（出现次数大于limit的。）

于是我们捋清楚了思路，而超过限制的明显由0或1组成，因此我们分类来讨论：

① 0结尾的：sum0 = 放0前以0/1结尾的总和 - 前面放了limit+1个0，以1结尾的

② 1结尾的：sum1 = 放1前以0/1结尾的总和 - 前面放了limit+1个1，以0结尾的

最后结果，sum1 + sum0

而此皆存在一个前提，当前放入的0/1总数，大于limit，如此才可能有重合。因此需要来表示当前存入的0/1数量==》

于是乎，大致思路有了，整体运用动态规划，设置i用于表示当前存入0的数量，j表示存入1的数量。再次观看案例，考虑到可能存在只放入同一个值（同时不超过limit和个数），其结果只有一种情况，由此可以设定初始值。

贴一张官方图：

（4）代码

class Solution {public int numberOfStableArrays(int zero, int one, int limit) {final long MOD = 1000000007;long[][][] dp = new long[zero + 1][one + 1][2];for (int i = 0; i <= Math.min(zero, limit); i++) {// 初始化，设置最基础的可能性，只填充同一个值时，只有一种情况。赋值1；dp[i][0][0] = 1;}for (int i = 0; i <= Math.min(one, limit); i++) {dp[0][i][1] = 1;}for (int i = 1; i <= zero; i++) {for (int j = 1; j <= one; j++) {if (i > limit) {dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1] - dp[i - limit - 1][j][1];} else {dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];}// dp[i][j][0]%= MOD;不这样写是因为，数据量大了后，会溢出，对应的数据变成负数了……dp[i][j][0] = (dp[i][j][0] % MOD + MOD) % MOD;// 数据回正if (j > limit) {dp[i][j][1] = dp[i][j - 1][0] + dp[i][j - 1][1] - dp[i][j - limit - 1][0];} else {dp[i][j][1] = dp[i][j - 1][0] + dp[i][j - 1][1];}dp[i][j][1] = (dp[i][j][1] % MOD + MOD) % MOD;}}return (int) ((dp[zero][one][0] + dp[zero][one][1]) % MOD);}
}

（5）碎碎念

你管这叫中等题？一开始我想的是用组合和乘法原理的思想，希望得到一个通解公式，类似那种伯努利装错信的思想，后来发现得不到有效的思路……还是太菜了。然后看了题解的提示，才有的思路。

2024.8.07 困难

链接：3130. 找出所有稳定的二进制数组 II

（1）题目描述：

（2）示例

（3）分析

这题目，实际上就是上面的，只不过数据量变大了，但是咱们的思路是完全正确的，而且取模后数据也不会超，直接试一试就行。Ctrl c v。

这里放一个灵神的解析，采用：容斥原理+乘法原理，我一开始的思想就类似这个，但没求出来，看到解析发现本来思路的可行性，灵神nb！

灵茶山艾府解析 - 力扣（LeetCode）

（4）代码

. - 力扣（LeetCode）贴个代码。

class Solution {private static final int MOD = 1_000_000_007;private static final int MX = 1001;private static final long[] F = new long[MX]; // f[i] = i!private static final long[] INV_F = new long[MX]; // inv_f[i] = i!^-1static {F[0] = 1;for (int i = 1; i < MX; i++) {F[i] = F[i - 1] * i % MOD;}INV_F[MX - 1] = pow(F[MX - 1], MOD - 2);for (int i = MX - 1; i > 0; i--) {INV_F[i - 1] = INV_F[i] * i % MOD;}}public int numberOfStableArrays(int zero, int one, int limit) {if (zero > one) {// swap，保证空间复杂度为 O(min(zero, one))int t = zero;zero = one;one = t;}long[] f0 = new long[zero + 3];for (int i = (zero - 1) / limit + 1; i <= zero; i++) {f0[i] = comb(zero - 1, i - 1);for (int j = 1; j <= (zero - i) / limit; j++) {f0[i] = (f0[i] + (1 - j % 2 * 2) * comb(i, j) * comb(zero - j * limit - 1, i - 1)) % MOD;}}long ans = 0;for (int i = (one - 1) / limit + 1; i <= Math.min(one, zero + 1); i++) {long f1 = comb(one - 1, i - 1);for (int j = 1; j <= (one - i) / limit; j++) {f1 = (f1 + (1 - j % 2 * 2) * comb(i, j) * comb(one - j * limit - 1, i - 1)) % MOD;}ans = (ans + (f0[i - 1] + f0[i] * 2 + f0[i + 1]) * f1) % MOD;}return (int) ((ans + MOD) % MOD); // 保证结果非负}private long comb(int n, int m) {return F[n] * INV_F[m] % MOD * INV_F[n - m] % MOD;}private static long pow(long x, int n) {long res = 1;for (; n > 0; n /= 2) {if (n % 2 > 0) {res = res * x % MOD;}x = x * x % MOD;}return res;}
}//作者：灵茶山艾府
//链接：https://leetcode.cn/problems/find-all-possible-stable-binary-arrays-ii/solutions/2758868/dong-tai-gui-hua-cong-ji-yi-hua-sou-suo-37jdi/
//来源：力扣（LeetCode）
//著作权归作者所有。非商业转载。