leetcode 第 325 场算法比赛

零、背景

不知道是不是确诊后变笨了，这次比赛题目我做的很慢，比赛期间没做完。

一、到目标字符串的最短距离

题意：给一个字符串数组和起始位置，可以双向遍历，问最近的与查询字符串相等的距离。

思路1：枚举所有相等的字符串，然后计算出两个方向的距离，取最小值即可。

思路2：枚举两个方向，查找即可。

二、每种字符至少取 K 个

题意：给一个字符串，问取前缀与取后缀后，是否可以使得每个字符都至少有 k 个，求前后缀长度最小和。

思路：预处理后缀和，枚举前缀，二分后缀。

PS：比赛的时候，我一直想复用 STL 的 lower_bound，编写比较函数纠结了好久。
最终还是手写二分通过了。

注意事项：如果前缀已经满足答案，就不需要去二分后缀了。

三、礼盒的最大甜蜜度

题意：给一个数组，问怎样选k个数字，才能使得 k 个数字的最小绝对值最大。

思路：最小值的最大值，二分答案即可。

细节：先对数字排序，检查答案是否满足时，根据第一个数字计算出下个最小的数字，然后再使用二分查找第一个大于等于的位置，循环找 k 个即可。

小技巧：第二个二分可以使用lower_bound。

四、好分区的数目

题意：给一个数组，问是否可以分为两个子序列，使得两个子序列和都大于等于 k，求满足要求的划分数。

思路1：总划分数是 2^n个，先求不满足的，相减就是满足的。

如果整个数组和小于 2*k，那显然没有答案。
其他情况，不满足的肯定是一个子序列小于k，一个不小于 k。
k 数据范围只有 1000， 可以通过动态规划计算出子序列和为 [0,k]的子序列个数。

状态：dp[i][j] 前 i 个元素子序列和为 j 的子序列个数。
第 i+1 个元素根据选择与不选择，更新状态即可。
复杂度：O(n^2)

小技巧：可以通过逆序计算，把二维数组转化为一维数组。

思路2：分类动态规划。

前 i 个元素的状态定义：

状态1：dp1[i][] 第一个子序列和不大于 k 时的子序列个数。
状态2：dp2[i][] 第一个子序列和大于等于k但第二个不大于k时的子序列个数。
状态3：dp3[i] 两个子序列和都大于等于k时的个数。

转移方程：

状态1可以转向状态1或者状态2或状态3。
状态2可以转向状态2或者状态3。
状态3可以转向状态3。

对于状态3，由于以满足答案，所以新来的元素不管选择哪个子序列，都满足答案，所以答案翻倍。

对于状态2，如果选择子序列1，更新自己的状态。
如果选择子序列2，子序列2的和大于等于k，则更新状态3，否则更新自己。

对于状态1最复杂。
如果选择子序列2，则当前状态不变。
如果选择子序列1，子序列和不大于k时，更新自身状态。
子序列和大于等于k时，需要根据前缀和判断子序列2的和，也大于等于k了，直接进入状态3，否则进入状态2。

复杂度：O(n^2)

对比下，第一个方法只需要一个简单的普通动态规划即可解决，而第二个方法则维护了三个状态，状态内部可以转化，转态间也可以转化，变得相当复杂。

四、最后

这次比赛第二个为了复用 STL 折腾了好久，以后二分如果需要写比较函数，那就自己实现二分查找吧，太浪费时间了。

加油，算法人。

《完》

-EOF-

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