leetcode 第 271 场算法比赛

零、背景

题目比较简单，本来打算半个小时写完的，结果一个小时也没写完，差点翻车。

一、环和杆

题意：给 10 个棍子和 3 个颜色的环，棍子上有环。
问哪些棍子上有三种颜色的环。

思路：循环统计即可。

二、子数组范围和

题意：给一个数组，求所有子数组中最大值与最小值的差值之和。

思路：数据量不大，枚举所有子数组，前缀相同的子数组累计计算最值即可。
复杂度：O(n^2)

三、给植物浇水 II

题意：给一排植物，两个人分别从两头顺序给植物浇水。
如果谁的水桶的水不够给当前植物浇水了，则立刻加满水。
问最后两人总共加了多少次水。

思路：从两头循环模拟即可。

四、摘水果

题意：在一个 x 轴上，给一些下标和水果数量，代表指定下标位置上有若干个水果。
现在给你一个起始下标和最大距离，问在可以向左和向右移动的时候，最多可以摘多少水果。

思路：典型的二分查找题。

总共有两种局部最优策略来摘水果。
一种是先往左走，到达某个位置后再向右走。
另一种是先向右走，到达某个位置后再向左走。

枚举这两种策略，取最优值即可。

这里以第一个策略为例来说明具体怎么二分搜索。

首先枚举的都是输入的下标，这样顶多枚举 O(n)次。
然后判断枚举的位置是否能到达，不能则没必要继续枚举了。
可以到达时，使用前缀和可以得到一个临时答案。
此时假设左半部的距离是 L。

之后再判断是否可以到原点。
判断公式是 2 * L < K，复杂度 O(1)。

如果可以了，就可以尝试向右走，去继续摘水果了。

右边最远可以走的距离是 start + K - 2 * K。
有了最远的距离，进行二分搜索找到具体的下标。
然后使用前缀和计算出一个更大的临时答案。

最后更新最优解即可。

PS：做这道题的时候，我在纠结要不要把二分搜索从数组转化为 map。
由于 map 的 distance 是 O(N) 的复杂度，最后我最好选择数组了。

五、最后

这次比赛难度还好。
不过我翻车了。

最后一题卡了好久，虽然四道题都做完了，但是排名很靠后了。

《完》

-EOF-

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