60天带你刷完Leetcode【第8天】606-597

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

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

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

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

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

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

题目： 给出一个影院座位表如下，求连续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。

题目： 给出一个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。

题目： 给出一个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))
)
;

题目： 给一个数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结尾的符合条件的个数讨论。

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

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

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

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

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