60天带你刷完Leetcode【第7天】616-607

刷题连载来到第7⃣️天，小编收到了一些反馈，其中有些是对刷题的质疑。诚然刷题相对于做项目搞研究可以说是浪费时间的，因为任何工作的内容都不会是做题。但小编想说：做题目是思维的体操，而思维是贯彻落实在学习工作的各方各面的。可能刷题这个名字和刷题所能带来的利益让做题目本身显得急功近利，但如果刷题时的出发点是做思维实验，那么目的就会变得纯粹，过程也会更加单纯美好🍻。

题目：

给出一个string和一个需要被加粗的词的list，给出加粗后的string，比如；"abcxyz123"根据["abc","123"]加粗后得到"abcxyz123"注意加粗的部分可以互相overlap，比如"aaabbcc"根据["aaa","aab","bc"]加粗后得到"aaabbcc"

题解：

这个题目有意思在于拆解成subtask，再逐个优化的思路。这题分两步：第一步在string里找到需要标记的词，第二步把有overlap的词merge起来。优化第一步可以是对每个需要加粗的词在string里找长度一样的substring，而不是找出所有string里可能的substring再对照list看需不需要加粗。这样可以把running time从O(n^3)减少到O(nlw)，n是string长度，l是list长度，w是list中word平均长度。第二步是常规的merge interval，在写法上可以方便一些：merge index而不是直接merge需要被bold的word。

615

题目： 给出两张表salary和employee分别如下：

要求找出每个月的各department平均工资相比于当月平均工资是高了还是低了。

输出如下：

题解：

厘清题意之后，其实就是做两个table，一个记录每个月department的平均工资，一个记录每个月整体的平均工资，再把两张表join起来并比较工资高低即可。

614。

题目： 给出一张表记录了follower和followee，求2nd degree follower的数量，即follower的follower的数量。例子如下：

题解：

可以选出在follower列里的followee，即有follower的follower，再count有多少follower，最后选出followee为folower。也可以用join相关的办法。

613。

题目： 给出一维空间上的点，求最短的点之间的距离。

题解：

一维空间点的距离即为坐标差。直接做cross join再做差即可。但是这题的follow-up比较有趣：如果这些点已经按照从小到大排列过了，如何求解？这里多了一个条件是想要寻求不需要join的解法。既然点已经从小到大排列好，那么最小的距离一定在相邻点之间产生。按照sql一行行loop rows的机制，我们需要的是一个user-defined variable去keep上一行row的值，这样用当前点的值减去上一行点的值即相邻点之间的距离。进一步可以利用这个trick给出原题的最优解，即先sort一遍以避免使用join。这个方法beat了99.71%的submission。具体代码如下：

# Initialize the prev variable to a big negative number so that the first value of difference will never get selected
set @prev := -100000000;
select min(diff) as shortest
from (select (x - @prev) as diff, @prev := x
 from (select * from point order by x) t
 ) tt
;

612。

题目： 给出二维空间上的点，求最短的点之间的距离。

题解：

类似上一题， 但是没法sort、避免join。

611。

题目： 给出一串数字，求出其中三个数字作为边长组合可以组成三角形的方案数。

题解：

成为三角形要求最短的两边之和也大于第三边，这让人想到了3sum。这里可以拿出一个数字，然后在剩下的数字里面拿出两个，并比较这三个数字是否可以组成三角形。为使所有三个数字的组合只访问一遍，可以每次拿出一个数并仅从比这个数大或小的剩余数字中取两个数。为方便比较，可以使拿出的一个数字为三个数字中最大的数，即每次拿出一个数并仅从比这个数小的剩余数字中取两个数。以这个loop strategy走一遍并在剩余数字上使用用two pointer就可以确定有多少个方案。这个strategy实际上还带来了更多优化：如果剩下的数字中，left right指向的数已经大于拿出来的那个数，那么两个指针中间的数加起来都会大于拿出来的拿个数，因此有right-left种方案可以成为三角形，可以直接right-1并继续check。running time: O(n)