第423场周赛：检测相邻递增子数组 Ⅰ、检测相邻递增子数组 Ⅱ、好子序列的元素之和、统计小于 N 的 K 可约简整数

Q1、检测相邻递增子数组 Ⅰ

1、题目描述

给你一个由 n 个整数组成的数组 nums 和一个整数 k，请你确定是否存在 两个 相邻 且长度为 k 的 严格递增 子数组。具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：

• 这两个子数组 nums[a..a + k - 1] 和 nums[b..b + k - 1] 都是 严格递增 的。
• 这两个子数组必须是 相邻的，即 b = a + k。

如果可以找到这样的 两个 子数组，请返回 true；否则返回 false。

子数组 是数组中的一个连续 非空 的元素序列。

2、解题思路

要解决这个问题，我们需要检查数组 nums 中是否存在两个相邻的严格递增子数组，且每个子数组的长度为 k。因此，可以将问题分解为以下步骤：

1. 检查递增子数组：我们先遍历 nums，找出从每个索引 i 开始的长度为 k 的子数组是否为严格递增。
2. 相邻递增子数组检查：如果在遍历过程中找到了满足条件的相邻严格递增子数组，则返回 true。如果遍历结束没有找到，返回 false。

3、解题过程

1. 从数组的每个索引 i 开始，检查 nums[i..i+k-1] 是否严格递增。
2. 如果 nums[i..i+k-1] 和 nums[i+k..i+2*k-1] 都是严格递增的，且满足两个子数组是相邻的，则返回 true。
3. 如果遍历完毕没有找到满足条件的子数组，则返回 false。

4、代码实现

class Solution {
public:bool hasIncreasingSubarrays(vector<int>& nums, int k) {int n = nums.size();// 边界情况检查if (n < 2 * k) {return false;}// 遍历数组, 检查相邻的递增子数组for (int i = 0; i <= n - 2 * k; ++i) {bool Increasing = true;// 检查第一个长度为 k 的子数组是否严格递增for (int j = i; j < i + k - 1; ++j) {if (nums[j] >= nums[j + 1]) {Increasing = false;break;}}// 剪枝if (!Increasing) {continue;}// 检查第二个长度为 k 的子数组是否严格递增for (int j = i + k; j < i + 2 * k - 1; ++j) {if (nums[j] >= nums[j + 1]) {Increasing = false;break;}}// 如果相邻的两个子数组都是严格递增的, 则返回 trueif (Increasing) {return true;}}// 遍历完后任未找到符合条件的子数组, 返回 falsereturn false;}
};

Q2、检测相邻递增子数组 Ⅱ

1、题目描述

给你一个由 n 个整数组成的数组 nums ，请你找出 k 的 最大值，使得存在 两个 相邻 且长度为 k 的 严格递增

子数组。具体来说，需要检查是否存在从下标 a 和 b (a < b) 开始的 两个 子数组，并满足下述全部条件：

• 这两个子数组 nums[a..a + k - 1] 和 nums[b..b + k - 1] 都是 严格递增 的。
• 这两个子数组必须是 相邻的，即 b = a + k。

返回 k 的 最大可能 值。

子数组 是数组中的一个连续 非空 的元素序列。

2、解题思路

在给定问题中，我们的目标是寻找两个相邻且严格递增的子数组，并且最大化长度 𝑘。当前的超时可能由于在每个候选长度 k 上都逐一检查数组所致。为此，我们可以对每个元素的递增情况进行一次遍历，预处理连续的递增段信息，然后利用这些信息来快速验证长度为 k 的相邻递增子数组是否存在。

1. 递增段预处理：

   • 预先处理 nums 中每个位置 i 的最长递增序列长度 increasing_lengths[i]，表示从位置 i 开始的最长递增序列的长度。

   • 通过一次遍历即可获取此信息。

2. 二分查找确定最大 𝑘 ：

