每天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】
微信扫一扫
关注该公众号