leetcode 第 437 场算法比赛

背景

连续一个月没打比赛了，恢复打比赛状态不好。
第三题没想明白，第四题比较简单，但是没去做。

A: 统计
B: 贪心
C: 栈+并查集+线段树
D: 动态规划

排名：200+，先做第四题可以进入前百名
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest

一、找出长度为 K 的特殊子字符串

题意：给一个字符串，问是否存在长度为k的特殊子串。
特殊子串：自身全部字符都相等，且前后相邻的字符不能与自身相等。

思路：统计连续相等的字符长度，判断是否等于 k。

二、吃披萨

题意：给一个数组，每天选择四个数字，奇数天代价是最大数字，偶数天代价是次大数字，求累计最大代价。

思路：贪心。

PS：比赛的时候看错题了，看出累计最小代价了，不过后来发现最大最小的贪心思路是一样的。

分析：每天选择 4 个数字，显然共有 n/4天，且有 a 个奇数天， b 个偶数天。

很容易想到，最大数字放在奇数天，这天剩余的三个数字显然需要选择最小的三个数字。

那是否存在一种方案，最大数字在偶数天，答案更优呢？
可以反证法证明，不存在。

证明：假设存在一种方案，最大值在偶数天，方案更优。
不妨设方案为 a1, a2, a3, a4 和 b1, b2, b3, b4，且 a4<b4。
此时答案为 a4 + b3。
如果我们交换 a4 与 b4，则答案为 b4 + b3。
由于 a4<b4，所以我们构造出一个更大的答案，假设不成立，所以最大值肯定在奇数天。
证明完毕。

扩展这个贪心，则是最大的 a 个数都在奇数天，然后补充 3a 个最小的数字。

剩余的数字都放在偶数天，显然也可以证明，每天选择两个最大的数字和最小的数字是最优的。
证明与上面类似，也是反正法，这里就不再证明了。

结论：对数组排序，奇数天选择1个最大值与3个最小值，偶数天选择2个最大值和2个最小值。

三、选择 K 个互不重叠的特殊子字符串

题意：给一个字符串，问是否可以选择 k 个互不重叠的特殊子串。

特殊子串定义：如果一个字符出现在子串中，则所有子串都需要出现在子串中。

思路：栈+并查集+线段树

第一步很容易想到，需要预处理出所有的特殊子串区间。
第二步使用动态规划计算可以选择多少个子串，是否大于 k。

假设已经构造出第一步，第二步思路如下。

首先对子串区间按左边界排序，较大的左边界在前面，这样就是从后到前遍历区间了。

状态转移方程如下：

状态定义：f(i) 以 i 为起始位置匹配一个子串时，可以匹配的最多子串个数。
状态定义：F(i) 以 i 为起始位置可以匹配的最多子串个数。

f(i) = max(f(i), 1 + F(r+1));
F(i) = max(f(i), f(i+1), ..., f(n));

对于 F(i) 函数，可以使用线段树来区间求最值。

for (auto [l, r] : nums) {
  int nowAns = segTree.QueryMax(l, l);
  int newAns = 1 + segTree.QueryMax(r + 1, nn);
  if (newAns > nowAns) {
    segTree.UpdateMax(l, l, newAns);
  }
}

当然，其实也可以在循环时，根据下个位置的值，计算出当前位置的值。

vector<int> maxVal(nn, 0);
int R = n + 1;
for (auto [l, r] : nums) {
  while (l < R) {
    R--;
    maxVal[R] = max(maxVal[R], maxVal[R + 1]);
  }
  maxVal[R] = max(maxVal[R], 1 + maxVal[r + 1]);
}

那该如何计算出所有的特殊子串呢？

方法1：暴力枚举。

什么时候两个字符需要合并呢？
答案是有交集的时候，例如：abab。

所以，我们可以不断的循环，判断是否存在两个字符存在交集。

while(1){
  if(!ExistAndMerge()){
    break;
  }
}

怎么判断存在交集呢？
显然，不能使用左右边界判断，因为可能存在反例，例如 ababa。
所以我们需要使用集合，来判断区间内是否存在，区间外是否存在，都存在时，就代表存在交集。

一种简单的方法是前缀统计法，即枚举所有前缀各字符出现的次数。
然后通过前缀差，就可以判断区间内字符是否存在了。

方法2：单调栈。

交集区间合并常见的方法就是单调栈。

不过这道题的交集定义不太一样。
分析区间存在交集情况，发现有两种。

情况1：边界交集，例如 abab，即两个区间不是包含关系，有明显的交集。
情况2：包含交集，例如 ababa，即一个区间包含另一个区间，但是内部的小区间又有大区间的字符。

单调栈合并时判断这两种情况即可。
单调栈比较复杂，这里就不再展开介绍了。

四、最长 V 形对角线段的长度

题意：给一个矩阵，需要从1开始走，之后走过的方格值需要是交替的 2与0，最多顺时针90度转向一次，问最多可以走多少个方格。

思路：经典的动态规划。

状态定义：f(x,y,dir,flag,step)
含义：在左边(x,y) 方向为 dir，转向次数为flag，步长为step时，之后可以走的步数。

状态转移方程：

f(x,y,dir,flag,step) = max(
  f(X,Y,dir,flag,step+1),      // 直线走
  f(X,Y,(1+dir)%4,flag+1,step) // 转向
)

然后枚举所有起始位置的四个方向，求最大值。

五、最后

这个比赛顺序出的不好，第三题和第四题难度是反的，第三题属于综合性比较难的题，涉及复杂的区间合并与双方程动态规划、而第四题则是最简单的动态规划。

以后做题还是四道题都先读一下吧，否则就会像这次，第四题很简单但是没去做，第三题区间合并卡了好久。

《完》

-EOF-

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