leetcode 第 389 场算法比赛

零、背景

今天比赛最后一题是三分+二分，代码量比较大，比赛期间没通过，赛后才调试通过。

A: 枚举判断逆向子串是否在子串里。
B: 数学计算。
C: 枚举下边界，二分找到上边界，计算出答案。
D: 枚举索引位置，三分左边界找到最优答案。

比赛排名：最后一题做出来时公布。
比赛代码：https://github.com/tiankonguse/leetcode-solutions/tree/master/contest

一、字符串及其反转中是否存在同一子字符串

题意：问是否存在长度为2的子串，反转后，依旧是子串。

思路：枚举所有长度为2的子串，反转，判断是否是子串。

二、统计以给定字符开头和结尾的子字符串总数

题意：问以字母 c 为收尾字符的子串的个数。

思路：数学计算题。

统计字母 c 的个数 num。
如果子串长度为 1， 则有 num 个。
如果子串的长度大于 1，则是 num 个字母里挑选两个当做收尾，即 C(num, 2)。

三、成为 K 特殊字符串需要删除的最少字符数

题意：问最少删除多少个字符，使得任意两个字符的频率之差不超过 k。

思路：枚举+二分。

可以发现，至于统计的字符个数有关系，与字符自身没有关系。
所以需要先统计字符的个数，并对个数进行排序。

之后枚举最终答案的最小频次 l ，最大频次则为 l+k。
小于最小频次的字符，都需要删除。
大于最大频次的字符，都需要删除与最大频次保持一致。

上面两个都可以通过前缀和来计算得到。

复杂度：O(n log(n))

四、拾起 K 个 1 需要的最少行动次数

题意：给一个 01 数组，任意选择一个坐标当做索引位置，问至少多少代价，才能捡起 k 个 1。

操作0：将索引位置的值捡起，代价为0。
操作1：将某个位置(非索引位置)的值设置为 1，代价为 1，至多 X 次。
操作2：交换相邻两个位置的值，代价为 1，无限制次数。

思路：需要先枚举索引位置，然后判断当前位置的最优答案。

显然，如果选择操作1，必然是操作索引相邻的位置，这样答案会更优。
故可以优先判断尽量的选择操作1，操作2只交换索引的相邻位置，是否可以得到答案。
如果可以，就是当前索引位置的最优答案。

如果操作 1 用完了，还没答案，则需要再离索引较远的位置选择一些 1，通过操作 2 慢慢移动到索引位置。
操作 1 每用一次，就可以创造出一个1，结合一次操作2，就可以捡起一个1.

对于剩余的 1，不妨设为 K 个， 需要通过操作2 从原数组移动到索引位置。
显然，要移动的 K 个 1 是连续的。
通过观察 K 个 1 的左边界与答案的关系，可以发现是先降低再增加。
这种曲线需要使用三分来找到最优答案。

左边界确定后，也可以通过二分查找，确定右边界。
之后就与第三题一样，通过下标偏移量的前缀和来计算出移动的距离和。

复杂度：O(n log(n) log(n))

五、最后

这次比赛最后两道题很类似。
第三题直接二分找左右边界，然后前缀和计算答案。
第四题先三分确定左边界，二分找到右边界，再通过前缀和计算答案。

年前比赛暂停了一个月，最近最后一题都会做，不过比赛的时候好像时间不够了。
分析原因，最后一题只是大概想了算法就开始敲代码，对于细节是敲代码的时候再确定的，这就导致有写细节被遗漏，从而代码样例不通过。
以后打算先在草稿上推导出完整的算法伪代码，再开始敲代码。

《完》

-EOF-

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