欢迎大家加QQ群：623375442，可以方便群里面交流。今天是快乐的DP周，第二题有点偏难。这起码5分，甚至6分了吧。
100527. Find the Largest Almost Missing Integer
给你一个整数数组 nums 和一个整数 k 。
如果整数 x 恰好仅出现在 nums 中的一个大小为 k 的子数组中，则认为 x 是 nums 中的几近缺失（almost missing）整数。
返回 nums 中 最大的几近缺失 整数，如果不存在这样的整数，返回 -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]
解答：为了减少代码错误可能，直接使用暴力遍历所有可能子数组。
class Solution {
public int largestInteger(int[] nums, int k) {
int[] count = new int[51];
for (int i = k - 1; i < nums.length; ++i) {
boolean[] isVisit = new boolean[51];
for (int j = i - k + 1; j <= i; ++j) {
if (!isVisit[nums[j]]) {
count[nums[j]] += 1;
isVisit[nums[j]] = true;
}
}
}
for (int i = 50; i >= 0; --i) {
if (count[i] == 1) return i;
}
return -1;
}
}100596. Longest Palindromic Subsequence After at Most K Operations
给你一个字符串 s 和一个整数 k。
在一次操作中，你可以将任意位置的字符替换为字母表中相邻的字符（字母表是循环的，因此 'z' 的下一个字母是 'a'）。例如，将 'a' 替换为下一个字母结果是 'b'，将 'a' 替换为上一个字母结果是 'z'；同样，将 'z' 替换为下一个字母结果是 'a'，替换为上一个字母结果是 'y'。
返回在进行 最多 k 次操作后，s 的 最长回文子序列 的长度。
子序列 是一个 非空 字符串，可以通过删除原字符串中的某些字符（或不删除任何字符）并保持剩余字符的相对顺序得到。
回文 是正着读和反着读都相同的字符串。
测试样例：
输入： s = "abced", k = 2
输出：3
解释:
- 将 s[1] 替换为下一个字母，得到 "acced"。
- 将 s[4] 替换为上一个字母，得到 "accec"。
子序列 "ccc" 形成一个长度为 3 的回文，这是最长的回文子序列。
解答：动态规划题。我们设计一个dp数组dp[i][j][k]代表s[i..j]使用k次变化，最长的回文子序列。递推公式可以详见代码。
class Solution {
public int longestPalindromicSubsequence(String s, int k) {
int len = s.length();
int[][][] dp = new int[len][len][k + 1];
for (int i = 0; i < len; ++i) {
int st = 0, ed = i;
while (ed < s.length()) {
int diff = minimum(s.charAt(st) - 'a', s.charAt(ed) - 'a');
for (int j = 0; j <= k; ++j) {
if (i == 0) {
dp[st][ed][j] = 1;
} else {
dp[st][ed][j] = Math.max(dp[st][ed - 1][j], dp[st + 1][ed][j]);
if (j != 0) {
dp[st][ed][j] = Math.max(dp[st][ed][j - 1], dp[st][ed][j]);
}
if (j >= diff) {
dp[st][ed][j] = Math.max(dp[st][ed][j], dp[st + 1][ed - 1][j - diff] + 2);
}
}
}
++st;
++ed;
}
}
return dp[0][len - 1][k];
}
private int minimum(int st, int ed) {
int res = Integer.MAX_VALUE;
for (int i = 0; i < 26; ++i) {
res = Math.min(res, Math.min(Math.abs(i - st), 26 - Math.abs(i - st)) + Math.min(Math.abs(i - ed), 26 - Math.abs(i - ed)));
}
return res;
}
}100540. Sum of K Subarrays With Length at Least M
给你一个整数数组 nums 和两个整数 k 和 m。
返回数组 nums 中 k 个不重叠子数组的 最大 和，其中每个子数组的长度 至少 为 m。
子数组 是数组中的一个连续序列。
测试样例：
输入：nums = [-10,3,-1,-2], k = 4, m = 1
输出：-10
解释: 最优的选择是将每个元素作为一个子数组。输出为 (-10) + 3 + (-1) + (-2) = -10。
解答：动态规划题。还是用了TreeSet记录最大值，其实不用。。。赛后我再改改这题。有这个条件：每个子数组的长度 至少 为 m。所以我们用前缀和变形，记录一下最大位置。然后暴力遍历数组k次，来计算不重叠子数组的 最大 和。
class Solution {
public int maxSum(int[] nums, int k, int m) {
int[] prefixSum = new int[nums.length + 1];
for (int i = 0; i < nums.length; ++i) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int[] dp = new int[nums.length];
for (int i = 1; i <= k; ++i) {
int[] nextDp = new int[nums.length];
Arrays.fill(nextDp, Integer.MIN_VALUE / 2);
int[] finalDp = dp;
TreeSet<Integer> max = new TreeSet<>((a, b)
-> (Integer.compare(cal(finalDp, prefixSum, b), cal(finalDp, prefixSum, a))));
for (int j = i * m - 1; j < nums.length; ++j) {
max.add(j - m);
int tmp = max.first();
if (i == 1) {
if (j - 1 < 0) {
nextDp[j] = prefixSum[j + 1];
} else if (tmp == -1) {
nextDp[j] = Math.max(nextDp[j - 1], prefixSum[j + 1]);
} else {
nextDp[j] = Math.max(nextDp[j - 1], dp[tmp] + prefixSum[j + 1] - prefixSum[tmp + 1]);
}
} else {
nextDp[j] = Math.max(nextDp[j - 1], dp[tmp] + prefixSum[j + 1] - prefixSum[tmp + 1]);
}
}
dp = nextDp;
}
return dp[nums.length - 1];
}
private int cal(int[] dp, int[] prefixSum, int pos) {
if (pos == -1) {
return prefixSum[prefixSum.length - 1];
}
return dp[pos] + (prefixSum[prefixSum.length - 1] - prefixSum[pos + 1]);
}
}[100581. Lexicographically Smallest Generated String] (https://leetcode.cn/contest/weekly-contest-439/problems/lexicographically-smallest-generated-string/)
给你两个字符串，str1 和 str2，其长度分别为 n 和 m 。
如果一个长度为 n + m - 1 的字符串 word 的每个下标 0 <= i <= n - 1 都满足以下条件，则称其由 str1 和 str2 生成：
- 如果 str1[i] == 'T'，则长度为 m 的 子字符串（从下标 i 开始）与 str2 相等，即 word[i..(i + m - 1)] == str2。
- 如果 str1[i] == 'F'，则长度为 m 的 子字符串（从下标 i 开始）与 str2 不相等，即 word[i..(i + m - 1)] != str2。
返回可以由 str1 和 str2 生成 的 字典序最小 的字符串。如果不存在满足条件的字符串，返回空字符串 ""。
如果字符串 a 在第一个不同字符的位置上比字符串 b 的对应字符在字母表中更靠前，则称字符串 a 的 字典序 小于 字符串 b。
如果前 min(a.length, b.length) 个字符都相同，则较短的字符串字典序更小。
子字符串 是字符串中的一个连续、非空 的字符序列。
测试样例：
输入：str1 = "TFTF", str2 = "ab"
输出："ababa"
解释: 这题脑筋急转弯，其实不太难。我们首先生成一个都是'a'的字符串。首先处理T的位置。因为m只有500，可以暴力计算，看所有T的位置是否可以满足。其次我们遍历F的位置。寻找第一个可以修改的位置。之前我们的字符串都赋'a'了，其实就是字典许最小了。这种情况下，尝试变不同，只需要把a变成b就行了。
class Solution {
public String generateString(String str1, String str2) {
int n = str1.length(), m = str2.length();
int L = n + m - 1;
char[] word = new char[L];
Arrays.fill(word, 'a');
boolean[] forced = new boolean[L];
for (int i = 0; i < n; i++) {
if (str1.charAt(i) == 'T') {
if (i + m - 1 >= L) return "";
for (int j = 0; j < m; j++) {
int pos = i + j;
char c = str2.charAt(j);
if (forced[pos]) {
if (word[pos] != c) return "";
} else {
word[pos] = c;
forced[pos] = true;
}
}
}
}
for (int i = 0; i < n; i++) {
if (str1.charAt(i) == 'F') {
boolean valid = false;
for (int j = 0; j < m; j++) {
if (word[i + j] != str2.charAt(j)) {
valid = true;
break;
}
}
if (!valid) {
int posToChange = -1;
for (int j = m - 1; j >= 0; j--) {
int pos = i + j;
if (!forced[pos]) {
posToChange = pos;
break;
}
}
if (posToChange == -1) return "";
word[posToChange] = 'b';
}
}
}
return new String(word);
}
}