G-o-o-g-l-e 电面

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

zyoppy008 发表于 2016-10-4 13:16
来不及了。。我明天就要电面了。。。

按矩形的竖边的横坐标排序，然后从左往右，碰到矩形就把边表示的区间加入线段树，出矩形就删掉区间

suiyuan2009 发表于 2016-10-4 13:19
按矩形的竖边的横坐标排序，然后从左往右，碰到矩形就把边表示的区间加入线段树，出矩形就删掉区间

这个我知道。。。跟perfect rectangle 类似 扫描线嘛。。。但是没有用到线段树，还有具体怎么算面积呢。。。

zyoppy008 发表于 2016-10-4 13:22
这个我知道。。。跟perfect rectangle 类似 扫描线嘛。。。但是没有用到线段树，还有具体怎么算面积呢。 ...

线段树求和，线段树里记的就是有没有被覆盖，然后就求出两个相邻的横坐标之间的面积了

suiyuan2009 发表于 2016-10-4 13:25
线段树求和，线段树里记的就是有没有被覆盖，然后就求出两个相邻的横坐标之间的面积了

大神厉害哎。。懂的比较模糊，估计店面要出这个题，我也只能摔键盘了

suiyuan2009 发表于 2016-10-4 13:25
线段树求和，线段树里记的就是有没有被覆盖，然后就求出两个相邻的横坐标之间的面积了

这让我没看过题目...又没看过这 扫描线+线段树 的人...能在45分钟想出来么...求解..

leixiang5 发表于 2016-10-4 13:41
这让我没看过题目...又没看过这 扫描线+线段树 的人...能在45分钟想出来么...求解..

只能说。。。警报响的好。。。。

最清晰的解法，完美handle你的情况。
https://discuss.leetcode.com/topic/55923/o-n-solution-by-counting-corners-with-detailed-explaination