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

这次的题目难度不大，但其中有一题小编的解法beat了99.13%所有提交的答案的运行时间。可以说，小编和你们以前在成长😄

606

题目：从一颗binary tree构造一个特定format的string。要求是tree和string一一对应，即node为null的情况尽量不记录在string里。

题解：根据左右child node是否为null的四种情况分别判断要不要把null记录在string里，而后用preoder遍历即可。注意理解一一对应即可。

605

题目：给出一个1d array，其中0代表可以种花，1代表不可以，再给出要种的花的数量n，问能不能把n朵花都种上。

题解：这题很奇怪，就是采用greedy的策略，有坑就把花种上。

604

题目：给出一个”compressed” string比如L1e2t1C1o1d1e1，代表着LeetCode，即数字代表character出现次数。要求implemented一个class，这个class有两个methods: next()和hasNext()，作用分别是给出input string下一个字母和判断是否有下一个字母。

题解：这题有很多解法，核心是把存储input string对应的decompressed string。比如如L1e2t1C1o1d1e1可以存成LeetCode，也可以用两个array分别存字母和出现次数。

603

题目：给出一个影院座位表如下，求连续free座位有两个以上的行。比如下面的例子应选出第1，2行和第4-5行。

| seat_id | free |
|---------|------|
| 1       | 1    |
| 2       | 1    |
| 3       | 0    |
| 4       | 1    |
| 5       | 1    |

| 6       | 1    |

题解：思路在于先选出free座位，再选出id连续的行。第二步比较好的办法是列举可能的情况：id和id+1都在表里和id和id-1都在表里。这样可以写一个subquery来用in来选出这两种情况对应的id。

602

题目：给出一个request_accepted表如下：求拥有friend最多的用户和其拥有的用户数。比如下表3加了4同时1、2加了3，所以3有3个朋友。

| requester_id | accepter_id | accept_date|
|--------------|-------------|------------|
| 1            | 2           | 2016_06-03 |
| 1            | 3           | 2016-06-08 |
| 2            | 3           | 2016-06-08 |
| 3            | 4           | 2016-06-09 |

题解：题意是在accepter和requester一共出现了几次就算做有几个朋友。所以可以一次把requester作为本人、acceptor作为朋友，一次把acceptor作为本人、requester作为朋友再把选出的结果union起来再count。

601

题目：给出一个stadium访问情况的表，date是连续的，求出连续三天以上有100人以上访问的row。比如下面的例子，第5-8行所代表的4天每一天都有100人以上访问，因此这四行被选出来。

| id   | date       | people    |
+------+------------+-----------+
| 1    | 2017-01-01 | 10        |
| 2    | 2017-01-02 | 109       |
| 3    | 2017-01-03 | 150       |
| 4    | 2017-01-04 | 99        |
| 5    | 2017-01-05 | 145       |
| 6    | 2017-01-06 | 1455      |
| 7    | 2017-01-07 | 199       |
| 8    | 2017-01-08 | 188       |

题解：这题思路和603相仿，关键在于id这一列。选出可能出现在连续三天的id即可，这样有三种情况，即id为连续三天的第一天、第二天、第三天，implement方法是此id对应的另外两天的id也在表中出现。题目本身提供的solution太繁琐，这里的方法只需要subquery，因此beat了99.13%的submission。尤其是在hdfs上处理海量数据，不用group by和join意味着减少reducer，而reducer相比mapper对性能和维护有着更重要的影响。代码如下：

select * from stadium 
where people >= 100
and
(
    (id+1 in (select id from stadium where people >= 100) 
    and id+2 in (select id from stadium where people >= 100))
    or
    (id-1 in (select id from stadium where people >= 100) 
    and id-2 in (select id from stadium where people >= 100))
    or
    (id+1 in (select id from stadium where people >= 100) 
    and id-1 in (select id from stadium where people >= 100))
)
;

600

作者:学渣小编

给一个数n。问从1到n的数转换成二进制后，有多少个二进制数中不出现连续的1。Note: 1 <= n <= 10^9。比如1到5：1->1, 2->10, 3->11, 4->100, 5->101。这其中只有3转换成的二进制数有连续的1出现，因此有4个数满足题意。

题解：

用dp, 从n的第一个前缀开始build, 分以0结尾和以1结尾的符合条件的个数讨论。

num =（10110）2

前缀= 1

prefixEnding0 = 1，入选{0}

prefixEnding1 = 0，

isPrefixValid = true，入选{1}组成

前缀= 10

prefixEnding0 = 1，入选{00}

prefixEnding1 = 1，入选{01}

isPrefixValid = true，入选{10}

前缀= 101

prefixEnding0 = 3，入选{000,010,100}

prefixEnding1 = 1，入选{001}

isPrefixValid = true，入选{101}

前缀= 1011

prefixEnding0 = 5，入选{0000,0100,1000,0010,1010}

prefixEnding1 = 3，入选{0001,0101,1001}

isPrefixValid = false，入选{}

prefix = 10110

prefixEnding0 = 8，入选{00000,01000,10000,00100,10100,00010,01010,10010}

prefixEnding1 = 5，入选{00001,01001,10001,00101,10101}

isPrefixValid = false，入选{}

最后，我们返回8 + 5 = 13。

Running time: O(1); Space O(1)

599

题目题解：给出两个array代表两个人想去的餐馆，求出俩人都想去的餐馆。用hash table即可。

598

题目：给出一个m*n的matrix，初始每个位置均为0。再给出一个operation array，每个operation是一个长度为2的数组[a,b]，代表左上角[0,0]到右下角[a,b]的区域的每个数字要+1。求最后matrix里最大数字所组成区域的大小。

题解：理解题目后，实际上就是求每次operation都覆盖的区域，即所有operation影响的最小范围。

597

题目：给出一个friend_request表和request_accepted表，求accepted rate。

题解：根据题意count request数量和acceptance数量即可， 注意在select使用isnull来防止分母为0的情况。

明日题目 Leetcode: 596-587

查看所有题目：

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

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