60天带你刷完Leetcode【第6天】626-617

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

每天30分钟 关注【北美加群小助手】学渣小编带你60天刷完硅谷IT公司面试题。学渣也能跻身一线公司、升职加薪、当上总经理、出任CEO、迎娶白富美、从此走上人生巅峰!想想还有点小激动😏


小编注意到Facebook都有专门的Data Engineer new grad岗位了(一直有experienced岗位),说明Data Engineering越来越重要、SQL题目也要足够重视了~


626

作者:学酥

题目:如下面的表,问如何将相邻两行的人名字调换得到sample out

+---------+---------+
|    id   | student |
+---------+---------+
|    1    | Abbot   |
|    2    | Doris   |
|    3    | Emerson |
|    4    | Green   |
|    5    | Jeames  |
+---------+---------+






>>>>>

+---------+---------+
|    id   | student |
+---------+---------+
|    1    | Doris   |
|    2    | Abbot   |
|    3    | Green   |
|    4    | Emerson |
|    5    | Jeames  |
+---------+---------+

题解:SQL语句不能loop每一行数据并keep上一个iteration的值,只能对某一行做处理。因此这个题要instead改变id而不是改变student的名字,而id可根据奇偶来做+1或-1处理。


625

作者:学酥

题目:找到一些特定数中的最小数,这些数每一位digit的乘积等于给定的一个整数a。比如238和443和68的每一位digit的乘积都等于48,其中68最小。

题解:实际上这道题问的是找到给定数的个位数factor的最小排列。可以从大到小找到能整除给定数的个位数factor(从9到0),并将找到的factor从低位到高位的组成答案。


624

作者:学酥

题目:有m个sorted array,从任意两个不同的array中各取一个数,求取出数值差的最大绝对值。

题解:由于每个候选的array都是sorted的,可以在loop每个array的过程中keep一个到当前array之前的最小数和最大数,将这些最小数和最大数与当前的array的最大值和最小值做差并从中选取global的最大差值。


623

作者:学酥

题目:要求在binary tree的某一层d加入value为k的node,每个在那一层的node下面加两个。

题解:可以常规的level order到第d层,然后停止并做相应的添加node操作。也可以做dfs,记录当前recursion对应的层数,到第d层添加node并返回。


621

作者:学酥

题目:给一个task list,要求设计task scheduler。每个task用一个字母代表,在list里每出现一次代表运行需要一个单位的时间。比如['A','A','A','B','B','B']表示需要运行task A三个单位时间,task B三个时间。还有一个input是cool down的时间n,规定同一个task运行一个时间点后必须相隔一定时间再运行一个时间点。比如n=2则运行一个task两个时间点后必须运行其他task或idle。求最少的运行完所有task所需的单位时间。比如上面的list的一个最短运行方案为A -> B -> idle -> A -> B -> idle -> A -> B.

题解:理解题目后,发现没有idle的最短运行时间要么是task的个数,要么有idle的话为最耗时task运行所需要的时间,其余的task的执行可以安排在运行最耗时task方案的idle的位置上。比如['A','A','A','B','B','B',’C’]和上面例子的最短运行时间一样,方案是把’C’放在一个idle的时间点上运行。而['A','A','A','B','B','B',’C’,’D’]将把上面例子方案中的idle填满,这时运行时间等于task的个数;['A','A','A','B','B','B',’C’,’D’,’F’]将比上面例子多一个运行时间,不过等于task的个数。计算最耗时task运行所需要的时间为(最耗时task所需时间-1)*(n+1)+最耗时task的种数,比如如果AB都是最耗时task那种数为2。


620

此题按照题意去写即可。


619

此题按照题意去写即可。


618

作者:学酥

题目:按照题意将对table做pivot(转换成另一张表)。这里是把其中一列每一个值单独做成一列

| name   | continent |
|---------|-------------|
| Jack    | America   |
| Pascal | Europe    |
| Xi         | Asia         |
| Jane    | America   |



>>>>>


| America | Asia | Europe |
|-----------|------|----------|
|    Jack    | Xi    | Pascal   |
|    Jane    |        |              |    

题解:先思考新的表要如何得到。比较straightforward的做法是从原表中分别找出每一列,再想办法合并;要想合并列就要join(要想合并行可以union),join就要有share的一列,否则将是cross join;要有share的一列,常见的办法是增加一个index列,这在mysql中可以通过user-defined variable实现,下面的query可以每选出一行data就对a加1,使其成为从0开始的一列index:

Set @a = 0;

select name, @a := @a + 1 as id from student where continent = 'America';

但要怎么join呢?结果是保留了所有的data,因此不能inner join,否则行数会减小至参与join所有table的行数最小值,而必须使用left join并将行数最多的table放在最左(或者vice versaright join)。这样就导致一个问题:必须提前知道哪一列有最多的数据,因此题目强调America有最多的数据。

Follow-up:如果不知道/不想知道哪一列有最多的数据呢?可以看一下另一种aggregate的办法:group-by。我们可以用上述的user-defined variable得到下表(在select的时候加上case-when/ if-else就可以使value为null),再group by idx即可合并idx相同的行而得到所需要的结果。group之后的select有一个 trick,要根据group-by的规则使用min(col_name)或者max,因为我们每个group只有一个value(一个idx对应一个value),因此随便选择一个operater都可以得到正确结果。

| America | Asia | Europe | idx |
|-----------|------|--------|-----|
|     Jack   | null |   null   |   0  |  

|       null     | null |  Pascal |   0   |

|      null    |  Xi  |    null  |   0   |
|     Jane   | null |   null   |   1  |

代码:

set @idx1 = 0, @idx2 = 0, @idx3 = 0;

select min(America) America, min(Asia) Asia, min(Europe) Europe

from (

select (case when continent='America' then @idx1 = @idx1+1

            when continent='Asia' then @idx2 = @idx2+1

            when continent='Europe' then @r3 = @idx3+1

        end) as idx,

       (case when continent='America' then name

        end) as America,

       (case when continent='Asia' then name

        end) as Asia,

       (case when continent='Europe' then name

        end) as Europe

       from student

       order by name#) T

group by idx
;


617

作者:学酥

题目:合并两个binary tree,规则是新binary tree的node value为两个旧的tree在对应位置的node的sum。例子如下:

   1

  /  \

  3   2

\

 5



+

  2

 /  \

1    3

 \     \

  4    7



>>>>>>


   1+2

  /       \

3+1    2+3

/  \        \

5   4       7

题解:traverse两棵树,在每一个recursion构建新的node并按照规则设定value的值,将左右child设置为对旧的tree左右child做recursion的返回值。


明日题目 Leetcode: 606-597


查看所有题目:

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



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


阅读 5668

微信扫一扫
关注该公众号