当前位置：首页 > article >正文

LeetCode --- 439周赛

article 2025/3/13 3:17:23

题目列表

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 = -1
        for x in nums:
            cnt = 0
            for j in range(n - k + 1):
                if x in nums[j:j+k]:
                    cnt += 1
                    if cnt > 1:
                        break
            if cnt == 1:
                mx = max(mx, x)
        return mx

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

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

代码如下

// 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 x
    def largestInteger(self, nums: List[int], k: int) -> int:
        n = len(nums)
        mx = -1
        if 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 次修改字符的操作这个条件，我们同样可以用区间 $D P$ 来求解

定义： $df s (l, r, k)$ 表示区间 $[l, r]$ 中还能进行 $k$ 次操作的最长回文串的长度
转移方程： $df s (l, r, k) = ma x (df s (l + 1, r, k), df s (l, r - 1, k), df s (l + 1, r - 1, k - o p s) + 2)$
- $df s (l + 1, r, k)$ 表示不考虑 $s [l]$ 的最长回文串的长度
- $df s (l, r - 1, k)$ 表示不考虑 $s [r]$ 的最长回文串的长度
- $df s (l + 1, r - 1, k - o p s)$ 表示考虑让 $s [l] = s [r]$ 后区间 $[l + 1, r - 1]$ 最长回文串的长度，其中 $o p s$ 为让 $s [l] = s [r]$ 所需要进行的操作数，令 $d i s t = ab s (s [l] - s [r])$ ，则 $o p s = min (d i s t, 26 - d i s t)$
初始化：当 $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)
        @cache
        def dfs(l: int, r: int, k: int) -> int:
            if l >= r:
                return r - l + 1
            res = 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 res
        ans = dfs(0, n - 1, k)
        dfs.cache_clear()
        return ans

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

在这里插入图片描述
选 $k$ 个不重叠的子数组，使得它们的元素和最大，很经典的划分型 $D P$ ，一般的解法如下

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

代码如下

// 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 = -inf
            for 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$ ，再遍历 $s t r 1$ 中 $F$ 的位置，来检查是否 $an s [i : i + m] = s t r 2$ ，如果相等，则从后往前遍历 $an s [i : i + m]$ ，将最靠右的能改变的位置填上 $b$ ，然后依次验证 $s t r 1$ 中所有填 $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];
                }
            }
        }
        // 记录可以修改的下标，并将所有不确定的位置都变成 a
        vector<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;
    }
};