9.26新鲜热乎的狗狗昂塞

1. 如果element较少数字较大，可以直接上dfs, set去重。如果数字多，用动规，构建dp[nums.length + 1][sum + 1], 能做到复杂度O(n * sum(elements))。
2. 用PriorityQueue maintain 可以同时在线的人，用 global int k来记录出栈的人，每次栈更新，每个栈里的人可以为第 k + (1, ... heap.size()) 的人
3. 貌似是求 sum of tree - sum of subtree ?
4. 将岛屿编码去重？

seanhfyz 发表于 2018-9-27 09:02
我的思路是把List分别按start和end排序，放进ListSortByStart和ListSortByEnd的两个list里
取ListSortBy ...

只需要sortByEnd，取第K个，return所有跟它相交的interval

最后那个distinct island，除了找到所有的岛之后两两对比还有更快的方法嘛？

Phoenix_0592 发表于 2018-9-27 12:29
最后那个distinct island，除了找到所有的岛之后两两对比还有更快的方法嘛？

可以把找到的岛的路径预先存起来
遍历的时候总是先得到左上角的点（起点一致）
路径一致 即为相同

楼主女硕士，今年5月毕业，到现在还没找到工作。刷题也有300多了。投了很多很多简历，就拿到2个OA， 刚做完不知道结果。深深感受到找工作太难了。。。。现在只希望能找到个给抽H1B的工作。薪水什么的都无所谓了，地点也无所谓。相投new grad， 但是找不到内推。所以请问地里有什么各路大神能帮我一下下？？？谢谢了，感激不尽

谢谢LZ，祝你拿到offer

还差26分能看。。祝楼主顺利取offer！

seanhfyz 发表于 2018-9-27 09:02
我的思路是把List分别按start和end排序，放进ListSortByStart和ListSortByEnd的两个list里
取ListSortBy ...

和我思路一样。只不过不用全部排序，只要get Kth min就可以。这样从nlogn降到nlogk。应该是对的吧。
第一题是不是就是老老实实2^n没有任何花哨的？

wangdi561 发表于 2018-9-27 12:26
1. 如果element较少数字较大，可以直接上dfs, set去重。如果数字多，用动规，构建dp[nums.length + 1][sum  ...

怎么dp啊
可以解释一下吗

wsx247 发表于 2018-9-27 15:57
怎么dp啊
可以解释一下吗

Step1. Sum all elements, eg.[2,5,1], sum = 8, construct a 2D array boolean[i][j] = boolean[3 + 1][8  + 1], means whether a certain sum j can be formed by front i elements
Step2. update dp[i][j] = dp[i - 1][j] || dp[i - 1][j - arr[i]]
Step3. record all j where dp[arr.length][j] = true