leetcode 第 379 场算法比赛，差点进前30名

零、背景

2024 年的第一场比赛，有点坑人，差点进入前 30 名。

A: 签到题，寻找最大值。
B: 棋盘判断，情况分析、递归，枚举都可以。
C: 数据结构题。
D: 动态规划。

一、对角线最长的矩形的面积

题意：给一些矩阵，求矩阵对角线最长的矩阵，如果对角线相等，返回面积最大的矩阵。

思路：记录当前最大的对角线和面积，按题意循环比较即可。

小技巧：可以记录面积的平方，从而避免记录带有小数的对角线。

二、捕获黑皇后需要的最少移动次数

题意：有一个8*8的国际象棋棋盘，给你三个棋子的坐标，一个白色的车，一个白色的象，一个黑色的皇后，问只移动白色棋子，最少多少步可以杀死黑色皇后。
规则1：车可以上下左右走直线，但不能跳过其他棋子。
规则2：象可以走45度的斜线，但不能跳过其他棋子。

方法1：深度优先记忆化搜索。

定义一个map[x0][y0][x1][y1] 的状态，代表两个白色棋子的位置，搜索判断两个棋子走所有可能得步骤，求出最优值。

关键点：如何避免死循环。
一个方法：默认所有状态标记未计算，当开始计算时，先标记当前状态答案为无穷大。由此可以避免形成环。

时间复杂度：O(4 * 8* 8^4)
解释：状态有8^4个，状态转移两个棋子可移动的线有 2 条，每条最多移动 8 格。

方法2：分类讨论。

不考虑障碍物，如果一步无法杀死皇后，车至少两步就可以到达皇后的位置。
有障碍物之后一个，故答案是最多两步可以杀死皇后。

那什么皇后可以一步杀死皇后呢？
皇后恰好在车或象一步行动方向的直线上，且中间没有障碍物。

如果中间有障碍物，第一步障碍物先移动走，第二步就满足一步杀死皇后了。

综合上面的三类情况，可以判断一步可以杀死皇后时，答案是一步，否则答案是两步。

我们可以分情况分析三个棋子的位置情况，计算答案。

不过三个棋子的相对情况非常多，手动分类讨论会死人的。

方法3：枚举。

通过枚举一步可以到达的坐标，判断是否有答案即可。
复杂度：O(32)

三、移除后集合的最多元素数

题意：给两个集合，问分别从两个集合中选 k 个数字，如何才能使得选的数字组成的新集合大小最大。

思路：两个集合优先选择各自的差集，最后不够了再从交集中取即可。

四、执行操作后的最大分割数量

题意：给一个字符串，每次需要删除一个集合大小为 k 的前缀，删除次数称为最大分割数。
现在可以修改字符串的一个字符，问如何修改才能使得最大分隔数更大。

思路：分类讨论的动态规划。

假设状态是 dp[N][flag] 代表后 N 个字符在是否使用修改的情况下的最优值。

如果不使用修改次数，则状态转移方程固定为：

next_N = last_set_count(N, k);
dp[N][flag] = max(dp[N][flag], 1 + dp[next_N][flag]);

last_set_count 的含义是查找从下标 N 开始，向后查找最大的集合，使得集合的大小为 k，返回下一个坐标。

如果 k 不等于 26，而且 flag 为可以修改，则修改的状态方程需要分情况讨论

首先找到第 k 个不同元素的首次出现的位置。

next_N = last_set_count(N, k-1) + 1;

情况1：前面有重复数字，可以修改一个重复的数字，从而使得当前位置的值是第 k+1 个不同数字。

if(next_N - N > k){
  dp[N][0] = max(dp[N][0], 1 + dp[next_N - 1][1]);
}

情况2：下个数字与前缀集合有重复数字，可以修改前缀的重复数字，使得当前位置满足last_set_count。

dp[N][0] = max(dp[N][0], 1 + dp[next_N][1]);

情况3：下个数字与前缀集合有重复数字，可以修改下个数字，使得当前位置满足last_set_count。

for (int i = 0; i < 26; i++) {
  if (has(pre, i)) continue;
  const char oldChar = s[next_N];
  s[next_N] = 'a' + i; // 保存值
  dp[N][0] = max(dp[N][0], 1 + dp[next_N][1]);
  s[next_N] = oldChar; // 恢复值
}

三种情况结合起来，就是完整的动态转移方程。

五、最后

这次比赛最后一题确实有难度，需要分情况写动态规划，比赛的时候只有 30 人做出来了。
我第二题花费了太多时间，做第四题时时间不够，做出来后比赛已经结束十分钟了。

《完》

-EOF-

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