   • 使用二分查找寻找最大的 k 值。对于每个候选长度 k，快速判断是否存在相邻且严格递增的子数组。
   • 在判断过程中，利用 increasing_lengths 数组来验证：如果位置 i 的递增序列长度 increasing_lengths[i] ≥ k 且位置 i + k 的递增序列长度 increasing_lengths[i + k] ≥ k，则位置 i 和 i + k 可以构成所需的相邻递增子数组。

3、代码实现

class Solution {
public:int maxIncreasingSubarrays(vector<int>& nums) {int n = nums.size();// 预处理递增长度vector<int> increasing_lengths(n, 1);for (int i = n - 2; i >= 0; --i) {if (nums[i] < nums[i + 1]) {increasing_lengths[i] = increasing_lengths[i + 1] + 1;}}// 二分查找确定最大 k 值int low = 1, high = n / 2;int maxK = 0;while (low <= high) {int mid = low + (high - low) / 2;bool found = false;// 检查是否存在两个长度为 mid 的相邻递增子数组for (int i = 0; i + 2 * mid - 1 < n; ++i) {if (increasing_lengths[i] >= mid && increasing_lengths[i + mid] >= mid) {found = true;break;}}if (found) {maxK = mid;low = mid + 1;} else {high = mid - 1;}}return maxK;}
};

4、复杂度分析

• 时间复杂度: 预处理 increasing_lengths 数组的复杂度为 O(n)。二分查找过程的复杂度为 O(logn)，对于每个候选长度 k，只需 O(n) 的时间验证是否存在符合条件的相邻子数组。因此总复杂度为 O(nlogn)。

• 空间复杂度: O(n)，用于存储 increasing_lengths 数组。

Q3、好子序列的元素之和

1、题目描述

给你一个整数数组 nums。好子序列 的定义是：子序列中任意 两个 连续元素的绝对差 恰好 为 1。

子序列 是指可以通过删除某个数组的部分元素（或不删除）得到的数组，并且不改变剩余元素的顺序。

返回 nums 中所有 可能存在的 好子序列的 元素之和。

因为答案可能非常大，返回结果需要对 109 + 7 取余。

注意，长度为 1 的子序列默认为好子序列。

2、解题思路

1. 子问题拆解

我们要处理的是所有满足条件的子序列，并求它们元素的总和。
这涉及：

• 统计每个元素能够生成多少种好子序列。
• 计算这些子序列的和。

2. 动态规划

设：

• cnt[x] 表示以元素 x 结尾的好子序列的个数。
• f[x] 表示以元素 x 结尾的所有好子序列的元素总和。

3. 转移公式

1. 遍历数组中的每个元素 x：

   • 对于每个 x，好子序列可以从以下几种情况构成：

     1. 独立的好子序列：长度为 1，计数为 1，元素和为 x。
     2. 连接到 x-1 的好子序列：可以接在所有以 x-1 结尾的好子序列后。
     3. 连接到 x+1 的好子序列：可以接在所有以 x+1 结尾的好子序列后。

   • 更新公式：

     ​ $cnt[x]=cnt[x-1]+cnt[x+1]+1$

     ​ $f[x]=f[x-1]+f[x+1]+x\times cnt[x]$

2. 遍历完成后，所有好子序列的总和为 $\text{sum}(f[x])$。

4. 使用哈希表

由于元素可能不是连续的，我们使用哈希表 f 和 cnt 记录每个元素对应的状态，避免无意义的内存浪费。

3、代码实现

class Solution {
public:int sumOfGoodSubsequences(vector<int>& nums) {// 定义模数const int MOD = 1'000'000'007;// 定义哈希表: f 用于记录元素和, cnt 用于记录以某元素为结尾的子序列个数unordered_map<int, int> f, cnt;// 遍历数组for (int x : nums) {// c 是当前元素 x 能够构成的好子序列个数long long c = (cnt[x - 1] + cnt[x + 1] + 1) % MOD;// 更新以 x 结尾的子序列的总和 f[x]f[x] = (x * c + f[x] + f[x - 1] + f[x + 1]) % MOD;// 更新以 x 结尾的子序列个数 cnt[x]cnt[x] = (cnt[x] + c) % MOD;}// 最终结果为所有元素的 f 值之和long long ret = 0;for (const auto& [_, s] : f) {ret += s;}return ret % MOD; // 返回结果，取模}
};

4、复杂度分析

时间复杂度

• 遍历数组，每个元素更新状态：
  • 时间复杂度：O(n)，其中 n 是数组长度。

空间复杂度

• 使用哈希表记录 cnt 和 f，存储最多 O(n) 个元素：
  • 空间复杂度：O(n)。

Q4、统计小于 N 的 K 可约简整数

1、题目描述

给你一个 二进制 字符串 s，它表示数字 n 的二进制形式。

同时，另给你一个整数 k。

如果整数 x 可以通过最多 k 次下述操作约简到 1 ，则将整数 x 称为 k-可约简 整数：

• 将 x 替换为其二进制表示中的置位数（即值为 1 的位）。

例如，数字 6 的二进制表示是 "110"。一次操作后，它变为 2（因为 "110" 中有两个置位）。再对 2（二进制为 "10"）进行操作后，它变为 1（因为 "10" 中有一个置位）。

返回小于 n 的正整数中有多少个是 k-可约简 整数。

由于答案可能很大，返回结果需要对 109 + 7 取余。

二进制中的置位是指二进制表示中值为 1 的位。

2、解题思路

1. 二进制分位处理：

