欢迎大家加QQ群：623375442，可以方便群里面交流。昨天双周赛最后一题8分，大晚上实在做不动了。
第一题可以用第二题的思路，我就跳过第一题了。
100469. Find Minimum Time to Reach Last Room I
给你一个由 n 个整数组成的数组 nums ，请你找出 k 的 最大值，使得存在 两个 相邻 且长度为 k 的 严格递增 子数组。具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：
- 这两个子数组 nums[a..a + k - 1] 和 nums[b..b + k - 1] 都是 严格递增 的。
- 这两个子数组必须是 相邻的，即 b = a + k。
返回 k 的 最大可能 值。
子数组 是数组中的一个连续 非空 的元素序列。
测试样例：
输入：nums = [2,5,7,8,9,2,3,4,3,1]
输出：3
解释：
- 从下标 2 开始的子数组是 [7, 8, 9]，它是严格递增的。
- 从下标 5 开始的子数组是 [2, 3, 4]，它也是严格递增的。
- 这两个子数组是相邻的，因此 3 是满足题目条件的 最大 k 值。
解答：我们首先计算当前数组连续严格递增的情况比如[2,5,7,8,9,2,3,4,3,1] -> [1,2,3,4,5,1,2,3,1,1]。即从当前位置往前看看，最长递增长度。这样每个位置的最大可能，就是最长字符串阶段。比如[1,2,3,4] -> [1,2] + [3,4]。或者算上之前那个最长数组。比如[7,8,9,2,3,4] -> [7,8,9] + [1,2,3]
class Solution {
public int maxIncreasingSubarrays(List<Integer> nums) {
int[] mem = new int[nums.size()];
int res = 0;
{
int last = Integer.MAX_VALUE;
int i = 0;
for (int n : nums) {
if (n <= last) {
mem[i] = 1;
} else {
mem[i] = mem[i - 1] + 1;
}
res = Math.max(res, mem[i] / 2);
if (i >= mem[i]) {
res = Math.max(res, Math.min(mem[i], mem[i - mem[i]]));
}
last = n;
++i;
}
}
return res;
}
}100486. Sum of Good Subsequences
给你一个整数数组 nums。好子序列 的定义是：子序列中任意 两个 连续元素的绝对差 恰好 为 1。
子序列 是指可以通过删除某个数组的部分元素（或不删除）得到的数组，并且不改变剩余元素的顺序。
返回 nums 中所有 可能存在的 好子序列的 元素之和。
因为答案可能非常大，返回结果需要对 10^9 + 7 取余。
注意，长度为 1 的子序列默认为好子序列。
测试样例：
输入：nums = [1,2,1]
输出：14
解释：
- 好子序列包括：[1], [2], [1], [1,2], [2,1], [1,2,1]。
- 这些子序列的元素之和为 14。
解答：典型的动态规划。具体逻辑看代码注释。
class Solution {
private static final int mod = 1_000_000_007;
public int sumOfGoodSubsequences(int[] nums) {
HashMap<Integer, long[]> mem = new HashMap<>();
for (int n : nums) {
// 长度为 1 的子序列默认为好子序列。
if (!mem.containsKey(n)) {
mem.put(n, new long[]{n, 1});
} else {
long[] tmp = mem.get(n);
tmp[0] = (tmp[0] + n) % mod;
tmp[1] = (tmp[1] + 1) % mod;
}
long[] cur = mem.get(n);
// 加上n - 1情况
update(cur, mem.getOrDefault(n - 1, null), n);
// 加上n + 1情况
update(cur, mem.getOrDefault(n + 1, null), n);
}
int res = 0;
for (Map.Entry<Integer, long[]> entry : mem.entrySet()) {
res = (int) ((res + entry.getValue()[0]) % mod);
}
return res;
}
private void update(long[] cur, long[] other, int n) {
if (other != null) {
// 次数刷新
cur[1] = (cur[1] + other[1]) % mod;
// 类和刷新，新的类和 = 老的类和 + （之前位置的类和 + 之前位置次数 * 当前数字）
cur[0] = ((cur[0] + other[1] * n) % mod + other[0]) % mod;
}
}
}100473. Count K-Reducible Numbers Less Than N
给你一个 二进制 字符串 s，它表示数字 n 的二进制形式。
同时，另给你一个整数 k。
如果整数 x 可以通过最多 k 次下述操作约简到 1 ，则将整数 x 称为 k-可约简 整数：
- 将 x 替换为其二进制表示中的置位数（即值为 1 的位）。
例如，数字 6 的二进制表示是 "110"。一次操作后，它变为 2（因为 "110" 中有两个置位）。再对 2（二进制为 "10"）进行操作后，它变为 1（因为 "10" 中有一个置位）。
返回小于 n 的正整数中有多少个是 k-可约简 整数。
由于答案可能很大，返回结果需要对 10^9 + 7 取余。
二进制中的置位是指二进制表示中值为 1 的位。
测试样例：
输入：s = "111", k = 1
输出：3
解释：n = 7。小于 7 的 1-可约简整数有 1，2 和 4。
解答：有个重要的提示，1 <= s.length <= 800。所以第一次位数类和不可能大于800，所以第一步记录一下不同类和的情况，k可约的情况和组合情况。然后我们利用这个数组，计算长度小于s的情况下，所有的可能。最后利用数位数组的逻辑，刷新最后结果。
class Solution {
private static final int mod = 1_000_000_007;
private static boolean[][] kFold;
private static int[][] combine;
static {
// 计算不同类和情况下，k可约
kFold = new boolean[801][6];
kFold[1][1] = true;
for (int i = 2; i <= 5; ++i) {
for (int j = 1; j <= 800; ++j) {
int bitSum = 0;
for (int k = 0; k <= 10; ++k) {
bitSum += (j >> k) & 1;
}
kFold[j][i] = kFold[bitSum][i - 1];
}
}
// 计算组合
combine = new int[801][801];
combine[0][0] = 1;
for (int i = 1; i <= 800; ++i) {
for (int j = 0; j <= i; ++j) {
if (j == 0 || j == i) {
combine[i][j] = 1;
} else {
combine[i][j] = (combine[i - 1][j - 1] + combine[i - 1][j]) % mod;
}
}
}
}
public int countKReducibleNumbers(String s, int k) {
if (s.equals("1")) {
return 0;
}
int res = 1;
// 小于s长度的数组
for (int i = 2; i < s.length(); ++i) {
for (int j = 1; j <= i; ++j) {
// 对于长度位i的字符串，有j个1，且k可约的情况下，能够贡献的次数。
if (kFold[j][k]) {
res = (res + combine[i - 1][j - 1]) % mod;
}
}
}
int oneCount = 1, remain = s.length() - 2;
for (int i = 1; i < s.length(); ++i) {
// 数位数组逻辑
if (s.charAt(i) == '1') {
for (int j = 0; j <= remain; ++j) {
if (kFold[oneCount + j][k]) {
res = (res + combine[remain][j]) % mod;
}
}
}
--remain;
oneCount += s.charAt(i) - '0';
}
return res;
}
}