第439场周赛：找出最大的几近缺失整数、至多 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、解题思绪

问题理解

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

解题思绪

• 特殊环境处置惩罚：
  
  
  
  • 如果 nums 的长度小于 k，则不可能存在符合条件的整数，直接返回 -1。
    
  • 如果 nums 的长度即是 k，则整个数组是一个子数组，返回数组中的最大值。
    
  
  
• 一般环境：
  
  
  
  • 使用哈希表 hash 记录每个整数在的个数。
    
  • 遍历 nums，查抄每个整数是否满意 “几近缺失” 的条件。
    
  • 如果 k == 1，则直接查抄每个整数是否只出现一次。
    
  
  
• 返回效果：
  
  
  
  • 返回满意条件的最大整数，如果没有则返回 -1。
    
  
  

3、代码实现

C++

1. class Solution {
2. public:
3.     int largestInteger(vector<int>& nums, int k) {
4.         const int n = nums.size();
5.         // 特殊情况处理
6.         // 如果数组长度小于 k, 返回 -1
7.         if (n < k) {
8.             return -1;
9.         }
10.         // 如果数组长度等于 k, 返回数组中的最大值
11.         if (n == k) {
12.             return *max_element(nums.begin(), nums.end());
13.         }
15.         // 使用哈希表记录每个整数在 nums 中的位置
16.         unordered_map<int, int> hash;
17.         for (int i = 0; i < n; ++i) {
18.             hash[nums[i]]++;
19.         }
21.         // 初始化最大几近缺失整数
22.         int maxMissing = -1;
24.         // 检查单个元素是否满足条件
25.         auto checkSingleElement = [&](int num) {
26.             if (hash[num] == 1) {
27.                 maxMissing = max(maxMissing, num);
28.             }
29.         };
31.         // 检查第一个和最后一个元素
32.         checkSingleElement(nums[0]);
33.         checkSingleElement(nums.back());
35.         // 如果 k == 1, 直接检查每个整数是否只出现一次
36.         if (k == 1) {
37.             for (auto [k, v] : hash) {
38.                 checkSingleElement(k);
39.             }
40.         }
42.         return maxMissing;
43.     }
44. };

复制代码

Python

1. class Solution:
2.     def largestInteger(self, nums: List[int], k: int) -> int:
3.         n = len(nums)
4.         # 特殊情况处理
5.         if n < k:
6.             return -1
7.         if n == k:
8.             return max(nums)
10.         # 使用哈希表记录每个整数的出现次数
11.         hash = defaultdict(int)
12.         for num in nums:
13.             hash[num] += 1
15.         # 初始化最大几近缺失整数
16.         max_missing = -1
18.         # 检查单个元素是否满足条件
19.         def check_single_element(num):
20.             if hash[num] == 1:
21.                 nonlocal max_missing
22.                 max_missing = max(max_missing, num)
24.         # 检查第一个和最后一个元素
25.         check_single_element(nums[0])
26.         check_single_element(nums[-1])
28.         # 如果 k == 1, 直接检查每个整数是否只出现一次
29.         if k == 1:
30.             for num in hash:
31.                 check_single_element(num)
33.         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、解题思绪

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

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

3、代码实现

C++

