本文最后更新于 1 分钟前，文中所描述的信息可能已发生改变。
Q1. 找出最大的几近缺失整数
解题思路
统计每个区间的数字出现次数总数，然后再次遍历所有区间，找到该区间内出现次数等于统计次数的数字，返回最大值。
示例代码
python
class Solution:
def largestInteger(self, nums: List[int], k: int) -> int:
n = len(nums)
ans = -1
cnt = Counter()
for i in range(len(nums) - k + 1):
for j in range(i, i + k):
cnt[nums[j]] += 1
for i in range(n - k + 1):
tmp = Counter(nums[i: i + k])
for k1, v1 in cnt.items():
if v1 == tmp[k1]:
ans = max(ans, k1)
return ansQ2. 至多 K 次操作后的最长回文子序列
解题思路
记忆化搜索：
i 和 j 分别表示区间的左右边界，cnt 表示还剩余的操作次数，如果 i >= j，则返回 0 （偶数长度） 或 1（奇数长度）。
选或不选:
- 不选的话，res = max(dfs(i + 1, j, cnt), dfs(i, j - 1, cnt)，
- 选的话，判断一下操作次数是否满足, res = dfs(i + 1, j - 1, cnt - tmp) + 2
区间 DP：
f[k][l][r] 表示在区间 [l, r + 1] 内最多进行 k 次操作的最长回文子序列长度。
示例代码
python
class Solution:
def longestPalindromicSubsequence(self, s: str, k: int) -> int:
n = len(s)
def check(i, j):
a, b = ord(s[i]) - 97, ord(s[j]) - 97
return min((a - b + 26) % 26, (b - a + 26) % 26)
@cache
def dfs(i, j, cnt):
if i >= j:
return int(i == j)
tmp = check(i, j)
res = max(dfs(i + 1, j, cnt), dfs(i, j - 1, cnt))
if tmp <= cnt:
res = max(res, dfs(i + 1, j - 1, cnt - tmp) + 2)
return res
return dfs(0, n - 1, k)python
class Solution:
def longestPalindromicSubsequence(self, s: str, k: int) -> int:
n = len(s)
f = [[[0] * n for _ in range(n)] for _ in range(k + 1)]
def check(i, j):
a, b = ord(s[i]) - 97, ord(s[j]) - 97
return min((a - b + 26) % 26, (b - a + 26) % 26)
for t in range(k + 1):
for l in range(n - 1, -1, -1):
f[t][l][l] = 1
for r in range(l + 1, n):
tmp = check(l, r)
res = max(f[t][l + 1][r], f[t][l][r - 1])
if tmp <= t:
res = max(res, f[t - tmp][l + 1][r - 1] + 2)
f[t][l][r] = res
return f[k][0][n - 1]Q3. 长度至少为 M 的 K 个子数组之和
解题思路
记忆化搜索，选或不选：
- 不选的话，res = dfs(i + 1, cnt)
- 选的话，res = dfs(j, cnt - 1) + pre[j] - pre[i]), j - i >= m
时间复杂度： O(n^2 * k)，会超时。
划分 DP，滚动数组优化：
时间复杂度：O(n * k)
示例代码
python
class Solution:
def maxSum(self, nums: List[int], k: int, m: int) -> int:
n = len(nums)
pre = list(accumulate(nums, initial=0))
@cache
def dfs(i, cnt):
if i == n or cnt == 0:
return -inf if cnt else 0
res = dfs(i + 1, cnt) if i + cnt * m < n else -inf
for j in range(i + m, n - (cnt - 1) * m + 1):
res = max(res, dfs(j, cnt - 1) + pre[j] - pre[i])
return res
ans = dfs(0, k)
dfs.cache_clear()
return anspython
class Solution:
def maxSum(self, nums: List[int], k: int, m: int) -> int:
n = len(nums)
pre = list(accumulate(nums, initial=0))
f = [0] * (n + 1)
d = [0] * (n + 1)
for i in range(1, k + 1):
d = [f[j] - pre[j] for j in range(n + 1)]
f[(i - 1) * m: i * m] = [-inf] * m
mx = -inf
for j in range(i * m, n - (k - i) * m + 1):
mx = max(mx, d[j - m])
f[j] = max(f[j - 1], mx + pre[j])
return f[n]相似题目
Q4. 字典序最小的生成字符串
解题思路
参考：构造 & 贪心
示例代码
python
class Solution:
def generateString(self, str1: str, str2: str) -> str:
n, m = len(str1), len(str2)
ans = [''] * (n + m - 1)
flag = [False] * (n + m - 1)
for i, c in enumerate(str1):
if c == 'F': continue
for j in range(m):
if ans[i + j] != '' and ans[i + j] != str2[j]:
return ''
ans[i + j] = str2[j]
flag[i + j] = True
for i in range(len(ans)):
if ans[i] == '':
ans[i] = 'a'
for i, c in enumerate(str1):
if c == 'F' and ''.join(ans[i: i + m]) == str2:
failed = True
for j in range(m - 1, -1, -1):
if not flag[i + j]:
ans[i + j] = 'b'
failed = False
break
if failed: return ''
return ''.join(ans)