LeetCode周赛290回顾总结
一、2248.多个数组求交集
1、原题链接:
2、解题思路:
这题比较简单,想必都能写出来,就不做过多赘述了。
3、参考代码:
class Solution { public: vector<int> intersection(vector<vector<int>>& nums) { vector<int> res; unordered_map<int,int> mp; int n = nums.size(); for(int i = 0; i < n; i ++){ for(auto & a : nums[i]){ mp[a] ++; } } for(auto & [k,v] : mp){ if(v == n) res.push_back(k); } sort(res.begin(),res.end()); return res; } };
二、2249.统计圆内格点数目
1、原题链接:
2、解题思路:
根据圆的方程过滤出落在圆上面的点,当满足圆心为(a,b) 半径为r的圆的方程为(x-a)²+(y-b)²<=r²说明点(x,y)在圆内。
3、参考代码:
class Solution { public: int countLatticePoints(vector<vector<int>>& circles) { // 遍历坐标系中的所有点,根据圆的方程过滤出落在圆上面的点 int res = 0; for (int i = 0; i <= 200; i++) { for (int j = 0; j <= 200; j++) { for (auto& circle : circles) { int x = circle[0], y = circle[1], r = circle[2]; // 圆心为(a,b) 半径为r的圆的方程为(x-a)²+(x-b)²=r² if ((i - x) * (i - x) + (j - y) * (j - y) <= r * r) { res++; break; } } } } return res; } };
三、6043.统计包含每个点的矩形数目
1、原题链接:
2、解题思路:
由于这个矩形两个坐标要满足0 <= xj <= li且0 <= yj <= hi,简单的整体排序无法保证两个均满足,又观察到横坐标和纵坐标的范围,因此这里对纵坐标存储,横坐标加入到这个纵坐标对应的vector数组中,然后暴力二分并计数即可
3、参考代码:
class Solution { public: const int maxn = 110; vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) { // 由于横坐标范围较大,此处采用纵坐标作为下标索引,记录纵坐标对应的横坐标集合 vector<vector<int>> a(maxn); int n = points.size(); for (const auto& x: rectangles) { a[x[1]].push_back(x[0]); } // 对每个纵坐标下横坐标进行排序,后面二分找位置 for (int i = 1; i <= 100; ++i) { sort(a[i].begin(), a[i].end()); } vector<int> ans(n, 0); for (int i = 0; i < n; ++i) { int x = points[i][0]; int y = points[i][1]; for (int j = y; j <= 100; ++j) { if (!a[j].empty()) { ans[i] += a[j].size() - (lower_bound(a[j].begin(), a[j].end(), x) - a[j].begin()); } } } return ans; } };
上一篇:
IDEA上Java项目控制台中文乱码