leetcode周赛290记录

• 注意数据范围。纵坐标取值空间较小
• 故在纵坐标维度上，对每个相同的纵坐标的横坐标进行排序。
• 而不是反过来

class Solution {

public:
    vector countRectangles(vector>& rectangles, vector>& points) {
        vector df[101];
        for(vector a : rectangles)
        {
            df[a[1]].push_back(a[0]);
        }
        for(int i  =  0;i<101;i++) sort(df[i].begin(),df[i].end());
        vector count;
        for(vector p : points)
        {
            int tmp = 0;
            for(int i = p[1];i<101;i++)
            {
                tmp += df[i].end() - lower_bound(df[i].begin(),df[i].end(),p[0]);
            }
            count.push_back(tmp);
        }
        return count;
    }
};

• 一来就想到线段树。给每个区间加上1.但是区间取值空间太大，线段树维护存不下
• 特殊：区间个数较少，且每次区间都加的是1，而不是其他数。
• 因此对给定的数字，搜索在其前面开花的区间，并搜索在其前面凋谢的区间。

class Solution {
public:
    vector fullBloomFlowers(vector>& flowers, vector& persons) {
        vector st;
        vector end;
        for(vector a:flowers)
        {
            st.push_back(a[0]);
            end.push_back(a[1]);
        }
        sort(st.begin(),st.end());
        sort(end.begin(),end.end());
        vector ans;
        for(int v : persons)
        {
            auto i = upper_bound(st.begin(),st.end(),v);
            auto j = upper_bound(end.begin(),end.end(),v);
            ans.push_back(i - st.begin()  - (j - end.begin()));
        }
        return ans;
    }
};

• 另：比赛中反应出的C++问题
• set迭代器不能用于计数
• 自定义排序函数的写法可以是

        sort(rectangles.begin(), rectangles.end(), [](auto &a, auto &b) { return a[1] > b[1]; });

• 注意变遍历为引用，可以节省复杂度：
  例如超时代码：

for(vector c : circles)
                {
                    int x1 = c[0];
                    int y1 = c[1];
                    int r = c[2];
                    if((x1 - x)*(x1 - x) + (y1 - y) * (y1 - y) <= r*r)
                    {
                        flag = true;
                        break;
                    }
                }

在vector之前加引用以后，不超时了：

class Solution {
public:
    int countLatticePoints(vector>& circles) {
        int ans = 0;
        for(int x = 0;x<=200;x++)
        {
            for(int  y = 0;y<=200;y++)
            {
                bool flag = false;
                for(vector& c : circles)
                {
                    int x1 = c[0];
                    int y1 = c[1];
                    int r = c[2];
                    if((x1 - x)*(x1 - x) + (y1 - y) * (y1 - y) <= r*r)
                    {
                        flag = true;
                        break;
                    }
                }
                ans += flag;
            }
        }
        return ans;
    }
};