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

2017-09-28 CS学渣学酥小混混 北美加群小助手Jogchat 北美加群小助手Jogchat

刷题连载来到第7⃣️天,小编收到了一些反馈,其中有些是对刷题的质疑。诚然刷题相对于做项目搞研究可以说是浪费时间的,因为任何工作的内容都不会是做题。但小编想说第一,做题目是思维的体操,而思维是贯彻落实在学习工作的各方各面的。可能刷题这个名字和刷题所能带来的利益让做题目本身显得急功近利,但如果刷题时的出发点是做思维实验,那么目的就会变得纯粹,过程也会更加单纯美好🍻。第二,我们的文章注重思路,可能大家已经发现了,这些对题目的分析和解答就是面试的时候可以说给面试官的,我们也尽量不放code让大家更多的去体会思路而不是题目本身。从这期开始,这个特色将更加鲜明。谢谢大家的支持,欢迎各种形式的feedback👏!


616

题目:给出一个string和一个需要被加粗的词的list,给出加粗后的string,比如;"abcxyz123"根据["abc","123"]加粗后得到"<b>abc</b>xyz<b>123</b>"注意加粗的部分可以互相overlap,比如"aaabbcc"根据["aaa","aab","bc"]加粗后得到"<b>aaabbc</b>c"

题解:这个题目有意思在于拆解成subtask,再逐个优化的思路。这题分两步:第一步在string里找到需要标记的词,第二步把有overlap的词merge起来(看似很自然,但刷了一定量的题之后总是想着能不能用一些固有的方法一步到位)。优化第一步可以是对每个需要加粗的词在string里找长度一样的substring,而不是找出所有string里可能的substring再对照list看需不需要加粗。这样可以把running time从O(n^3)减少到O(n*l*w),n是string长度,l是list长度,w是list中word平均长度。第二步是常规的merge interval,在写法上可以方便一些:merge index而不是直接merge需要被bold的word。


615

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


salary

employee

| id | employee_id | amount | pay_date   |
|----|-------------|--------|------------|
| 1  | 1           | 9000   | 2017-03-31 |
| 2  | 2           | 6000   | 2017-03-31 |
| 3  | 3           | 10000  | 2017-03-31 |
| 4  | 1           | 7000   | 2017-02-28 |
| 5  | 2           | 6000   | 2017-02-28 |
| 6  | 3           | 8000   | 2017-02-28 |

| employee_id | department_id |
|-------------|---------------|
| 1           | 1             |
| 2           | 2             |
| 3           | 2             |

要求找出每个月的各department平均工资相比于当月平均工资是高了还是低了。比如上面的例子输出如下table,因为department 1在三月比当月整体平均工资高,而在二月持平。

| pay_month | department_id | comparison  |
|-----------|---------------|-------------|
| 2017-03   | 1             | higher      |
| 2017-03   | 2             | lower       |
| 2017-02   | 1             | same        |
| 2017-02   | 2             | same        |

题解:厘清题意之后,其实就是做两个table,一个记录每个月department的平均工资,一个记录每个月整体的平均工资,再把两张表join起来并比较工资高低即可。其中找department的平均工资需要把salary和employee给join起来。写起来有些费事。


614.

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

input

output

+-------------+------------+
| followee    | follower   |
+-------------+------------+
|     A       |     B      |
|     B       |     C      |
|     B       |     D      |
|     D       |     E      |
+-------------+------------+

+-------------+------------+
| follower    | num        |
+-------------+------------+
|     B       |  2         |
|     D       |  1         |
+-------------+------------+

题解:可以选出在follower列里的followee,即有follower的follower,再count有多少follower,最后选出followee为folower。也可以用join相关的办法。这题有意思在corner case,可以引发对于sql编程corner case的思考。这里一个是input可能存在duplicated row,而dedup(deduplicate)是必要的,对group起来的几行数据dedup的方法可以是COUNT(DISTINCT projection)。另一个非常隐蔽,和大小写有关。sql是case insensitive的,不仅是关键词比如select是可以大小写混用的,每一个值也是大小写混用的。所以用上面的方法,followee如果是a,follower是A,这个followee会被认为是follower,这样最终被选出的follower成为a而不是A。但最后output在leetcode上是按照string判断的,因此是case sensitive的,因此上面的情况会被判错。如果一定要有这条要求的话,那join的方法更好:以一个input的table的follower和另一个table的followee做join,选出可以有follower的follower,再从第一个table里选出follower,从第二个table里选出follower的follower的数量。


613.

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

题解:一维空间点的距离即为坐标差。straightforward做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)


610.

题目:给出一张表示三角形,三边边长的表,判断每一行代表的三角形是不是valid的

题解:在select利用if / case-when-then-end即可。


609

题目:给出一列string,每个string以一定形式记录一个文件的位置和内容,找出重复内容的file位置。

题解:按照要求parse string、用map记录出现过的file内容并加以判断。虽然简单但是公司很喜欢考。


608

题目:给出一个表,一列是tree node id,另一列是这个node的parent对应的id,求判断每一个node是root,leaf还是正常的inner node

题解:在select利用带subquery的if / case-when-then-end即可。


607

题目题解:给出三个表,一个记录salesperson,一个记录销售给到的company,一个记录transcation,即哪个salesperson卖给了哪个company,按照要求使用join输出即可。


明日题目 Leetcode: 606-597


查看所有题目:

打开Wechat微信->Contacts[联系人]->Official Accounts[公众号]->北美加群小助手Jogchat->天天刷题



【长按关注北美加群小助手Jogchat.com】



阅读 5721

微信扫一扫
关注该公众号