leetcode 第 416 场算法比赛

零、背景

这次比赛比较简单，拼手速的时候到了。

A: 字符串统计。
B: 二分。
C: 滑动窗口。
D: 滑动窗口。

排名：200+
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/416

一、举报垃圾信息

题意：给一个字符串数组，如果至少存在两个字符串在黑名单字符串中出现，则称为垃圾数组。
问是否是垃圾数组。

思路：黑名单储存为 hash 表，统计有多少个在黑名单中即可。

二、移山所需的最少秒数

题意：n 个工人同时开挖一个山，告诉你每个工人挖山的效率，问最少需要多少时间才能把山挖空。
工人效率定义：挖 x 单位的山，需要 T=t+2t+3t+...+xt时间。

思路：二分。

二分答案时间，计算时间内每个工人可以挖的山的高度，看累计起来是否可以把山挖空。

对于一个工人，时间T确定了，可以列出一个一元二次方程，解方程即可计算出山的高度x。
复杂度：O(n log(n))

如果你不想解一元二次方程，则可以使用二分去求解找到答案。
复杂度：O(n log(n) log(n))

三、统计重新排列后包含另一个字符串的子字符串数目 I

题意：给一个字符串，问有多少子串重排列后是指定字符串的前缀。

思路：滑动窗口。

先一个字符串重新排列后是另一个字符串的前缀的判断方法。
由于第一个字符串可以重新排列，这说明统计两个子串的字符，第二个字符串的字符在第一个字符串里都出现，则一定满足要求。

由此这道题可以转化为：有多少子串的字符可以拼出指定字符串。
对于子串的字符串统计问题，很容易想到滑动窗口。

固定左边的起始位置，找到第一个右边界，使得这个子串满足要求，显然所有后缀也都是满足的。
固定的左边位置右移一次后，可以复用上一次的右边界。
如果右边界不满足要求，继续右移即可。

可以证明，复杂度为O(n)

四、统计重新排列后包含另一个字符串的子字符串数目 II

题意：给一个字符串，问有多少子串重排列后是指定字符串的前缀。

思路：与第三题一样，没区别。

五、最后

这次比赛题目设计的很失败。

滑动窗口作为 leetcode 入门做的第一个算法，几乎所有人都会这个算法。

第三题，没有任何特殊变形直接出了一个赤裸裸的滑动窗口的题目。
第四题的数据范围也可第三题一摸一样，第三题通过后，第四题自然可以通过。

《完》

-EOF-

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