1. class Solution {
2. public:
3.     int longestPalindromicSubsequence(string s, int k) {
4.         int n = s.size();
5.         // dp[i][j][l] 表示在子串 s[i..j] 中进行最多 l 次操作后,
6.         // 最长回文子序列的长度
7.         vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k + 1, -1)));
8.         return helper(s, 0, n - 1, k, dp);
9.     }
11.     int helper(const string& s, int i, int j, int l, vector<vector<vector<int>>>& dp) {
12.         // 如果已经计算过, 直接返回结果
13.         if (dp[i][j][l] != -1) {
14.             return dp[i][j][l];
15.         }
17.         // 边界条件
18.         if (i == j) {
19.             return dp[i][j][l] = 1; // 只有一个字符
20.         }
21.         if (i > j) {
22.             return dp[i][j][l] = 0; // 空字符
23.         }
25.         // 如果 s[i] == s[j], 直接递归处理子问题
26.         if (s[i] == s[j]) {
27.             dp[i][j][l] = 2 + helper(s, i + 1, j - 1, l, dp);
28.         } else {
29.             // 如果 s[i] != s[j], 尝试替换 s[i] 或者 s[j]
30.             int cost = minOperations(s[i], s[j]);
31.             if (l >= cost) {
32.                 dp[i][j][l] = 2 + helper(s, i + 1, j - 1, l - cost, dp);
33.             }
34.             // 不替换, 分别尝试删除 s[i] 或 s[j]
35.             dp[i][j][l] = max(dp[i][j][l], max(helper(s, i + 1, j, l, dp), helper(s, i, j - 1, l, dp)));
36.         }
38.         return dp[i][j][l];
39.     }
41.     int minOperations(char a, char b) {
42.         // 计算将 a 替换成 b 所需的最小操作次数
43.         int diff = abs(a - b);
44.         return min(diff, 26 - diff);
45.     }
46. };

复制代码

Python

1. class Solution:
2.     def longestPalindromicSubsequence(self, s: str, k: int) -> int:
3.         n = len(s)
4.         # 定义 dp 数组
5.         dp = [[[-1 for _ in range(k + 1)] for _ in range(n)] for _ in range(n)]
6.         return self.helper(s, 0, n - 1, k, dp)
8.     def helper(self, s: str, i: int, j: int, l: int, dp: List[List[List[int]]]) -> int:
9.         # 如果已经计算过, 直接返回结果
10.         if dp[i][j][l] != -1:
11.             return dp[i][j][l]
13.         # 边界条件
14.         if i == j:
15.             dp[i][j][l] = 1     # 只有一个字符
16.             return dp[i][j][l]
17.         if i > j:
18.             dp[i][j][l] = 0     # 空字符串
19.             return dp[i][j][l]
21.         # 如果 s[i] == s[j], 直接递归处理子问题
22.         if s[i] == s[j]:
23.             dp[i][j][l] = 2 + self.helper(s, i + 1, j - 1, l, dp)
24.         else:
25.             # 如果 s[i] != s[j]，尝试替换 s[i] 或 s[j]
26.             cost = self.minOperations(s[i], s[j])
27.             if l >= cost:
28.                 dp[i][j][l] = 2 + self.helper(s, i + 1, j - 1, l - cost, dp)
29.             # 不替换, 分别尝试删除 s[i] 或 s[j]
30.             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)))
32.         return dp[i][j][l]
34.     def minOperations(self, a: str, b: str) -> int:
35.         # 计算将 a 替换为 b 所需的最小操作次数
36.         diff = abs(ord(a) - ord(b))
37.         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、解题思绪

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

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

3、代码实现

C++

1. class Solution {
2. public:
3.     int maxSum(vector<int>& nums, int k, int m) {
4.         int n = nums.size();
5.         // 前缀和数组
6.         vector<int> s(n + 1);
7.         partial_sum(nums.begin(), nums.end(), s.begin() + 1);
9.         // f[j] 表示前 j 个元素中选取 i 个子数组的最大和
10.         vector<int> f(n + 1);
12.         // 遍历子数组数量
13.         for (int i = 1; i <= k; i++) {
14.             // 新的 f 数组
15.             vector<int> nf(n + 1, INT_MIN / 2);
16.             // 记录最大的 f[L] - s[L]
17.             int mx = INT_MIN / 2;
19.             // 遍历 j, 确保左右两边有足够空间给其他子数组
20.             for (int j = i * m; j <= n - (k - i) * m; j++) {
21.                 // 更新 mx
22.                 mx = max(mx, f[j - m] - s[j - m]);
23.                 // 更新 nf[j]
24.                 nf[j] = max(nf[j - 1], mx + s[j]); // 不选 vs 选
25.             }
26.             f = move(nf); // 更新 f 数组
27.         }
29.         return f[n]; // 返回最终结果
30.     }
31. };

复制代码

Python

