Leetcode 第 159 场比赛回顾

作者: | 更新日期:

滑动窗口实际就是贪心,有时候不容易证明。

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/vc-QsIJ7rcst_Ch1EG5R2A

零、背景

这次比赛题型和往常一样,涉及简单几何计算、简单排序、滑动窗口、动态规划。

今天突然发现,滑动窗口最优值问题其实就是贪心,而这个贪心需要能够证明其正确性。
我没想明白,浪费了不少时间。
最后剩余十五分钟的时候,只好放弃这道题,先把最后一道动态规划题做了。

赛后想到使用二分解决最优值问题,敲了之后就通过了。
然后见有人使用滑动窗口,便又想了想,发现确实是正确的。

下面就来分别看看这四道题吧。

一、是否在一条直线上

题意:给 n 个点,问是否在一条直线上。

思路:两点确定一条直线, 所以循环判断后面的点是否在前两个点组成的直线上。

二、找父路径

题意:给一些目录路径,求所有没有父路径的路径。

思路:最容易想到的思路是字典树。
如果你看过我以前的题解的话,就知道我曾使用两层二分操作排序数组来模拟字典树。
所以排序的数组和字典树是等价的,只不过查找麻烦一些。

这道题只需要找父节点,使用排序数组就不麻烦了。
只需要不断找到一个父节点,向后遍历跳过所有儿子节点即可。

三、四字母平衡字符串

题意: 一个字符串里面只有四个字符。问是否可以修改一个子字符串,使得这个字符串里面的四个字母的个数相等。

思路:我猜想可以使用滑动窗口,但是这个方法算是贪心,是否正确不好证明。
所以我首先想到使用二分搜索答案,然后判断答案是否可行的方法。

对于一个答案,我们需要枚举所有可能的区间,然后根据前缀和后缀的统计来判断是否满足要求。
只有一种情况不满足要求:前缀和后缀里面有一个字符大于平均值。

复杂度(complexity):n log(n)

四、时间调度

题意:给一些时间区间以及区间的报酬,求挑选一些不冲突的区间,使得报酬最大。

思路:典型的动态规划题。

定义递归方程:dfs(time),含义是[0, time)时间内的最大报酬。

经典做法是按结束时间排序,然后有两个选择:
1、选择某个时间区间,然后递归求开始时间之前的最优值dfs(beginTime+1)
2、不选择这个时间,递归求结束时间之前的最优值dfs(endTime)

如果结束时间有相同的,依次假设选择对应的时间区间即可。

这里有一个问题:时间很大,报酬也很大,经典的方法存不下这么大的数据。
所以这里只能储存下标。

储存下标后有另外一个问题:需要根据一个时间,找到下标。
所以这里就需要二分查找,找到最后一个满足要求的时间区间的下标。

复杂度(complexity):n log(n)

五、最后

这次比赛的题还是有点难度的。

第二题虽说可以排序解决,但是使用了字典树的思想。
第三题找最优值,二分查找是一种不错的选择。滑动窗口不好理解,后面我会单独写一篇文章介绍。
第四题动态规划的方法很多,我使用的二分搜索,后面我也会单独写篇文章介绍另外一种更高端更常见的方法。

这样看来,leetcode 上有难度的题,一般就是二分查找与动态规划了。
感兴趣的可以重点学习一下这两个题型。

-EOF-

本文公众号:天空的代码世界
个人微信号:tiankonguse
QQ算法群:165531769(不止算法)
知识星球:不止算法

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面打开下面的地址进行留言。如果下面没有地址,可以关注公众号留言。
原文地址:https://mp.weixin.qq.com/s/vc-QsIJ7rcst_Ch1EG5R2A

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越