LeetCode --- 439周赛

题目列表

3471. 找出最大的几近缺失整数
3472. 至多 K 次操作后的最长回文子序列
3473. 长度至少为 M 的 K 个子数组之和
3474. 字典序最小的生成字符串

一、找到最大的几近缺失整数

简单来说，就是看数字 $x$ 出现在多少个大小为 $k$ 的子数组中，如果只出现在一个大小为 $k$ 的子数组中，则认为 $x$ 是几近缺失的整数，返回最大的 $x$ 即可，直接暴力所有大小为 $k$ 的子数组，然后统计每一个数字的出现次数即可，代码如下

// C++
class Solution {
public:int largestInteger(vector<int>& nums, int k) {int n = nums.size(), mx = -1;for(int x : nums){int cnt = 0;for(int j = 0; j <= n - k; j++){if(count(nums.begin() + j, nums.begin() + j + k, x)){cnt++;if(cnt > 1){break;}}}if(cnt == 1) mx = max(mx, x);}return mx;}
};

# Python
class Solution:def largestInteger(self, nums: List[int], k: int) -> int:n = len(nums)mx = -1for x in nums:cnt = 0for j in range(n - k + 1):if x in nums[j:j+k]:cnt += 1if cnt > 1:breakif cnt == 1:mx = max(mx, x)return mx

如果我们仔细观察就会发现以下一些规律：

• 当 $k=1$ 时，问题变成只出现一次的数字的最大值
• 当 $k=n$ 时，问题变成求 $nums$ 数组中的最大值
• 当 $1<k<n$ 时，对于任意一个 $0<i<n-1$ 的 $nums[i]$ 来说，nums[i] 都必然出现在 $\ge 2$ 个子数组中，只有 $nums[0]$ 和 $nums[-1]$ 只分别出现在 $nums[0:k]$ 和 $nums[n-k:n]$ 中，我们只要考虑 $nums[0]$ 和 $nums[-1]$ 在 $nums$ 中是否只出现了一次即可

代码如下

// C++
class Solution {
public:int largestInteger(vector<int>& nums, int k) {int n = nums.size(), mx = -1;if(k == n) {mx = ranges::max(nums);}else if(k == 1){unordered_map<int,int>mp;for(auto x : nums) ++mp[x];for(auto [x, c] : mp){if(c == 1){mx = max(mx, x);}}}else{int cnt0 = 0, cnt1 = 0;for(int i = 0; i < n; i++){if(nums[i] == nums[0]) cnt0++;if(nums[i] == nums.back()) cnt1++;}if(cnt0 == 1) mx = max(mx, nums[0]);if(cnt1 == 1) mx = max(mx, nums.back());}return mx;}
};

# Python
class Solution:def f(self, nums: List[int], x: int) -> int:return -1 if x in nums else xdef largestInteger(self, nums: List[int], k: int) -> int:n = len(nums)mx = -1if k == n:mx = max(nums)elif k == 1:cnt = Counter(nums)for x, c in cnt.items():if c == 1:mx = max(mx, x)else:mx = max(self.f(nums[1:], nums[0]), self.f(nums[:-1], nums[-1]))return mx

二、至多 K 次操作后的最长回文子序列

这题和 516. 最长回文子序列 类似，是加强版，多了可以有 k 次修改字符的操作这个条件，我们同样可以用区间 $DP$ 来求解

• 定义：$dfs(l,r,k)$ 表示区间 $[l,r]$ 中还能进行 $k$ 次操作的最长回文串的长度
• 转移方程：$dfs(l,r,k)=max(dfs(l+1,r,k),dfs(l,r-1,k),dfs(l+1,r-1,k-ops)+2)$
  • $dfs(l+1,r,k)$ 表示不考虑 $s[l]$ 的最长回文串的长度
  • $dfs(l,r-1,k)$ 表示不考虑 $s[r]$ 的最长回文串的长度
  • $dfs(l+1,r-1,k-ops)$ 表示考虑让 $s[l]=s[r]$ 后区间 $[l+1,r-1]$ 最长回文串的长度，其中 $ops$ 为让 $s[l]=s[r]$ 所需要进行的操作数，令 $dist=abs(s[l]-s[r])$，则 $ops=min(dist,26-dist)$
• 初始化：当 $l=r$ 时，返回 $1$，当 $l>r$ 时，返回 $0$

代码如下

// C++
class Solution {
public:int longestPalindromicSubsequence(string s, int k) {int n = s.size();int f[n][n][k+1];memset(f, -1, sizeof(f));auto dfs = [&](this auto&& dfs, int l, int r, int k)->int{if(l >= r){return l == r;}if(f[l][r][k] != -1) return f[l][r][k];int res = max(dfs(l + 1, r, k), dfs(l, r - 1, k));int ops = abs(s[l] - s[r]);ops = min(ops, 26 - ops);if(ops <= k){res = max(res, dfs(l + 1, r - 1, k - ops) + 2);}return f[l][r][k] = res;};return dfs(0, n - 1, k);}
};

