狗家onsite

pandami 发表于 2018-11-28 08:31
第一题题号是？

https://leetcode.com/problems/evaluate-division/

少冰半糖谢谢 发表于 2018-11-28 10:04
1）是的 每个节点都服从先占原则。
2）surrounding的意思就是你理解的那样，可以往parent、left、right ...

感谢回复！现在清楚了。。 但是你在楼上说其实是求最大区间。 区间请问你是如何定义的？难道是指最大子树或者是出去一个子树其它node加起来也成为一个区间？ 但是最大不能保证就赢？ 我觉得是这样你看对不对。 比如说一个子树他的左子树有M个点， 右子树有N个点，除去这个子树之外有K个点。 必须满足 K < 1 + m + n && m < k + 1 + n && n < k + 1 + m。 中心思想就是我选了这个点之后，无论你选我的parent 还是我的某个child， 我都能赢。 我觉得要考虑到树unbalance的情况。。。

请问第4题每次选的点必须和之前所有选的点连在一起吗？

少冰半糖谢谢 发表于 2018-11-28 06:58
这道题包装得很好，实则就是通过树的遍历来统计各个分区有多少个点，然后选最大的分区就行了

楼主能再解释下分区是什么意思吗？

Thanks for sharing!

lukuang 发表于 2018-11-28 10:59
感谢回复！现在清楚了。。 但是你在楼上说其实是求最大区间。 区间请问你是如何定义的？难道是指最大子树 ...

emmmm 除去区间的概念和那个不等式 我觉得你其他说的都对。相当于对树进行了分割，选最优分割即可，就是你最后说的那个中心思想。ps，你的那三个条件是互斥的，肯定不是用&&，这里有点问题。

shuofeng11 发表于 2018-11-28 12:45
楼主能再解释下分区是什么意思吗？

想象一颗二叉树，然后呢，你的对手选了右侧中间点的一个节点，记为N。此时在游戏开始之前，你也要选一个点，在你看来，你可以选的点只可能在以下三个区域：N的左子树，N的右子树，N的父节点及其父节点的某一支子树。那你会怎么选呢？你为了赢，肯定选大的区域

shuofeng11 发表于 2018-11-28 12:29
请问第4题每次选的点必须和之前所有选的点连在一起吗？

只选starting node，之后就是扩张自己的版图，不选点。我可能没讲清楚。。

shuofeng11 发表于 2018-11-28 12:29
请问第4题每次选的点必须和之前所有选的点连在一起吗？

只选starting node，之后就是扩张自己的版图，不选点。我可能没讲清楚。。

shuofeng11 发表于 2018-11-28 12:29
请问第4题每次选的点必须和之前所有选的点连在一起吗？

只选starting node，之后就是扩张自己的版图，不选点。我可能没讲清楚。