这是悦乐书的第 325 次更新, 第 348 篇原创
01 看题和准备
今天介绍的是 LeetCode 算法题中 Easy 级别的第 195 题 (顺位题号是 836). 矩形表示为数组[x1,y1,x2,y2], 其中(x1,y1) 是其左下角的坐标,(x2,y2)是其右上角的坐标.
如果交叉区域为正, 则两个矩形重叠. 两个仅在拐角处或边缘处接触的矩形不会重叠. 给定两个 (轴对齐) 矩形, 判断它们是否重叠. 例如:
输入: rec1 = [0,0,2,2],rec2 = [1,1,3,3]
输出: true
输入: rec1 = [0,0,1,1],rec2 = [1,0,2,1]
输出: false
注意:
矩形 rec1 和 rec2 都是 4 个整数的数组.
矩形中的所有坐标值都在 - 10 ^ 9 到 10 ^ 9 之间.
本次解题使用的开发工具是 eclipse,jdk 使用的版本是 1.8, 环境是 win7 64 位系统, 使用 Java 语言编写和测试.
02 分析题目
我们可以先从一维的角度来分析问题, 即将问题对象降低成两条线段, 判断两条线段是否会存在重叠的部分. 具体的分析可以看图一:
image
从上图得到的结论就是, 只要两个点满足: X1 <X4 && X3 < X2, 就可以重叠.
再将视角切回题目中的矩形上来, 换成两对点组成的矩形区域, 判断两个矩形是否重叠. 具体分析可以看图二和图三:
image
image
从上面两张图, 四种情况来分析, 只要四个点满足: X1 < X4 && X3 < X2 && Y1 < Y4 && Y3 < Y2, 两个矩形就可以重叠.
03 第一种解法
直接判断四个点都必须满足条件才能保证重叠.
- public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
- return rec1[0] < rec2[2] && rec2[0] < rec1[2] &&
- rec1[1] < rec2[3] && rec2[1] < rec1[3] ;
- }
04 第二种解法
也可以反方向进行判断, 仅仅是边界重叠是没用的, 所以判断条件需要带上等号, 变成大于等于.
- public boolean isRectangleOverlap2(int[] rec1, int[] rec2) {
- if (rec1[0]>= rec2[2] || rec2[0]>= rec1[2]) {
- return false;
- }
- if (rec1[1]>= rec2[3] || rec2[1]>= rec1[3]) {
- return false;
- }
- return true;
- }
05 小结
算法专题目前已日更超过五个月, 算法题文章 195 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.
以上就是全部内容, 如果大家有什么好的解法思路, 建议或者其他问题, 可以下方留言交流, 点赞, 留言, 转发就是对我最大的回报和支持!
来源: http://www.jianshu.com/p/cf36cbf9d4b5