# # Leetcode 第290场周赛题解

## # Problem A - 多个数组求交集 (opens new window)

### # 方法一：模拟

class Solution:
def intersection(self, nums: List[List[int]]) -> List[int]:
return sorted(list(functools.reduce(lambda a, x: a & x, map(set, nums))))

1
2
3

## # Problem B - 统计圆内格点数目 (opens new window)

### # 方法一：暴力

• 时间复杂度 $\mathcal{O}(NRC)$$R$$C$ 为行列方向的搜索范围。
• 空间复杂度 $\mathcal{O}(1)$

class Solution:
def countLatticePoints(self, circles: List[List[int]]) -> int:
xmin = min(x - r for x, y, r in circles)
xmax = max(x + r for x, y, r in circles)
ymin = min(y - r for x, y, r in circles)
ymax = max(y + r for x, y, r in circles)
ans = 0
for x in range(xmin, xmax + 1):
for y in range(ymin, ymax + 1):
found = False
for xi, yi, r in circles:
if (x - xi) ** 2 + (y - yi) ** 2 <= r ** 2:
found = True
break
if found:
ans += 1
return ans

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

## # Problem C - 统计包含每个点的矩形数目 (opens new window)

### # 方法一：沿 y 方向枚举

• 时间复杂度 $\mathcal{O}(N\log N+M\log M+MY_{\max}\log N)$
• 空间复杂度 $\mathcal{O}(N+M+Y_{\max})$

class Solution {
public:
vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
int n = rectangles.size(), m = points.size();
int ymax = 0;
for (int i = 0; i < n; ++i)
ymax = max(ymax, rectangles[i][1]);
for (int i = 0; i < m; ++i)
ymax = max(ymax, points[i][1]);
vector<vector<int>> y(ymax + 1);
for (int i = 0; i < n; ++i) {
y[rectangles[i][1]].push_back(rectangles[i][0]);
}
for (int i = 0; i <= ymax; ++i)
sort(y[i].begin(), y[i].end());
vector<int> ans(m);
for (int i = 0; i < m; ++i) {
for (int j = points[i][1]; j <= ymax; ++j) {
ans[i] += y[j].end() - upper_bound(y[j].begin(), y[j].end(), points[i][0] - 1);
}
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

### # 方法二：双指针+平衡二叉搜索树

• 时间复杂度 $\mathcal{O}(N\log N+M\log M+(M+N)\log \min(N, Y_{\max}))$
• 空间复杂度 $\mathcal{O}(N+M)$

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

class Solution {
public:
vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
int n = rectangles.size(), m = points.size();
sort(rectangles.rbegin(), rectangles.rend());
vector<int> order(m);
for (int i = 0; i < m; ++i)
order[i] = i;
sort(order.begin(), order.end(), [&](int i, int j){
return points[i][0] > points[j][0];
});
vector<int> ans(m);
ordered_set os;
int ptr = 0;
for (int i = 0; i < m; ++i) {
int id = order[i];
while (ptr < n && rectangles[ptr][0] >= points[id][0]) {
os.insert(rectangles[ptr][1]);
ptr++;
}
ans[id] = (int)os.size() - os.order_of_key(points[id][1]);
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

## # Problem D - 花期内花的数目 (opens new window)

### # 方法一：双指针 + 小根堆

• 时间复杂度 $\mathcal{O}((N+M)\log N + M\log M)$
• 空间复杂度 $\mathcal{O}(N+M)$

class Solution {
public:
vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
int n = flowers.size(), m = persons.size();
vector<int> ans(m);
vector<int> order(m);
for (int i = 0; i < m; ++i)
order[i] = i;
sort(order.begin(), order.end(), [&](int i, int j) {
return persons[i] < persons[j];
});

sort(flowers.begin(), flowers.end());
int ptr = 0;
priority_queue<int, vector<int>, greater<>> pq;
for (int i = 0; i < m; ++i) {
int idx = order[i];
while (ptr < n && flowers[ptr][0] <= persons[idx]) {
pq.push(flowers[ptr][1]);
ptr++;
}
while (!pq.empty() && pq.top() < persons[idx])
pq.pop();
ans[idx] = pq.size();
}

return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29