## 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对性能和维护有着更重要的影响。

```sql
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的情况。