建立网站预算/培训心得模板

题目

OJ平台

题目解析

扫描步骤：

1. 把点扫描转为线扫描。把每个矩形用左右两边进行表示，如何表示边？(a,b,c) a代表这条边的x座标，而b，c代表对应的y座标。
2. 把一竖行的所有线合并。但注意可能被隔开，但没关系，后续判断即可。
3. 根据如图所示的规律进行求解。最左边的和最右边的一竖肯定只能是一竖线，而中间的每一竖线都有左右两竖线！

代码详解

java代码解析

class Solution {public boolean isRectangleCover(int[][] rectangles) {int n = rectangles.length << 1, index = 0;//扫描线数组，四元组：[横坐标，纵坐标起点，纵坐标终点，左线段还是右线段]int[][] lines = new int[n][4];for (int[] rectangle : rectangles) {//加入四元组，1表示左线段，-1表示右线段lines[index++] = new int[]{rectangle[0], rectangle[1], rectangle[3], 1};lines[index++] = new int[]{rectangle[2], rectangle[1], rectangle[3], -1};}//对扫描线进行排序预处理，方便后续的线段判断Arrays.sort(lines, (o1, o2) -> o1[0] == o2[0] ? Integer.compare(o1[1], o2[1]) : Integer.compare(o1[0], o2[0]));//分别存储相同横坐标下的 [左边线段] 和 [右边线段]，在对横坐标进行一次处理后，存放的应该是对应方向合并后的线段List<int[]> leftLine = new ArrayList<>(), rightLine = new ArrayList<>();//双指针遍历每一个集合中的横坐标，通过横坐标获取到矩形的纵线段for (int left = 0; left < n; ) {int right = left;leftLine.clear();rightLine.clear();//找到left横坐标相同的部分，使得区间[left, right)的横坐标都是相同的while (right < n && lines[left][0] == lines[right][0]) right++;//遍历这个区间内的线段（横坐标相同）for (int i = left; i < right; i++) {//得到当前横坐标上的线段，二元组 [纵坐标起始位置，纵坐标终止位置]int[] yLine = new int[]{lines[i][1], lines[i][2]};//引用传递，line直接指向左线段或者右线段集合List<int[]> line = lines[i][3] == 1 ? leftLine : rightLine;if (line.isEmpty()) line.add(yLine);else {//如果能进来这个else，说明在当前横坐标上有多条“左边”或“右边”，将当前边和上一次的边取出对比，如果当前边的纵坐标起点和上一条边出现了交叉，必然不是完美矩阵int[] prevYLine = line.get(line.size() - 1);//线段有交叉，说明必然有交叉矩阵，不符合题意if (yLine[0] < prevYLine[1]) return false;else if (yLine[0] == prevYLine[1]) {//如开始的x坐标是1，对应的线段是左线段[1,3]和[3,4]，当前线段和上一条线段能够刚好相接，直接修改上一条线段的纵坐标终止位置为当前线段的终止位置prevYLine[1] = yLine[1];} else {//@这个else暂时没看懂：现在懂了，如果没有被合并为一条线，则后面会进行判断的！line.add(yLine);}}}if (left > 0 && right < n) {//若不是完美矩形的边缘竖边，检查放入的左线段和右线段，因为在上面的循环操作中，合法线段都最后合并成一条，所以还需要比较左线段和右线段对应的起始和终止点if (leftLine.size() != rightLine.size()) return false;for (int i = 0; i < leftLine.size(); i++) {if (leftLine.get(i)[0] == rightLine.get(i)[0] && leftLine.get(i)[1] == rightLine.get(i)[1]) continue;return false;}} else {//左边缘竖边在经过合并后存放大小为1的线段数组，如x=1时，存放的是[1,4]，此时如果存在右边缘线段，必然不是完美矩形，反之亦然if (leftLine.size() + rightLine.size() != 1) return false;}//移动left指针，继续寻找下一个x坐标对应的所有线段数组left = right;}return true;}
}

• 结合图来解释扫描线的这一段代码：

为什么不在这个位置直接return false？

因为如图所示，可能中间横插一块，导致无法合并为一条线，所以是直接就入队的形式。而后面对最左边和最右边的线进行特殊化处理，因为这两个线一定能合并为一条线。

对应代码

else {line.add(yLine);
}
...else {//这是对最左和最右边的处理if (leftLine.size() + rightLine.size() != 1) return false;
}

• 最关键的处理技巧：

只要这个合并后的竖线在内部，则必定是成双的（注意是一竖行一竖行的扫）！也就是两个格子由于都能被挨到，所以都会存在左右各合并成>=1条线的情况，而且线的数量上肯定是相等的！

cpp代码

class Solution {
public:
// cpp扫描线：实际上还是利用了完美矩形的特点，你可以从交点的情况分析，当然也可从合并边的方式分析。
//比如我这里就是从合并边的方向分析，具体而言就是：只要不是最左边和最右边的边，则肯定会有两条边一一对应。
//注意：是一竖行一竖行的验证bool isRectangleCover(vector <vector<int>> &rectangles) {int sz = rectangles.size();rectangles.resize(2 * sz);int idx = sz;for (int i = 0; i < sz; i++) {//更新线int x1 = rectangles[i][0], x2 = rectangles[i][2];int y1 = rectangles[i][1], y2 = rectangles[i][3];rectangles[i] = {x1, y1, y2, -1};assert(idx < 2 * sz);rectangles[idx++] = {x2, y1, y2, 1};}//排序线sort(begin(rectangles), end(rectangles), [](vector<int> &a, vector<int> &b) {if (a[0] != b[0])return a[0] < b[0];return a[1] < b[1];});//进行扫描线int l = 0, r = 0;vector <pair<int, int>> l1, l2;while (r < 2 * sz) {l1.clear();l2.clear();while (r < 2 * sz && rectangles[l][0] == rectangles[r][0])r++;//得出一竖行的所有点for (int i = l; i < r; i++) {//进行一竖行线的合并pair<int, int> cur = make_pair(rectangles[i][1], rectangles[i][2]);vector <pair<int, int>> &line = rectangles[i][3] == -1 ? l1 : l2;if (line.empty()) {line.push_back(cur);} else {if (cur.first < line.back().second)//产生重叠return false;else if (cur.first == line.back().second)//合并line.back().second = cur.second;else {//可能中间存在分割line.push_back(cur);}}}//合并完线以后进行三种情况的分析if (l > 0 && r < sz * 2) {//处理中间线if (l1.size() != l2.size())return false;else {for (int i = 0; i < l1.size(); i++) {if (l1[i].first != l2[i].first || l1[i].second != l2[i].second)return false;}}} else {//处理左右边缘线if (l1.size() + l2.size() != 1)return false;}//继续往前推进l = r;}return true;}
};