目录
Solution?3:?SegmentTree?logN 线段树
第一题?6041. 多个数组求交集
我的Solution
遍历每个数组维护一个Set，然后去重，用到了函数
retainAll()
用法:
public boolean retainAll(Collection c)
参数：此方法将集合c作为包含要从该集合保留的元素的参数。
class Solution {
public List<Integer> intersection(int[][] nums) {
Set<Integer> set = new HashSet<>();
int n = nums.length;
List<Integer> res = new ArrayList<>();
for(int num:nums[0]){
set.add(num);
}
Set<Integer> tmpSet = new HashSet<>();
for(int i=1;i<n;i++){
tmpSet.clear();
for(int num:nums[i]){
tmpSet.add(num);
}
set.retainAll(tmpSet);
}
for(int num:set){
res.add(num);
}
Collections.sort(res);
return res;
}
}Solution2 直接计数
由于题目中条件说明 每个集合中数字没有重复，所以可以直接计数，且
1 <= nums[i][j] <= 1000 所以可以直接用数组计数
交集 是 出现次数 == 集合数量 的那些元素
class Solution {
public List<Integer> intersection(int[][] nums) {
List<Integer> res = new ArrayList<>();
int [] count = new int[1001];
for(int i=0;i<nums.length;i++){
for(int num:nums[i]){
count[num]++;
}
}
for(int i=1;i<=1000;i++){
if(count[i] == nums.length){
res.add(i);
}
}
return res;
}
}第二题?6042. 统计圆内格点数目
我的思路
每个circle枚举，使用set存，新建了坐标class，属于是复杂了就不在这里放代码了，后来学习到可以通过i*1000+j这种方式将坐标转换成数，方便用set去重。
class Solution {
public int countLatticePoints(int[][] circles) {
Set<Integer> set = new HashSet<>();
int n = circles.length;
for(int i=0;i<n;i++){
int x = circles[i][0];
int y = circles[i][1];
int r = circles[i][2];
for(int xx=x-r;xx<=x+r;xx++){
for(int yy=y-r;yy<=y+r;yy++){
if((xx-x)*(xx-x)+(yy-y)*(yy-y) <= r*r){
set.add(xx*1000+yy); //二维坐标展平
}
}
}
}
return set.size();
}
}根据题目数据范围直接暴力枚举求
暴力枚举Solution?
根据题目数据范围直接暴力枚举求? 参考的题解
class Solution {
public int countLatticePoints(int[][] circles) {
int ret = 0;
for(int x = -100;x <= 200;x++){
for(int y = -100;y <= 200;y++){
for(int[] c : circles){
if((c[0] - x) * (c[0] - x) + (c[1] - y) * (c[1] - y) <= c[2]*c[2]){
ret++;
break;
}
}
}
}
return ret;
}
}第三题?
我的思路
直接暴力，TLE
Solution 排序
观察数据范围发现 h数据范围比较小
1 <= hi, yj?<= 100
可以先按照横坐标排序，然后处理
我们考虑将矩形右上角和点的坐标放入同一个数组中，并对数组按照 横坐标 进行排序，如果矩形右上角点的 横坐标 与点的 横坐标 相等，我们考虑把矩形右上角的点 放在前面 。
接着我们考虑以下处理方法。
依次遍历数组中的元素：
1、如果该元素为 矩形的右上角 ：
我们将该矩形的 纵坐标 添加到一个容器中。2、如果当前元素为 点 ：
由于我们数组中的元素是按照 横坐标 排序的，所以 已处理 的元素的 横坐标 都要大于等于当前点的横坐标， 未处理 的元素的 横坐标 都要小于当前点，不需要考虑，所以我们只需要考虑 已处理 的元素，即在容器中查询：“大于等于当前点 纵坐标 的元素数量”即可。作者：Class_
链接：https://leetcode-cn.com/problems/count-number-of-rectangles-containing-each-point/solution/by-class_-jbc6/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution {
public int[] countRectangles(int[][] rectangles, int[][] points) {
int n = rectangles.length, Q = points.length;
int[][] es = new int[n+Q][];
for(int i = 0;i < n;i++){
es[i] = rectangles[i];
}
for(int i = 0;i < Q;i++){
es[n+i] = new int[]{points[i][0], points[i][1], i};
}
//把矩形和坐标放在一起排序
Arrays.sort(es, (x, y) -> {
if (x[0] != y[0]) return -(x[0] - y[0]);
return x.length - y.length;
});
int[] ct = new int[101]; //统计小于等于高度h的矩形数量
int[] ans = new int[Q];
for(int[] e : es){
if(e.length == 2){
for(int i = 0;i <= e[1];i++){
ct[i]++;
}
}else{
//统计结果 e2是query的idx e1是坐标的高度
// 由于按横坐标降序 所以不用考虑横坐标
ans[e[2]] = ct[e[1]];
}
}
return ans;
}
}
//Solution 排序+二分
第四题 6044. 花期内花的数目
我的思考
一开始我的思路是用差分数组，可以很快的修改一段区间的值，显然我没有注意到数据的范围，由于
1 <= starti?<= endi?<= 10^9
所以这种方法内存不够，应该考虑其他的方法如扫描线，二分搜索等。
Solution 1: 扫描线
所有数据对时间排序，依次处理
开花，看花，谢花
排序可以用优先队列实现，实现方法多种多样
数据结构：?PriorityQueue/TreeMap/Arrays/ArrayList
https://leetcode.com/problems/number-of-flowers-in-full-bloom/discuss/1976812/Sweep-Line-Process-Events-from-left-to-right-(Minimum-Platforms-Meetting-Rooms)class Solution {
private static final int START = 0;
private static final int PERSON = 1;
private static final int END = 2;
private static class Event implements Comparable<Event> {
int x; // time of event
int index; // only required if the event is of type person
int type; // type of event, START, END, OR PERSON
public Event(int x, int index, int type) {
this.x = x;
this.index = index;
this.type = type;
}
@Override
public int compareTo(Event other) {
// if x values are different, sort by x
if(x < other.x) {
return -1;
}
if(x > other.x) {
return 1;
}
// if same x values, sort by the priority priority(START) > priority(PERSON) > priority(END)
return this.type - other.type;
}
}
public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
List<Event> list = new ArrayList<>();
// add all the start and end events
for (int[] flower : flowers) {
list.add(new Event(flower[0], -1, START));
list.add(new Event(flower[1], -1, END));
}
// add all the person events
for(int i = 0; i < persons.length; i++) {
list.add(new Event(persons[i], i, PERSON));
}
Collections.sort(list);
// number of flowers in full bloom as we sweep through the events
int count = 0;
int[] res = new int[persons.length];
for(Event e : list) {
// if we come across a start event, the number of flowers that are in full bloom increases
if(e.type == START) {
count ++;
}
// if we come across an end event, the number of flowers that are in full bloom decreases
else if(e.type == END) {
count --;
}
// if we come across a person, then he sees how many ever flowers that are in full bloom now
else {
res[e.index] = count;
}
}
return res;
}
}public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
/*3 events:
0 - Bloom
1 - Person
2 - Die
*/
//{time position, event type, if person -> index}
//first sort by time, then by event type
Queue<int[]> pq = new PriorityQueue<>((a,b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
//add the person events
for(int i = 0; i < persons.length; i++){
//for person also add what index they were - {time position, human, index}
pq.offer(new int[]{persons[i], 1, i});
}
//add the blossom events
for(int[] flower : flowers){
pq.offer(new int[]{flower[0], 0});
pq.offer(new int[]{flower[1], 2});
}
//traverse them all
int[] ret = new int[persons.length];
int numEvents = pq.size();
int blooms = 0;
for(int i = 0; i < numEvents; i++){
int[] cur = pq.poll();
//if bloom, increment blooms
if(cur[1] == 0){
blooms++;
//if die, decrement blooms
}else if(cur[1] == 2){
blooms--;
//if person, set their index to # blooms
}else{
int personIndex = cur[2];
ret[personIndex] = blooms;
}
}
return ret;
}
????
Solution 2: 二分
开花时间排序，找到开过的花
谢花时间排序，找到谢过的花
开过的花?-?谢过的花
复习二分模板：
https://sumygg.com/2017/09/08/upper-bound-and-lower-bound-in-java/upper_bound():返回的是被查序列中第一个大于查找值得指针；
lower_bound()：返回的是被查序列中第一个大于等于查找值的指针；
1、upper_bound【c++中api】
查找排序数组中第一个大于target的数组下标
用法：int t=upper_bound(a+l,a+r,target)-a
解释：在升序排列的a数组内二分查找[l,r)区间内的值为target的元素。返回m在数组中的下标+1。
特殊情况：
1.如果target在区间中没有出现过，那么返回第一个比m大的数的下标。
2.如果target比所有区间内的数都大，那么返回r。这个时候会越界，小心。
3.如果区间内有多个相同的target，返回最后一个target的下标+1。
时间复杂度：
一次查询O(log n)，n为数组长度
java实现:
public int upper_bound(int[] nums, int begin, int end, int target) { //[begin,end)
while (begin < end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] <= target) {
begin = mid + 1;
} else {
end = mid;
}
}
return begin;
}2、
lower_bound；【c++中api】
用法：int t=lower_bound(a+l,a+r,target)-a
解释：在升序排列的a数组内二分查找[l,r)区间内的值为target的元素。返回m在数组中的下标。
特殊情况：
1.如果m在区间中没有出现过，那么返回第一个比m大的数的下标。
2.如果m比所有区间内的数都大，那么返回r。这个时候会越界，小心。
3.如果区间内有多个相同的m，返回第一个m的下标。
时间复杂度：
一次查询O(log n)，n为数组长度。
java实现:
public int lower_bound(int[] nums, int begin, int end, int target) {
while (begin < end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] < target) {
begin = mid + 1;
} else {
end = mid;
}
}
return begin;
}class Solution {
public int[] fullBloomFlowers(int[][] flowers, int[] persons) {
int n = flowers.length;
int[] flower_begin = new int[n];
int[] flower_end = new int[n];
for(int i=0;i<n;i++){
flower_begin[i] = flowers[i][0];
flower_end[i] =flowers[i][1];
}
//分别排序花开 花谢时间
Arrays.sort(flower_begin);
Arrays.sort(flower_end);
int[] res = new int[persons.length];
for(int i=0;i<persons.length;i++){
int begin = upper_bound(flower_begin,0,n,persons[i]);
int end = lower_bound(flower_end,0,n,persons[i]);
res[i] = begin - end;
}
return res;
}
//在[begin,end)中找第一个大于等于value的数的index
public int lower_bound(int[] nums, int begin, int end, int value) {
while (begin < end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] < value) {
begin = mid + 1;
} else {
end = mid;
}
}
return begin;
}
//在[begin,end)中找第一个大于value的数的index
public int upper_bound(int[] nums, int begin, int end, int value) {
while (begin < end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] <= value) {
begin = mid + 1;
} else {
end = mid;
}
}
return begin;
}
}
????
????
Solution?3:?SegmentTree?logN 线段树
不要求熟练的掌握
????对所有花区间修改，对所有person进行query
