咕果MTV onsite

gky58 发表于 2018-11-10 02:26
我当时想的是类似的思路，存右子树的节点数，但是没有很想清楚。。。。

嗯，这道题要写过很多次才能比较熟，而且其实实现起来还牵扯到平衡问题，估计面试官也不可能要求你没见过的情况下45分钟能全部写出来。应该没问题的，加油。

第三轮用union find set可解吧，根设为set里最大值

大木虫 发表于 2018-11-9 21:51
这道题类似 里口 散要务 的思路，update的实现麻烦一些，getKth()和update/insert 都是logn

补充内容 (201 ...

麻烦问一下，按照lc315的思路，getKth（）怎么实现呢，按照315的思路，只能实现对于每个分数，用logN的时间查找到是第几名。

巨魔阿克 发表于 2018-11-11 09:06
麻烦问一下，按照lc315的思路，getKth（）怎么实现呢，按照315的思路，只能实现对于每个分数，用logN的时 ...

我是这样想的，你看对不对
从root看，我知道左边有几个，右边有几个，所以我知道root是第几个。假设root是按顺序排第n0个node,
比较n0和k，我们知道该去左还是右继续找。假如说n0<k，我们就向右找，现在找的目标是在n0~N的范围里找第k个node,我们可以看现在所处的child左边有多少，右边有多少，得出现在node所处的位置n1,比一下是比k大还是小。如果大，我们就向左，如果小，我们就向右，假设n1>k,那么我们就向左找，范围变成了n0~n1，以此类推，直到找到第K个node

大木虫 发表于 2018-11-11 09:58
我是这样想的，你看对不对
从root看，我知道左边有几个，右边有几个，所以我知道root是第几个。假设root ...

那感觉你这个思想更像是使用binary search tree?

大木虫 发表于 2018-11-11 09:58
我是这样想的，你看对不对
从root看，我知道左边有几个，右边有几个，所以我知道root是第几个。假设root ...

那segmentTreeNode应该怎么写？

struct segmentTreeNode{

}

补充内容 (2018-11-12 06:40):
struct segmentTreeNode{
segmentTreeNode* left;
segmentTreeNode* right;
int score,
int leftChildren;
int rightchildRen;
}

巨魔阿克 发表于 2018-11-12 06:38
那segmentTreeNode应该怎么写？

struct segmentTreeNode{

对，是BST。我散要务就是这么写的

楼主，你的第三轮是怎么从nlogn优化成n的，可以细讲一下吗

想了想感觉BST还是make sense的，每个节点存储右子树的节点个数。。。
update就是删除再插入，删除或插入均需查找&更新O(logn)个节点，复杂度为O(log n)；getEntry就是大木虫讲的思路，复杂度也是O(log n)

穿袈裟的流氓 发表于 2018-11-12 09:43
楼主，你的第三轮是怎么从nlogn优化成n的，可以细讲一下吗

这题就是两步，先把所有card放到suit map里，再对map的每个entry找straight flush。
1. map的entry里如果存的是ordered set，插入是O(log n)，查找是O(log n)。每次从后往前找straight flush，找到了就break。整个下来复杂度就是O(n log n)。
2. 如果是unordered set，插入O(1)，查找O(1)。每次要遍历这个set里的所有value，对每个value(Let's say x)找x-1, x-2, x-3, x-4，没法break。复杂度是O(n)。