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

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


每天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】


阅读 5721

微信扫一扫
关注该公众号