前言
第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 []int for 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 := 0 result := 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 }
