leetcode 第 352 场算法比赛

零、背景

这次比赛第三题不知为啥，线段树被卡常数了，最后不断简化线段树模板，超时 6 次最后才通过。

一、最长奇偶子数组

题意：给一个数组，求这一个最长子数组，满足第一个元素是偶数，之后所有值就交替，且最大值不超过指定值。

思路1：枚举。
枚举子数组起始位置，求满足条件的最长长度，最后取最大值。
复杂度：O(n^2)

思路2：贪心。
按最大值为分割线将数组分隔为若干子数组，之后求每段子数组中的最长奇偶交替的子数组。
复杂度：O(n)

二、和等于目标值的质数对

题意：寻找所有的质数二元组，他们之和等于 n ，且第一个质数不大于第二个质数。

思路：枚举。
枚举所有小于 n 的质数，求差判断差值是否是质数，是了且满足大小关系，就找到一个答案。

三、不间断子数组

题意：给一个数组，如果一个子数组的任意两个元素的差值都在2之内，则称为不间断子数组。
求不间断子数组的个数。

分析：对于一个不间断子数组，其所有前缀肯定都是不间断子数组。
所以对于一个起始位置，我们只需要找到最长的不间断子数组即可。

思路：枚举起始位置，然后二分找到最长的不间断子数组。
二分时，需要求数组指定区间的最大值与最小值，这个可以使用线段树来查询。
复杂度：O(n log(n))

PS：我使用线段树模板竟然超时了。
于是各种常数优化，最后没改变逻辑的情况下，把模板的无关功能都删除，最后才通过。

赛后看其他的代码，发现标准解法是双指针，怪不得被卡常数呢。

四、所有子数组中不平衡数字之和

题意：给一个数组，排序后相邻元素之差大于1时称为不平衡数字。
求所有子数组的不平衡数字个数之和。

思路：枚举所有子数组。
对于相同其实位置的子数组，可以复用上一个子数组的答案。
新插入一个元素后，更新当前前缀不平衡数字的个数，求和即可。

具体来说，新插入一个元素后，我们需要判断不平衡数字时是否新增或者减少。

这里分为几种情况。
1）插入的是重复数字，不平衡数字不变。
2）插入的是第一个数组，不平衡数字不变。
3）插入的是最大值，则与次大值比较，是否可以新增一个不平衡数字。
4）插入的是最小值，则与次小值比较，是否可以新增一个不平衡数字。
3）否则，插入的是中间值，左右的值之前组成了一个不平衡数字。这里判断新的值与左右的关系，从而可以判断是新增或减少不平衡数字。

复杂度：O(n^2 * f(n))

f(n) 的复杂度依赖于我们如何统计不平衡数字。

如果使用 map，复杂度就是 O(log(n))。
如果使用 hash，复杂度就是 O(1)

五、最后

这次比赛我第三题浪费了很长的时间，超时了 6 次，是自己想复杂了，直接用线段树来做，没用双指针来做。

《完》

-EOF-

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