leetcode 第 439 场算法比赛

背景

这次比赛题目其实不难，但是我在忙其他事情，就没怎么做题了。

A: 统计
B: 动态规划
C: 动态规划 D: 贪心

排名：200+
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest

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

题意：给一个长度为 n的数组，问在所有长度为 k 的子数组，哪个数字关联的子数组最多。
关联含义：数组存在于子数组中。
数据范围：长度 50 以内，值域 50 以内

思路：统计

枚举所有子数组，子数组值去重后，相关值索引加一。
最后遍历所有值域，输出最大值。

复杂度：O(n*k)

扩展1：假设长度很大，值域很小，该怎么做呢？
答案：可以滑动窗口动态维护值域集合。
复杂度：O(n * V)，V 为值域大小。

扩展2：假设长度很大，值域很大，该怎么做呢？
答案：值域分组，区间合并。
假设前缀数组 [0, x]已经枚举统计过了。
对于新的位置 p ，属于起始点为 [p-k+1,p] 的子数组，去除已经好枚举过的子数组，新增的子数组起始位置为 [max(x+1, p-k+1), p]。
新的子数组区间加1，最终即可计算出这个值所属的子数组个数，最终取最大值。
复杂度： O(n)

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

题意：给一个长度为 n 的字符串，最多进行 k 次修改，求修改后的最长回文子序列。
数据范围：字符串长度不大于 200，修改次数不大于 200。

思路：动态规划

状态定义: dp(l,r,k) 子字符串[l,r] 最多修改 k 次可以得到的最大回文子序列。
状态转移方程：

// Cost(l,r) : 位置 l 与 r 匹配的最小修改次数
dp(l,r,k) = max(
    dp(l+1,r-1, k-Cost(l,r)) + 2,
    dp(l+1, r, k),
    dp(l, r-1, k)
)

方程解释：左右端点尝试进行回文匹配与不匹配。
匹配时，需要操作代价不小于剩余操作次数 k。

Cost(l,r) 计算如下

int Trans(char a, char b) {
  int diff = abs(a - b);
  return min(diff, 26 - diff);
}

复杂度：O(200^3)

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

题意：给一个长度为 n的数组，问k个不重叠的长度为m的子数组的最大和是多少。
数据范围：数组长度[1,2000]，值域为[-1e4,1e4]，m 范围[1,3]

思路：动态规划

PS：这道题的关键是如何把状态转移方程的复杂度降低为常数，基本思路是储存一个辅助信息，直接把前缀状态的 max 都计算好，这样就转化为了只依赖上个状态了。

状态定义: dp(n,k) 前 n 个元素，取k个不重叠的子数组的最大和。

状态转移方程：

dp(n,k) = max(
  dp(n-1, k), // 不选择最后一个元素
  // dp(n-1,k-1) + sum(n, n), // 长度为 1，不能选择
  // ...
  // dp(n-m+1, k-1) + sum(n-m+2, n) 长度为 m-1，不能选择
  dp(n-m, k-1) + sum(n-m+1, n), // 长度为 m
  dp(n-m-1, k-1) + sum(n-m, n), // 长度为 m+1
  dp(n-m-2, k-1) + sum(n-m-1, n) //长度为 m+2
  ...
  dp(0, k-1) + sum(1,n) // 长度为 n
)

复杂度：O(n^2*k)

优化： 对齐之前枚举求和的部分，可以拆分一下
令 nm = n - m, k1 = k - 1，则方程可以转化如下

dp1(nm, k1, n) = max(
  dp(nm, k1) + sum(nm+1, n), // 长度为 m
  dp(nm-1, k1) + sum(nm, n), // 长度为 m+1
  dp(nm-2, k1) + sum(nm -1, n) //长度为 m+2
  ...
  dp(0, k1) + sum(1, n) // 长度为 n)
)
=  max(
  dp(nm, k1)                     + sum(nm+1, n), // 长度为 m
  dp(nm-1, k1) + sum(nm, nm-1)     + sum(nm, n), // 长度为 m+1
  dp(nm-2, k1) + sum(nm -1, nm-1)  + sum(nm, n) //长度为 m+2
  ...
  dp(0, k1)    + sum(1, nm-1)      + sum(nm, n) // 长度为 n)
)
= max(
  dp(nm, k1)          + sum(nm+1, n), // 长度为 m
  dp1(nm-1, k1, nm-1) + sum(nm, n)
) max(
  dp(nm, k1)          , // 长度为 m
  dp1(nm-1, k1, nm-1) + V(nm)
) + sum(nm+1, n)

简化上面的方程，如下。

dp2(nm,k1) = max(
  dp(nm, k1),
  dp1(nm-1, k1) + V
)
dp(n,k) = max(
  dp(n-1, k), // 不选择最后一个元素
  dp2(n-m, k-1) + sum(n-m+1,n) // 选择至少 m 个
)

简单来说，把O(n)的状态转移复杂度，利用前缀信息，转化为了O(2)的复杂度。
总体复杂度：O(n*k)

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

题意：给两个字符串，长度为 m 的模式串 pat 和长度为 n 的匹配串 mat，现在需要构造一个 n+m-1的字符串 ans。
当 pat[i] 为 T 时，要求 ans[i,i+n-1] 与 mat 相等, 当为 F 时不相等。
问是否可以构造出这样的答案，可以了输出字典序最小的答案。
数据范围：n 为[1,1e4]，m为[1,500]

思路：贪心。

第一步：所有字符串标记未确定。
第二步：遍历 pat，对于所有为 T 的匹配，可以确定某些位置的值，进行赋值并标记已确定，如果存在冲突，则不存在答案。
第三步：对于所有未标记的字符串，贪心设置为最小值 a。
第四步：从前到后遍历所有的 F，判断是否是不匹配的，如果不匹配，则不需要处理。
如果是匹配的，则在区间内从后到前找到第一个未标记的串，未找到代表不存在答案，存在则将值从 a 修改为 b。

复杂度：O(n*m)

可能得反例：第四步，将值从 a 修改为 b，会不会导致前面原先不匹配的变得匹配呢？
正确性证明：暂时没推导出来，需要分情况讨论，情况太多了。

这个问题扔给 DeepSeek .
满血版 R1 推导了几十分钟，得到的结论是综上，算法的大致步骤是正确的。
本地 DeepSeek 直接超时了。
豆包的 marsCode DeepSeek R1 也处理超时了。
阿里巴巴的通义灵码 DeepSeek R1 也处理超时了。
github Copilot GPT-4o 给出的结果是贪心正确。

五、最后

总的来看这次比赛。
第二题是简单的动态规划。
第三题则是比较复杂的动态规划，状态转移方程优化部分总是想不明白。
第四题是贪心，但是无法证明正确性，所以我就没去做了。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号： tiankonguse
公众号ID： tiankonguse-code