狗家l3 MTV onsite面经

帅帅的哭豆包儿 发表于 2019/12/20 05:23:00
谢谢你的回复，麻烦再问一下，在右侧插入新的node 有没有什么好的方法来更新子节点和父节点的关系？还有如何更快速的判断这...

我也不知道标准答案，我的做法就是一直往回一个parent然后preorder但是track一下level。找到了可以加的地方就反过来找加的点左边的点来更新linkedlist。感觉没啥更好的方法因为它也不告诉我有多少层，如果知道层数就可以2^（n-1）和linkedlist长度来判断有木有满了

xuzhenzhen2real 发表于 2019-12-15 13:47
明白了明白了，谢谢！请问一下multiset是怎么维护顺序的？每次有新的presum的话是logN插入的吗？我用的是 ...

我发现multiset中是没法进行iterator 加减法的，也就没法快速求出在这个iterator后边有几个数字。那这个题也只能自己维护一个二叉树了，树的节点中要记录右子树的元素个数，这样在查询的过程中能计算出大于某个数的元素个数。整体感觉有点麻烦，还不如直接brute force了

楼主问下第二题的 follow up是求 count of subarray sum less than k, 还是求maximux subarray sum less than k,  
前者的话就跟求count of subarray product less than k 一样双指针吧？
后者的话确实要用到set

楼主可以讲讲第一题用union find的思路吗？

求问楼主 第二题follow up什么思路啊？ subarray sum less than k