前言

第290场力扣周赛

感觉都算中等题

第一题

2248.多个数组求交集

2248.多个数组求交集

题解

题目：求多个数组求交集
思路：直接把元素存map中，如果长为数组个数，就说明该元素是交集

代码

func intersection(nums [][]int) []int {n := len(nums)mp := make(map[int]int)for _, v := range nums {for _, vv := range v {mp[vv]++}}var result []intfor k, v := range mp {if v == n {result = append(result, k)}}sort.Ints(result)return result
}

第二题

2249.统计圆内格点数目

2249.统计圆内格点数目

题解

思路：模拟

代码

func countLatticePoints(circles [][]int) int {type pair struct {x, y int}ans := 0result := make(map[pair]bool)for _, circle := range circles {x, y, r := circle[0], circle[1], circle[2]for x1, x2 := x-r, x+r; x1 <= x2; x1++ {for y1, y2 := y-r, y+r; y1 <= y2; y1++ {p := pair{x1, y1}if result[p] == true {continue}long := math.Sqrt(float64((x1-x)*(x1-x) + (y1-y)*(y1-y)))if long <= float64(r) {result[p] = true}}}}for range result {ans++}return ans
}

第三题

2250.统计包含每个点的矩形数目

2250.统计包含每个点的矩形数目

题解

1.贪心，按横坐标排序

1.固定x坐标，将x坐标降序
2.对于点x,y ,统计横坐标不小于x的矩形个数
3.因为高度y不超过100，所有用一个数组存储1~100高度有多少个矩形
4.累加高度大于等于y的矩形个数，就是答案了

2.如果这里y的范围是10^9,那么就不能用累加了，可以用线段树，线段树属于竞赛，面试一般不会用到，这里的思路是按行统计 + 二分查找

1.统计同高度的不同矩形x坐标
2.x坐标从小到大排序
3.二分找出横坐标不小于x的矩形个数

代码

func countRectangles(rectangles [][]int, points [][]int) []int {//按x降序sort.Slice(rectangles, func(i, j int) bool {x1, x2 := rectangles[i], rectangles[j]return x1[0] > x2[0]})//记录point的坐标 point[2]就是坐标for i := range points {points[i] = append(points[i], i)}//按x降序sort.Slice(points, func(i, j int) bool {x1, x2 := points[i], points[j]return x1[0] > x2[0]})result := make([]int, len(points))i, cnt := 0, [101]int{}for _, p := range points {idx := p[2]for ; i < len(rectangles) && rectangles[i][0] >= p[0]; i++ {cnt[rectangles[i][1]]++}for _, c := range cnt[p[1]:] {result[idx] += c}}return result
}

func countRectangles(rectangles [][]int, points [][]int) []int {cnt := [101][]int{}//统计同高度的不同矩形x坐标for _, r := range rectangles {x, y := r[0], r[1]cnt[y] = append(cnt[y], x)}for _, temp := range cnt {sort.Ints(temp) //x坐标从小到大排序}result := make([]int, len(points))for i, p := range points {x, y := p[0], p[1]/*为什么是cnt[y:]，因为(5,5)大于(4,4)，所有要统计大于等于y后面的所有点*/for _, temp := range cnt[y:] {//二分找出横坐标不小于x的下标//长度减去下标即不小于x的矩形个数result[i] += len(temp) - sort.SearchInts(temp, x)}}return result
}

第四题

6044.花期内花的数目

6044.花期内花的数目

题解

思路1：差分

1.flowers[i]就是在[start,end]区间上有一朵花
2.person[i]就是计算在这个时间点时候有几个花
3.因为多次设计区间加减，所以用差分，因为数据量较大所以要离散化
4.将diff升序，persion升序
5.当看花的时间点大于等于某个花开或花落的时间，计算差分
6.当条件不成立时说明前面的差分就是当前时间点花的个数

思路2：贪心+二分

1. 第i个人能看到的花的个数，等于start<=persion[i]的个数 减去 start<persion[i]的个数
2. 即开花数减去凋落数。
3. 所以单独统计开花时间和凋落时间，排序后二分就得到了答案

代码

func fullBloomFlowers(flowers [][]int, persons []int) []int {diff := make(map[int]int)//差分for _, f := range flowers {diff[f[0]]++diff[f[1]+1]--}n := len(diff)//离散化times := make([]int, 0)for t := range diff {times = append(times, t)}//排序，时间从小到大sort.Ints(times)//p[i][0]第i个人看花的时间，p[i][1]第i个人原来的下标p := make([][2]int, len(persons))for i, pp := range persons {p[i] = [2]int{pp, i}}//按照看花的时间从小到大排序sort.Slice(p, func(i, j int) bool {return p[i][0] < p[j][0]})result := make([]int, len(persons))i, sum := 0, 0//遍历看花for _, pp := range p {//看花的时间大于等于某个花开或花落的时间for ; i < n && times[i] <= pp[0]; i++ {//计算差分sum += diff[times[i]]}result[pp[1]] = sum}return result
}

func fullBloomFlowers(flowers [][]int, persons []int) []int {open := make([]int, len(flowers))closes := make([]int, len(flowers))for i, flower := range flowers {open[i] = flower[0]closes[i] = flower[1]}sort.Ints(open)sort.Ints(closes)result := make([]int, len(persons))for i, person := range persons {opNum := sort.SearchInts(open, person+1)clNum := sort.SearchInts(closes, person)result[i] = opNum - clNum}return result
}