第439场周赛：找出最大的几近缺失整数、至多 k 次操作后的最长回文子序列、长度至少为 M 的 K 个子数组之和、字典序最小的生成字符串

Q1、找出最大的几近缺失整数

1、题目描述

给你一个整数数组 nums 和一个整数 k 。

如果整数 x 恰好仅出现在 nums 中的一个大小为 k 的子数组中，则认为 x 是 nums 中的几近缺失（almost missing）整数。

返回 nums 中 最大的几近缺失 整数，如果不存在这样的整数，返回 -1 。

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

示例 1：

**输入：**nums = [3,9,2,1,7], k = 3

**输出：**7

解释：

• 1 出现在两个大小为 3 的子数组中：[9, 2, 1]、[2, 1, 7]
• 2 出现在三个大小为 3 的子数组中：[3, 9, 2]、[9, 2, 1]、[2, 1, 7]
• 3 出现在一个大小为 3 的子数组中：[3, 9, 2]
• 7 出现在一个大小为 3 的子数组中：[2, 1, 7]
• 9 出现在两个大小为 3 的子数组中：[3, 9, 2]、[9, 2, 1]

返回 7 ，因为它满足题意的所有整数中最大的那个。

示例 2：

**输入：**nums = [3,9,7,2,1,7], k = 4

**输出：**3

解释：

• 1 出现在两个大小为 3 的子数组中：[9, 7, 2, 1]、[7, 2, 1, 7]
• 2 出现在三个大小为 3 的子数组中：[3, 9, 7, 2]、[9, 7, 2, 1]、[7, 2, 1, 7]
• 3 出现在一个大小为 3 的子数组中：[3, 9, 7, 2]
• 7 出现在三个大小为 3 的子数组中：[3, 9, 7, 2]、[9, 7, 2, 1]、[7, 2, 1, 7]
• 9 出现在两个大小为 3 的子数组中：[3, 9, 7, 2]、[9, 7, 2, 1]

返回 3 ，因为它满足题意的所有整数中最大的那个。

示例 3：

**输入：**nums = [0,0], k = 1

输出：-1

解释：

不存在满足题意的整数。

2、解题思路

问题理解

1. 几近缺失整数：
   • x 必须在 nums 中恰好仅出现在一个大小为 k 的子数组中。
   • 如果 x 出现在多个子数组中，或者出现在大小不等于 k 的子数组中，则不符合条件。
2. 子数组：
   • 子数组是数组中的一个连续元素序列。

解题思路

1. 特殊情况处理：
   • 如果 nums 的长度小于 k，则不可能存在符合条件的整数，直接返回 -1。
   • 如果 nums 的长度等于 k，则整个数组是一个子数组，返回数组中的最大值。
2. 一般情况：
   • 使用哈希表 hash 记录每个整数在的个数。
   • 遍历 nums，检查每个整数是否满足 “几近缺失” 的条件。
   • 如果 k == 1，则直接检查每个整数是否只出现一次。
3. 返回结果：
   • 返回满足条件的最大整数，如果没有则返回 -1。

3、代码实现

C++