1. class Solution:
2.     def maxSum(self, nums: List[int], k: int, m: int) -> int:
3.         n = len(nums)
4.         # 前缀和数组
5.         s = [0] * (n + 1)
6.         for i in range(1, n + 1):
7.             s[i] = s[i - 1] + nums[i - 1]
9.         # f[j] 表示前 j 个元素中选取 i 个子数组的最大和
10.         f = [0] * (n + 1)
12.         # 遍历子数组数量
13.         for i in range(1, k + 1):
14.             # 新的 f 数组
15.             nf = [float('-inf')] * (n + 1)
16.             # 记录最大的 f[L] - s[L]
17.             mx = float('-inf')
19.             # 遍历 j, 确保左右两边有足够空间给其他子数组
20.             for j in range(i * m, n - (k - i) * m + 1):
21.                 # 更新 mx
22.                 mx = max(mx, f[j - m] - s[j - m])
23.                 # 更新 nf[j]
24.                 nf[j] = max(nf[j - 1], mx + s[j])  # 不选 vs 选
25.             f = nf  # 更新 f 数组
27.         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 == 'T'，则长度为 m 的 子字符串（从下标 i 开始）与 str2 相等，即 word[i..(i + m - 1)] == str2。
  
• 如果 str1 == '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、解题思绪

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

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

3、代码实现

C++

1. class Solution {
2.     // 计算 Z 函数
3.     vector<int> calc_z(const string& s) const {
4.         int n = s.size();
5.         vector<int> z(n);
6.         int box_l = 0, box_r = 0; // Z-box 的左右边界
7.         for (int i = 1; i < n; i++) {
8.             if (i <= box_r) {
9.                 z[i] = min(z[i - box_l], box_r - i + 1);
10.             }
11.             while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
12.                 z[i]++;
13.             }
14.             if (i + z[i] - 1 > box_r) {
15.                 box_l = i;
16.                 box_r = i + z[i] - 1;
17.             }
18.         }
19.         z[0] = n;
20.         return z;
21.     }
23.     // 预处理待定位置
24.     void preprocessUndetermined(string& ans, vector<int>& pre_q) const {
25.         int last_q = -1;
26.         for (int i = 0; i < ans.size(); i++) {
27.             if (ans[i] == '?') {
28.                 ans[i] = 'a'; // 将待定字符初始化为 'a'
29.                 last_q = i;
30.             }
31.             pre_q[i] = last_q;
32.         }
33.     }
35. public:
36.     string generateString(const string& s, const string& t) const {
37.         int n = s.size(), m = t.size();
38.         string ans(n + m - 1, '?'); // 初始化待定字符为 '?'
40.         // 处理 T 的条件
41.         vector<int> z = calc_z(t);
42.         int pre = -m; // 上一个 T 的位置
43.         for (int i = 0; i < n; i++) {
44.             if (s[i] != 'T') {
45.                 continue;
46.             }
47.             // 计算重叠部分的大小
48.             int size = max(pre + m - i, 0);
49.             // 检查 t 的前后缀是否匹配
50.             if (size > 0 && z[m - size] < size) {
51.                 return ""; // 无法满足条件, 返回空字符串
52.             }
53.             // 填充 t 的内容
54.             for (int j = size; j < m; j++) {
55.                 ans[i + j] = t[j];
56.             }
57.             pre = i; // 更新上一个 T 的位置
58.         }
60.         // 预处理待定位置
61.         vector<int> pre_q(ans.size());
62.         preprocessUndetermined(ans, pre_q);
64.         // 重新计算 Z 函数, 用于匹配 t
65.         z = calc_z(t + ans);
67.         // 处理 F 的条件
68.         for (int i = 0; i < n; i++) {
69.             if (s[i] != 'F') {
70.                 continue;
71.             }
72.             // 检查子串是否等于 t
73.             if (z[m + i] < m) {
74.                 continue; // 不等于 t, 跳过
75.             }
76.             // 找到最后一个待定位置
77.             int j = pre_q[i + m - 1];
78.             if (j < i) {   // 没有待定位置
79.                 return ""; // 无法满足条件, 返回空字符串
80.             }
81.             // 修改待定字符为 'b'
82.             ans[j] = 'b';
83.             i = j; // 直接跳到 j
84.         }
86.         return ans;
87.     }
88. };

复制代码

4、复杂度分析

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。