整理了Google一些最新高频面经题，求大神指教

给你点个赞！

很有用的信息！

求各位大神指点下第一题的思路可以吗...如果只是向右或者向下我是知道的，但是还可以向上的话 应该怎么做呀 两次dp吗？

第六题除了brute force 选出两个点构造直线ax+b = y 以外 还有什么好的方法么？求大神指导

线那题没问题么？如果是二维空间没重叠感觉所有点都可以二分啊

雨雪霏霏 发表于 2018-12-11 04:15
求各位大神指点下第一题的思路可以吗...如果只是向右或者向下我是知道的，但是还可以向上的话 应该怎么做呀 ...

可以向上的话就是按column更新了，这里得看更新dp table时每个格子的dependencies
具体代码可以参看这个https://www.1point3acres.com/bbs/thread-423857-1-1.html

hzhu07 发表于 2018-12-24 08:36
可以向上的话就是按column更新了，这里得看更新dp table时每个格子的dependencies
具体代码可以参看这个 ...

灰常感谢！

厉害！！！！！！！！！！！！！！

欢迎来一亩三分地论坛！

如果楼主没有记错的话，第六题其实只要对所有的点纵坐标或者横坐标排序，然后拉一条平行于纵坐标或者横坐标的中位数median的线x=median或者y=median，就会把所有的点分成数量相等的集合。

补充内容 (2019-1-20 03:22):
举个例子，天上飘着很多小球，某一瞬间重力产生所有的球垂直掉到横轴所在的地面上，此时所有点纵坐标为0，题目变成找一个点使得左边和右边的小球数量一致==》找中位数。然后排序，topK，QuickSelect都行