比赛review帖

miugel 发表于 2018-7-15 10:22
这周发挥比较好，四道题都能直接有思路，最后一道题写错了个地方，最后整体WA了一次。

1. 直接从右往左 ...

刚才铁汁被审核了。。 基本上123跟你解法差不多。

单聊一下第四条好了， POJ2431。

这题用PQ就可以做， 存储可以通过的所有加油站。

邮箱不够时poll最多油的加油站。

代码我贴链接好了。。 这个审核机制真的佛了

miugel 发表于 2018-7-15 10:22
这周发挥比较好，四道题都能直接有思路，最后一道题写错了个地方，最后整体WA了一次。

1. 直接从右往左 ...

帖子一直被审核。。 我直接贴图了

补充内容 (2018-7-15 22:45):
https://gist.github.com/catherin ... 4ba1f28d0dab426ade9

补充内容 (2018-7-15 22:47):
第四题我是刚好见过的。。

肥宅快乐水 发表于 2018-7-15 22:43
帖子一直被审核。。 我直接贴图了

补充内容 (2018-7-15 22:45):

赞，这个解法确实很巧妙~
最近在练DP，看到这种max/min问题就想朝这个方向靠哈哈

这周的题目也不难

1. Leaf-Similar Trees
把2棵树的答案都算出来然后比较就可以

2. Walking Robot Simulation
简单的模拟，但是我没看到是求过程中的最大距离，结果debug了40分钟

3. Koko Eating Bananas
值域二分

4. Length of Longest Fibonacci Subsequence
用的记忆化搜索做的，二维dp应该也可以

lintcode其实看了然后没怎么做。。 出门喝酒了

https://leetcode.com/contest/weekly-contest-94

[872 | pass]
in order traversal 找leaf

[873 | pass]
这题比我想象的还简单。。 感觉之前见过类似的
用set存A里的值， n方循环，因为数组长度<=1000, 去掉 a[i] = a[j] 的情况

[874 | fail]
我觉得做法没什么问题，很简单的一个走路。。 做不来， 一个test case过不了，倍长的一个， 也懒的测了。。

[875 | pass]
其实挺明显是二分法去找target rate的。 这里需要注意判断等于时的边界条件。

假设 m = (lo + hi ) >>> 1 为测试值， 现在 count(pile, m) <= H 时， 说明rate过高。且m是满足H这个需求的。 这时更新hi = m;
这跟自己写的二分搜索条件有关系。 我一直用的是
```
        while(lo < hi)
        {
            int m = (lo + hi) >>> 1;
            if(condition(m)) lo = m + 1;
            else hi = m;
        }
        return lo;
```

我最开始想在二分里面count hour的时候是不是得再用一个什么方法， 想了很久没做出来。
后来我想了一下， 算是 n lgn 的时间吧。。估计linear去数计算时间的方法能过，一提交果然就过了。

miugel 发表于 2018-7-22 10:54
这周的题目也不难

1. Leaf-Similar Trees

佛了兄弟， 多亏了你我过了874。。我也是完全没读题去找最远距离。。

874。。想起了许多。。

有玩过猫扑的人知道这个梗的吗。。如果知道大概会懂233怎么回事。。

肥宅快乐水 发表于 2018-7-22 10:59
佛了兄弟， 多亏了你我过了874。。我也是完全没读题去找最远距离。。

874。。想起了许多。。

哈哈，我是看了排行榜里发现好多人第二题都没过，然后就觉得应该是漏了什么东西没看到。真的是浪费生命的一题

晚上去看守望屁股了， 炫酷。。{:8_247:}

https://www.lintcode.com/contest/46

[1486 | pass]
用map记录即可，最后要按字典排序。因为是一进一出，所以不难。
我用两个map， 一个记录进出时间算运行时间， 另一个记录总体时间。

[935 | pass]
很标准一道backtrack

[1487 | pass]
n <= 10^5, 其实我有点犹豫O[n^2] 能不能过。
三角形的基本定理应用， 两边之和大于第三边。 更希望是两小边之和大于第三大边。
先县排序， 再两个指针走一遍。

[1488 | fail]
这题我有点懒的想了。。 现在方法是排序之后在set里面找下一个存在的数字， 算run。这显然最次情况是N^3,,

肥宅快乐水 发表于 2018-7-27 19:45
晚上去看守望屁股了， 炫酷。。

https://www.lintcode.com/contest/46

好凶好凶。。Lintcode也是厉害能有这多题。。

vtiaocao 发表于 2018-7-28 13:05
好凶好凶。。Lintcode也是厉害能有这多题。。

感觉已经是lc的复制了。。 lc上做不了的锁题在lintcode上都能做。。