class Solution {
public:int largestInteger(vector<int>& nums, int k) {const int n = nums.size();// 特殊情况处理// 如果数组长度小于 k, 返回 -1if (n < k) {return -1;}// 如果数组长度等于 k, 返回数组中的最大值if (n == k) {return *max_element(nums.begin(), nums.end());}// 使用哈希表记录每个整数在 nums 中的位置unordered_map<int, int> hash;for (int i = 0; i < n; ++i) {hash[nums[i]]++;}// 初始化最大几近缺失整数int maxMissing = -1;// 检查单个元素是否满足条件auto checkSingleElement = [&](int num) {if (hash[num] == 1) {maxMissing = max(maxMissing, num);}};// 检查第一个和最后一个元素checkSingleElement(nums[0]);checkSingleElement(nums.back());// 如果 k == 1, 直接检查每个整数是否只出现一次if (k == 1) {for (auto [k, v] : hash) {checkSingleElement(k);}}return maxMissing;}
};

Python

class Solution:def largestInteger(self, nums: List[int], k: int) -> int:n = len(nums)# 特殊情况处理if n < k:return -1if n == k:return max(nums)# 使用哈希表记录每个整数的出现次数hash = defaultdict(int)for num in nums:hash[num] += 1# 初始化最大几近缺失整数max_missing = -1# 检查单个元素是否满足条件def check_single_element(num):if hash[num] == 1:nonlocal max_missingmax_missing = max(max_missing, num)# 检查第一个和最后一个元素check_single_element(nums[0])check_single_element(nums[-1])# 如果 k == 1, 直接检查每个整数是否只出现一次if k == 1:for num in hash:check_single_element(num)return max_missing

4、复杂度分析

• 时间复杂度：
  • 遍历数组：O(n)。
  • 检查单个元素：O(1)。
  • 总时间复杂度：O(n)。
• 空间复杂度：
  • 哈希表 hash：O(n)。

Q2、至多 k 次操作后的最长回文子序列

1、题目描述

给你一个字符串 s 和一个整数 k。

在一次操作中，你可以将任意位置的字符替换为字母表中相邻的字符（字母表是循环的，因此 'z' 的下一个字母是 'a'）。例如，将 'a' 替换为下一个字母结果是 'b'，将 'a' 替换为上一个字母结果是 'z'；同样，将 'z' 替换为下一个字母结果是 'a'，替换为上一个字母结果是 'y'。

返回在进行 最多 k 次操作后，s 的 最长回文子序列 的长度。

子序列 是一个 非空 字符串，可以通过删除原字符串中的某些字符（或不删除任何字符）并保持剩余字符的相对顺序得到。

回文 是正着读和反着读都相同的字符串。

示例 1：

输入: s = “abced”, k = 2

输出: 3

解释:

• 将 s[1] 替换为下一个字母，得到 "acced"。
• 将 s[4] 替换为上一个字母，得到 "accec"。

子序列 "ccc" 形成一个长度为 3 的回文，这是最长的回文子序列。

示例 2：

输入: s = “aaazzz”, k = 4

输出: 6

解释:

• 将 s[0] 替换为上一个字母，得到 "zaazzz"。
• 将 s[4] 替换为下一个字母，得到 "zaazaz"。
• 将 s[3] 替换为下一个字母，得到 "zaaaaz"。

整个字符串形成一个长度为 6 的回文。

2、解题思路

这是一个典型的动态规划问题。我们可以通过以下步骤来解决：

1. 定义状态：
   • 设 dp[i][j][l] 表示在子串 s[i..j] 中进行最多 l 次操作后，最长回文子序列的长度。
2. 状态转移：
   • 如果 s[i] == s[j]，则直接递归处理子问题 dp[i + 1][j - 1][l]，并加上 2。
   • 如果 s[i] != s[j]，则尝试替换 s[i] 或 s[j]，或者不替换并分别删除 s[i] 或 s[j]。
3. 计算替换成本：
   • 使用 minOperations 函数计算将 s[i] 替换为 s[j] 所需的最小操作次数。
4. 边界条件：
   • 如果 i == j，则返回 1。
   • 如果 i > j，则返回 0。

3、代码实现

C++

class Solution {
public:int longestPalindromicSubsequence(string s, int k) {int n = s.size();// dp[i][j][l] 表示在子串 s[i..j] 中进行最多 l 次操作后,// 最长回文子序列的长度vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k + 1, -1)));return helper(s, 0, n - 1, k, dp);}int helper(const string& s, int i, int j, int l, vector<vector<vector<int>>>& dp) {// 如果已经计算过, 直接返回结果if (dp[i][j][l] != -1) {return dp[i][j][l];}// 边界条件if (i == j) {return dp[i][j][l] = 1; // 只有一个字符}if (i > j) {return dp[i][j][l] = 0; // 空字符}// 如果 s[i] == s[j], 直接递归处理子问题if (s[i] == s[j]) {dp[i][j][l] = 2 + helper(s, i + 1, j - 1, l, dp);} else {// 如果 s[i] != s[j], 尝试替换 s[i] 或者 s[j]int cost = minOperations(s[i], s[j]);if (l >= cost) {dp[i][j][l] = 2 + helper(s, i + 1, j - 1, l - cost, dp);}// 不替换, 分别尝试删除 s[i] 或 s[j]dp[i][j][l] = max(dp[i][j][l], max(helper(s, i + 1, j, l, dp), helper(s, i, j - 1, l, dp)));}return dp[i][j][l];}int minOperations(char a, char b) {// 计算将 a 替换成 b 所需的最小操作次数int diff = abs(a - b);return min(diff, 26 - diff);}
};

Python

class Solution:def longestPalindromicSubsequence(self, s: str, k: int) -> int:n = len(s)# 定义 dp 数组dp = [[[-1 for _ in range(k + 1)] for _ in range(n)] for _ in range(n)]return self.helper(s, 0, n - 1, k, dp)def helper(self, s: str, i: int, j: int, l: int, dp: List[List[List[int]]]) -> int:# 如果已经计算过, 直接返回结果if dp[i][j][l] != -1:return dp[i][j][l]# 边界条件if i == j:dp[i][j][l] = 1     # 只有一个字符return dp[i][j][l]if i > j:dp[i][j][l] = 0     # 空字符串return dp[i][j][l]# 如果 s[i] == s[j], 直接递归处理子问题if s[i] == s[j]:dp[i][j][l] = 2 + self.helper(s, i + 1, j - 1, l, dp)else:# 如果 s[i] != s[j]，尝试替换 s[i] 或 s[j]cost = self.minOperations(s[i], s[j])if l >= cost:dp[i][j][l] = 2 + self.helper(s, i + 1, j - 1, l - cost, dp)# 不替换, 分别尝试删除 s[i] 或 s[j]dp[i][j][l] = max(dp[i][j][l], max(self.helper(s, i + 1, j, l, dp), self.helper(s, i, j - 1, l, dp)))return dp[i][j][l]def minOperations(self, a: str, b: str) -> int:# 计算将 a 替换为 b 所需的最小操作次数diff = abs(ord(a) - ord(b))return min(diff, 26 - diff)

4、复杂度分析

• 时间复杂度：
  • 状态数为 O(n^2 * k)，每个状态的计算需要 O(1) 的时间。
  • 总时间复杂度：O(n^2 * k)。
• 空间复杂度：
  • dp 数组的空间复杂度为 O(n^2 * k)。

Q3、长度至少为 M 的 K 个子数组之和

1、题目描述

给你一个整数数组 nums 和两个整数 k 和 m。

返回数组 nums 中 k 个不重叠子数组的 最大 和，其中每个子数组的长度 至少 为 m。

子数组 是数组中的一个连续序列。

示例 1：

输入: nums = [1,2,-1,3,3,4], k = 2, m = 2

输出: 13

解释:

最优的选择是:

• 子数组 nums[3..5] 的和为 3 + 3 + 4 = 10（长度为 3 >= m）。
• 子数组 nums[0..1] 的和为 1 + 2 = 3（长度为 2 >= m）。

总和为 10 + 3 = 13。

示例 2：

输入: nums = [-10,3,-1,-2], k = 4, m = 1

输出: -10

解释:

最优的选择是将每个元素作为一个子数组。输出为 (-10) + 3 + (-1) + (-2) = -10。

2、解题思路

这是一个典型的动态规划问题。我们可以通过以下步骤来解决：

1. 前缀和预处理：
   • 使用前缀和数组 s 来快速计算任意子数组的和。
2. 动态规划定义：
   • 设 f[i][j] 表示在前 j 个元素中，选取 i 个不重叠子数组的最大和，每个子数组的长度至少为 m。
3. 状态转移：
   • 对于每个 i 和 j，我们需要找到所有可能的 L，使得 L 到 j 之间的子数组长度至少为 m，并且 L 之前的子数组已经选取了 i - 1 个。
   • 使用 mx 来记录 f[i - 1][L] - s[L] 的最大值，从而快速计算 f[i][j]。
4. 优化空间复杂度：
   • 使用滚动数组 f 和 nf 来减少空间复杂度。

3、代码实现

C++

class Solution {
public:int maxSum(vector<int>& nums, int k, int m) {int n = nums.size();// 前缀和数组vector<int> s(n + 1);partial_sum(nums.begin(), nums.end(), s.begin() + 1);// f[j] 表示前 j 个元素中选取 i 个子数组的最大和vector<int> f(n + 1);// 遍历子数组数量for (int i = 1; i <= k; i++) {// 新的 f 数组vector<int> nf(n + 1, INT_MIN / 2);// 记录最大的 f[L] - s[L]int mx = INT_MIN / 2;// 遍历 j, 确保左右两边有足够空间给其他子数组for (int j = i * m; j <= n - (k - i) * m; j++) {// 更新 mxmx = max(mx, f[j - m] - s[j - m]);// 更新 nf[j]nf[j] = max(nf[j - 1], mx + s[j]); // 不选 vs 选}f = move(nf); // 更新 f 数组}return f[n]; // 返回最终结果}
};

Python

class Solution:def maxSum(self, nums: List[int], k: int, m: int) -> int:n = len(nums)# 前缀和数组s = [0] * (n + 1)for i in range(1, n + 1):s[i] = s[i - 1] + nums[i - 1]# f[j] 表示前 j 个元素中选取 i 个子数组的最大和f = [0] * (n + 1)# 遍历子数组数量for i in range(1, k + 1):# 新的 f 数组nf = [float('-inf')] * (n + 1)# 记录最大的 f[L] - s[L]mx = float('-inf')# 遍历 j, 确保左右两边有足够空间给其他子数组for j in range(i * m, n - (k - i) * m + 1):# 更新 mxmx = max(mx, f[j - m] - s[j - m])# 更新 nf[j]nf[j] = max(nf[j - 1], mx + s[j])  # 不选 vs 选f = nf  # 更新 f 数组return f[n]  # 返回最终结果

4、复杂度分析

• 时间复杂度：
  • 外层循环 k 次，内层循环 O(n) 次。
  • 总时间复杂度：O(k * n)。
• 空间复杂度：
  • 使用两个长度为 n + 1 的数组 f 和 nf。
  • 总空间复杂度：O(n)。

Q4、字典序最小的生成字符串

1、题目描述

给你两个字符串，str1 和 str2，其长度分别为 n 和 m 。

如果一个长度为 n + m - 1 的字符串 word 的每个下标 0 <= i <= n - 1 都满足以下条件，则称其由 str1 和 str2 生成：

• 如果 str1[i] == 'T'，则长度为 m 的 子字符串（从下标 i 开始）与 str2 相等，即 word[i..(i + m - 1)] == str2。
• 如果 str1[i] == 'F'，则长度为 m 的 子字符串（从下标 i 开始）与 str2 不相等，即 word[i..(i + m - 1)] != str2。

返回可以由 str1 和 str2 生成 的 字典序最小 的字符串。如果不存在满足条件的字符串，返回空字符串 ""。

如果字符串 a 在第一个不同字符的位置上比字符串 b 的对应字符在字母表中更靠前，则称字符串 a 的 字典序 小于 字符串 b。
如果前 min(a.length, b.length) 个字符都相同，则较短的字符串字典序更小。

子字符串 是字符串中的一个连续、非空 的字符序列。

示例 1：

输入: str1 = “TFTF”, str2 = “ab”

输出: “ababa”

解释:

下表展示了字符串 "ababa" 的生成过程：

下标	T/F	长度为 m 的子字符串
0	'T'	“ab”
1	'F'	“ba”
2	'T'	“ab”
3	'F'	“ba”

字符串 "ababa" 和 "ababb" 都可以由 str1 和 str2 生成。

返回 "ababa"，因为它的字典序更小。

示例 2：

输入: str1 = “TFTF”, str2 = “abc”

输出: “”

解释:

无法生成满足条件的字符串。

示例 3：

输入: str1 = “F”, str2 = “d”

输出: “a”

2、解题思路

这是一个复杂的字符串构造问题，需要结合字符串匹配和贪心算法来解决。以下是具体步骤：

1. 处理 T 的条件：
   • 使用 Z 算法（Z-function）来快速匹配 str2 的前后缀。
   • 对于每个 str1[i] == 'T'，确保 word[i..(i + m - 1)] == str2。
   • 如果无法满足，则返回空字符串。
2. 处理 F 的条件：
   • 对于每个 str1[i] == 'F'，确保 word[i..(i + m - 1)] != str2。
   • 如果 word[i..(i + m - 1)] 已经等于 str2，则修改最后一个待定字符为 'b'，使其不等于 str2。
3. 字典序最小：
   • 将所有待定字符初始化为 'a'，确保字典序最小。
   • 在需要修改时，将待定字符改为 'b'。

3、代码实现

C++

class Solution {// 计算 Z 函数vector<int> calc_z(const string& s) const {int n = s.size();vector<int> z(n);int box_l = 0, box_r = 0; // Z-box 的左右边界for (int i = 1; i < n; i++) {if (i <= box_r) {z[i] = min(z[i - box_l], box_r - i + 1);}while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {z[i]++;}if (i + z[i] - 1 > box_r) {box_l = i;box_r = i + z[i] - 1;}}z[0] = n;return z;}// 预处理待定位置void preprocessUndetermined(string& ans, vector<int>& pre_q) const {int last_q = -1;for (int i = 0; i < ans.size(); i++) {if (ans[i] == '?') {ans[i] = 'a'; // 将待定字符初始化为 'a'last_q = i;}pre_q[i] = last_q;}}public:string generateString(const string& s, const string& t) const {int n = s.size(), m = t.size();string ans(n + m - 1, '?'); // 初始化待定字符为 '?'// 处理 T 的条件vector<int> z = calc_z(t);int pre = -m; // 上一个 T 的位置for (int i = 0; i < n; i++) {if (s[i] != 'T') {continue;}// 计算重叠部分的大小int size = max(pre + m - i, 0);// 检查 t 的前后缀是否匹配if (size > 0 && z[m - size] < size) {return ""; // 无法满足条件, 返回空字符串}// 填充 t 的内容for (int j = size; j < m; j++) {ans[i + j] = t[j];}pre = i; // 更新上一个 T 的位置}// 预处理待定位置vector<int> pre_q(ans.size());preprocessUndetermined(ans, pre_q);// 重新计算 Z 函数, 用于匹配 tz = calc_z(t + ans);// 处理 F 的条件for (int i = 0; i < n; i++) {if (s[i] != 'F') {continue;}// 检查子串是否等于 tif (z[m + i] < m) {continue; // 不等于 t, 跳过}// 找到最后一个待定位置int j = pre_q[i + m - 1];if (j < i) {   // 没有待定位置return ""; // 无法满足条件, 返回空字符串}// 修改待定字符为 'b'ans[j] = 'b';i = j; // 直接跳到 j}return ans;}
};

4、复杂度分析

• 时间复杂度：
  • Z 函数的计算：O(n + m)。
  • 处理 T 和 F 的条件：O(n * m)。
  • 总时间复杂度：O(n * m)。
• 空间复杂度：
  • Z 函数数组：O(n + m)。
  • 待定位置数组：O(n + m)。
  • 总空间复杂度：O(n + m)。