leetcode 第 336 场算法比赛

零、背景

这次比赛前三题用时 11 分钟做完的。
第四题我的思路是线段树加二分，做的慢了点，通过时排两百多名，应该有更简单的方法吧。

比赛源码： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/3/336

一、统计范围内的元音字符串数

题意：给一个字符串数组，问有多少个字符串收尾字符都是元音。

思路：循环判断即可。

小技巧：元音字符放在 set 容器中，查找即可。

PS：看到 left 和 right，我一度没看懂题，看了好几边才确认题意。

二、重排数组以得到最大前缀分数

题意：给一个数组，可以打乱为任意顺序的数组，问如何打乱，才能是前缀和大于0 的个数最多。

思路：前缀和大于 0 个数最多，显然是正整数放前面，负数放后面，越小的负数需要越往后放。

结论：从大到小排序，统计前缀即可。

三、统计美丽子数组数目

题意：给一个数组，问有多少个美丽子数组。
定义：每次可以选择两个数字，二进制某一位都是1时可以都消为0，如果最终子数组都变为0，则为美丽子数组。

思路：美丽子数组的定义其实就是判断数组的异或值，结果为 0 是，非 0 不是。
所以问题转化为了，有多少个子数组的异或值是 0。

暴力计算复杂度是O(n^2)，显然会超时。

不过对于统计满足要求的子数组个数的题型，策略都是计算当前的前缀值，然后判断与之前的前缀值求差，看有多少满足要求。

以区间和为例，sum[1,a] - sum[1,b] 就是 sum[b,a]。
a 和 sum[b,a] 是输入，求有多少个 b 满足要求。

公式可以转化为 sum[1,a]-sum[b,a]，问题就转化为了有多少前缀和 sum[1,b] 满足要求。

异或值类似，可以转化为了统计满足要求的前缀个数。

使用 hash 统计前缀的个数，复杂度O(n)

四、完成所有任务的最少时间

题意：有若干任务，需要在时间区间 [b,e] 内运行 d 秒。
电脑同一时间可以运行无数个任务，问电脑至少运行几秒才能运行到所有任务。

思路：电脑运行任务，很经典的问题，解决方法有很多。

我的思路是贪心，即优先按结束时间向前倒退若干秒，电脑按这个时间运行即可。

要保证贪心的正确性，任务需要先按结束时间从小到大排序。

证明：假设前面的任务已经运行了，对于当前任务，肯定运行的越晚越好，这样时间才能与后面的任务复用时间。

由于前面的任务已经运行了，会与当前任务复用一些时间，所以当前任务结束时间向前倒推时无法直接计算出来。

这里就需要使用一个数据结构和一个算法。
一个数据结构：线段树，用于统计区间内复用了多少时间。
一个算法：二分，找到任务结束时间倒推的边界，倒推的时间区间都需要运行任务，之前的都是复用时间。

PS1：我的线段树模板修改操作是区间都加一个值，而当前问题是复用，所以我浪费不少时间来修改线段树模板。

PS2：二分的时候，有个地方写错了，本来应该写任务区间内的复用时间，我写成二分区间内的复用时间，错误一次。

五、最后

这次比赛的最后一次，我感觉至少有三四种不同的做法。

你都是怎么做的呢？

比赛结束后，我有研究下都有啥解法，放到评论中吧。

第一名：线段树+二分，O(n*log(n)^2) 第二名：暴力循环，O(n^2)
第三名：暴力循环，O(n^2)
第四名：暴力循环，O(n^2)
第五名：区间合并优化，O(n^2)

《完》

-EOF-

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