讨论/题目交流/🏆 第 159 场力扣周赛/
🏆 第 159 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

缀点成线
删除子文件夹
替换子串得到平衡字符串
规划兼职工作

展开讨论
力扣 (LeetCode)发起于 2019-10-20
最近编辑于 2019-10-20

白天有点事,晚上补的题目。先上总结:本次周赛除了hard是陈题以外,其他的质量都很高,推荐:

  • 缀点成线
    判断每个点到第一个点的斜率是否相同即可,需要注意横线和竖线的情况。时间复杂度 O(n)O(n)

  • 删除子文件夹
    这道题乍一看有一个直接的反应是 trie 树,用 trie 树也确实是正解。但是这道题有复杂度稍高但是代码量更少的做法。如果我们把所有字符串排序,会看到类似下面的场景:

    /a
    /a/b
    /a/bc/c
    /a/bc/d

    其实排序字符串以后,根目录必然会在子目录上面,而且和子目录是连着的。所以,开始的时候,我们以第一个目录作为我们的根目录,对于后续的每一个目录,判断根目录是否是他的根目录。如果是,那么就跳过这个文件夹,否则我们更新根目录为当前目录。

    做法时间复杂度的瓶颈在于排序字符串,为 O(nmlog(n))O(nmlog(n))nn 为字符串的数量,mm 为字符串的长度,不同于数字排序,字符串之间的比较也是有代价的,计算复杂度的时候也需要考虑进去。

    而如果使用 trie 树的话,我们可以把 log(n)log(n) 部分优化掉,复杂度为 O(nm)O(nm)

  • 替换子串得到平衡字符串
    应该是本场最好的题目,题目让我们替换最小的子串,换句话说就是保留最长的串,使得所有字母的数量不大于 n/4n/4,这里之所以说串而不是子串了,是因为我们保留的串是有可能左右各一半的。

    使用双指针,开头分别指向字符串的头和尾,我们先把左指针尽量右移,使得所有字母的数量不大于 n/4n/4,然后开始右移右指针,同样使用到的字母总数不大于 n/4n/4,最后记录现在的使用的字符串长度。

    然后我们每次把左指针往回移动一个,那么右指针也可以继续向左试探,记录现在的情况下的最大字符串长度。
    最后我们遍历完所有的情况,就可以得到最后的结果了。时间复杂度为 O(n)O(n)

  • 规划兼职工作
    非常老的题目了,甚至都怀疑是不是可以在前面的题目里找到一模一样的原题。做法也很经典:首先把所有范围为 10910^9 的坐标都离散化为从 [1,n][1,n] 的点,由于总共就 55 万的区间,所以 nn 是小于 1010 万的。那么对于每个任务,也可以转变为 [start,end,profit][start,end,profit] 的三元组。对于每个三元组,我们把这个任务记录在 endend 上,具体做法是用一个dict记录每一个时间上的所有任务。

    做好预处理以后,剩下的工作就是 dp 了, dp[i]dp[i] 表示从 0i0-i 时刻,做任务能拿到的最大价值,那么首先 dp[i]>=dp[i1]dp[i]>=dp[i-1]。接着,如果 i 时刻有任务结束的话(我们记录在dict里了),dp[i]=max(dp[i],dp[start]+profit)dp[i] = max(dp[i],dp[start]+profit) ,会有这样的转移。最后在dp数组里取max就是结果了。总体复杂度是 nlog(n)nlog(n),也就是瓶颈在离散化的排序上。

细节和代码等后面的详细题解吧。

6
展开全部 16 讨论