# Python
class Solution:def longestPalindromicSubsequence(self, s: str, k: int) -> int:s = list(map(ord, s))n = len(s)@cachedef dfs(l: int, r: int, k: int) -> int:if l >= r:return r - l + 1res = max(dfs(l + 1, r, k), dfs(l, r - 1, k))ops = abs(s[l] - s[r])ops = min(ops, 26 - ops)if ops <= k:res = max(res, dfs(l + 1, r - 1, k - ops) + 2)return resans = dfs(0, n - 1, k)dfs.cache_clear()return ans

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

选 $k$ 个不重叠的子数组，使得它们的元素和最大，很经典的划分型 $DP$，一般的解法如下

• 定义：$f[i][j]$ 表示前 $j$ 个元素中选出 $i$ 个长度 $\ge m$ 的子数组的最大和
• 状态转移方程
  • $f[i][j]=f[i][j-1]$ 表示不选第 $j$ 个元素时，从前 $j$ 个元素中选出 $i$ 个长度 $\ge m$ 的子数组的最大和
  • $f[i][j]=max(f[i-1][k]+pre[j]-pre[k])$，其中 $k\in [(i-1)\ast m,j-m]$，表示选取 $[k,j)$ 作为第 $i$ 个子数组时，从前 $j$ 个元素中选出 $i$ 个长度 $\ge m$ 的子数组的最大和
• 初始化
  • 当 $i=0$ 时，表示没有选取子数组，$f[0][j]=0$
  • 当 $j<i\ast m$ 时，表示剩余的元素不能共选出 $i$ 个长度至少为 $m$ 的子数组，$f[i][j]=-inf$，表示不合法

代码如下

// C++
// 超时写法
class Solution {
public:int maxSum(vector<int>& nums, int k, int m) {int n = nums.size();vector<int> pre(n + 1);for(int i = 0; i < n; i++)pre[i + 1] = pre[i] + nums[i];vector f(k + 1, vector<int>(n + 1, INT_MIN/2));f[0] = vector<int>(n + 1);for(int i = 1; i <= k; i++){for(int j = i * m; j <= n - (k - i) * m; j++){f[i][j] = f[i][j - 1];for(int x = (i - 1) * m; x <= j - m; x++){f[i][j] = max(f[i][j], f[i-1][x] + pre[j] - pre[x]);}}}return f[k][n];}
};
// 优化时间复杂度
// 在循环计算 f[i][j] = max(f[i][j], f[i-1][x] + pre[j] - pre[x]) 时
// 我们会发现 max(f[i][j], f[i-1][x] + pre[j] - pre[x]) = max(f[i-1][x] - pre[x]) + pre[j] 
// 其中 max(f[i-1][x] - pre[x]) 我们可以边计算 f[i][j]，边维护，具体代码如下
class Solution {
public:int maxSum(vector<int>& nums, int k, int m) {int n = nums.size();vector<int> pre(n + 1);for(int i = 0; i < n; i++)pre[i + 1] = pre[i] + nums[i];vector f(k + 1, vector<int>(n + 1, INT_MIN/2));f[0] = vector<int>(n + 1);for(int i = 1; i <= k; i++){int mx = INT_MIN;for(int j = i * m; j <= n - (k - i) * m; j++){mx = max(mx, f[i - 1][j - m] - pre[j - m]);f[i][j] = max(f[i][j - 1], pre[j] + mx);}}return f[k][n];}
};

# Python
class Solution:def maxSum(self, nums: List[int], k: int, m: int) -> int:n = len(nums)pre = [0] * (n + 1)for i in range(n):pre[i+1] = pre[i] + nums[i]f = [[-inf] * (n + 1) for _ in range(k + 1)]f[0] = [0] * (n + 1)for i in range(1, k + 1):mx = -inffor j in range(i * m, n - (k - i) * m + 1):mx = max(mx, f[i - 1][j - m] - pre[j - m])f[i][j] = max(f[i][j - 1], mx + pre[j])return f[k][n]

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

这题的思路是先将确定的位置填上，再将不确定的位置填上 $a$ ，再遍历 $str1$ 中 $F$ 的位置，来检查是否 $ans[i:i+m]=str2$ ，如果相等，则从后往前遍历 $ans[i:i+m]$，将最靠右的能改变的位置填上 $b$，然后依次验证 $str1$ 中所有填 $F$ 的位置，如果不能修改，则返回空串
代码如下

// C++
class Solution {
public:string generateString(string str1, string str2) {int n = str1.size(), m = str2.size();string ans(n + m - 1, '?');// 将确定位置的值填上for(int i = 0; i < n; i++){if(str1[i] == 'T'){for(int j = 0; j < m; j++){// 如果发生冲突，则返回空串if(ans[i+j] != '?' && ans[i+j] != str2[j])return "";ans[i+j] = str2[j];}}}// 记录可以修改的下标，并将所有不确定的位置都变成 avector<bool> pos(n + m - 1, false);for(int i = 0; i < ans.size(); i++){if(ans[i] == '?'){pos[i] = true;ans[i] = 'a';}}// 依次验证所有的 F 位置for(int i = 0; i < n; i++){if(str1[i] == 'F' && ans.substr(i, m) == str2){bool flag = true;for(int j = m - 1; j >= 0; j--){if(pos[i+j]){ans[i+j] = 'b';flag = false;break;}}// 如果不能修改，则返回空串if(flag) return "";}}return ans;}
};