   • 每个小于 s 的数字可以看作是一个二进制字符串，类似数位 DP 的思想，我们逐位构造合法的数字。

   • 在构造过程中记录数字的置位数量，并确保这些数字小于 s。

2. 预计算 k-可约简性：

   • 对于每个可能的置位数 ones_count，我们计算数字是否能在 k 次操作内归约到 1。

   • 使用函数 reduction_steps[x] 表示数字 x 需要的操作次数：

     • reduction_steps[x] = reduction_steps[popcount(x)] + 1，其中 popcount(x) 表示 x 的置位数。

3. 动态规划：

   • 定义 dfs(pos, remaining_ones, is_limit)：

     • pos 表示当前处理的位。
     • remaining_ones 表示需要匹配的置位数量。
     • is_limit 表示当前是否受限于数字 s。

   • 每次枚举当前位是否为 1，并递归处理剩余的位。

4. 合并结果：

   • 遍历所有可能的 ones_count，检查 reduction_steps[ones_count] 是否小于等于 k。

   • 如果满足条件，使用 dfs 统计符合条件的数字个数并累加。

3、代码实现

class Solution {
public:int countKReducibleNumbers(string s, int k) {const int MOD = 1'000'000'007;int n = s.length();// 用于记忆化搜索, memo[i][remaining_ones] 表示从第 i 位开始, 剩余 remaining_ones 个置位的合法二进制字符串数目vector<vector<int>> memo(n, vector<int>(n, -1));// 深度优先搜索函数, 返回满足条件的数字个数auto dfs = [&](auto& self, int pos, int remaining_ones, bool is_limit) -> int {// 如果已经处理完所有位, 检查剩余置位是否为 0if (pos == n) {return !is_limit && remaining_ones == 0;}// 如果未受限且已经计算过当前状态, 直接返回记忆化结果if (!is_limit && memo[pos][remaining_ones] != -1) {return memo[pos][remaining_ones];}// 当前位的最大值int upper_bound = is_limit ? s[pos] - '0' : 1;int result = 0;// 枚举当前位可能取的值for (int digit = 0; digit <= min(upper_bound, remaining_ones); digit++) {result = (result + self(self, pos + 1, remaining_ones - digit, is_limit && digit == upper_bound)) % MOD;}// 如果未受限, 则记录当前结果if (!is_limit) {memo[pos][remaining_ones] = result;}return result;};long long total_count = 0;// 预计算每个数字需要多少次操作可以归约到 1vector<int> reduction_steps(n);for (int i = 1; i < n; i++) {reduction_steps[i] = reduction_steps[__builtin_popcount(i)] + 1;}// 遍历所有可能的置位数, 计算合法的数字个数for (int ones_count = 1; ones_count < n; ones_count++) {if (reduction_steps[ones_count] <= k) {// 计算二进制中恰好有 ones_count 个 1 的合法数字个数total_count += dfs(dfs, 0, ones_count, true);total_count %= MOD;}}return total_count;}
};

4、复杂度分析

时间复杂度：

• 预计算 reduction_steps 复杂度为 $O(n^2)$（由于需要对所有可能的数字计算置位数）。
• 每次 dfs 的复杂度为 $O(n^2)$，共进行 $O(n)$ 次，整体为 $O(n^3)$。

空间复杂度：

• 记忆化数组 memo 占用 $O(n^2)$ 空间。