LeetCode

November 15th : 319. 灯泡开关
November 16th : 391. 完美矩形

源自力扣官方题解，完事睡觉！

//version1 brutal force 根据1billion的数据量，暴力解法注定只是图一乐，哈哈
//暴力解法也就是把整个灯泡开闭的过程模拟一遍
class Solution {
public:
    int bulbSwitch(int n) {
        if(n < 2) return n;
        if(n == 2) return 1;
        vector bulbs = vector(n, 1);
        for(int i = n & 0x1 ? 1 : 0; i < n; i+=2) bulbs[i] = 0;
        for(int i = 3; i <= n; i++) 
            for(int j = 0; j < n; j+=i) 
                bulbs[j] = bulbs[j] == 1 ? 0 : 1;
        return accumulate(bulbs.begin(), bulbs.end(), 0);
    }
};
//version2 math method
class Solution {
public:
    int bulbSwitch(int n) {
        //return sqrt(n);
        return sqrt(n+0.5);
    }
};

两种方式，第一种也是比较直观的思路如下：

• ① 统计小矩形面积，更新左下右上四个值；
• ② 把每次遍历到的矩形四点坐标放入set中，重复的就去除；
• ③ 观察set是否只剩4个，且是左下右上四个值的组合；
• ④ ③满足且小矩形面积之和等于四个值组成矩形面积，返回真否则假。

注意：对于pair，unordered_set 没有专门的哈希函数，若是定义unordered_set>编译器会报错。

class Solution {
public:
    bool isRectangleCover(vector>& rectangles) {
        int sumArea = 0;
        int left = INT_MAX, up = INT_MIN;
        int right = INT_MIN, down = INT_MAX;
        set> s;
        for(auto& rectangle : rectangles) {
            left = min(left, rectangle[0]);
            right = max(right, rectangle[2]);
            up = max(up, rectangle[3]);
            down = min(down, rectangle[1]);

            sumArea += (rectangle[2]-rectangle[0]) * (rectangle[3]-rectangle[1]);

            pair lu = make_pair(rectangle[0], rectangle[3]);
            if(!s.count(lu)) s.insert(lu); else s.erase(lu);
            pair ld = make_pair(rectangle[0], rectangle[1]);
            if(!s.count(ld)) s.insert(ld); else s.erase(ld);
            pair ru = make_pair(rectangle[2], rectangle[3]);
            if(!s.count(ru)) s.insert(ru); else s.erase(ru);
            pair rd = make_pair(rectangle[2], rectangle[1]);
            if(!s.count(rd)) s.insert(rd); else s.erase(rd);
        }

        pair lu = make_pair(left, up);
        pair ld = make_pair(left, down);
        pair ru = make_pair(right, up);
        pair rd = make_pair(right, down);

        if(s.size() == 4 && s.count(lu) && s.count(ld) && s.count(ru) && s.count(rd))
            return sumArea == (up-down)*(right-left);

        return false;
    }
};

第二种思路，是题解当中的，使用堆进行矩阵的边匹配，有些类似拼图的过程，从左至右，从下至上寻找可以拼接的矩阵块，若是最终堆中没有矩阵块的话那么就是完美矩阵，否则就不是。思路可见力扣题解：图解 完美矩形 （扫描线）。

class Solution {
public:
    bool isRectangleCover(vector>& rectangles) {
        priority_queue, vector>, greater>> pq;
        // 记录扫描线的堆。扫描线包含矩形的右边界的 x、下边 y 和上边 y
        sort(rectangles.begin(), rectangles.end());//由左往右，自下而上排序
        int i = 0;// i 记录已经扫描的矩形
        int len = rectangles.size();
        int nextX = rectangles[0][0];
        int nextY = INT_MIN;
        // 先将最左边一列的矩形加到堆中，作为匹配的开始
        while(i tp = {rectangles[i][2], rectangles[i][1], rectangles[i][3]};
            pq.push(tp);
            i++;
        }
        // 从左到右，从下到上，从已经匹配的矩形开始往右推进，不断进行匹配
        // 因为都是矩形，所以当匹配成功时也一定是矩形
        while(!pq.empty()){
            auto cur = pq.top();
            pq.pop();
            // 从堆顶找一条 x 相同、连续的最长的线段，也就是上下边相接
            int xStart = get<0>(cur);
            int yStart = get<1>(cur);
            int yEnd = get<2>(cur);
            while(!pq.empty() && xStart==get<0>(pq.top()) && yEnd==get<1>(pq.top())){
                yEnd = get<2>(pq.top());
                pq.pop();
            }
            // 从 rectangles[i:] 开始找到与上面线段完美匹配的连续矩形，
            // 也就是和上面线段 x 相接并且高度相等的矩形
            while(i