早起刷题（Day 17）
洪笳淏 Lv4
 2022-04-24 18:00:00      

本文是对 2022.04.24 周赛的回顾

LeetCode6041. 多个数组求交集

#map

题目描述

给你一个二维整数数组 nums ，其中 nums[i] 是由 不同 正整数组成的一个非空数组，按 升序排列 返回一个数组，数组中的每个元素在 nums 所有数组 中都出现过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
示例 1：
输入：nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
输出：[3,4]
解释：
nums[0] = [3,1,2,4,5]，nums[1] = [1,2,3,4]，nums[2] = [3,4,5,6]，在 nums 中每个数组中都出现的数字是 3 和 4 ，所以返回 [3,4] 。

示例 2：
输入：nums = [[1,2,3],[4,5,6]]
输出：[]
解释：
不存在同时出现在 nums[0] 和 nums[1] 的整数，所以返回一个空列表 [] 。
 

提示：
1 <= nums.length <= 1000
1 <= sum(nums[i].length) <= 1000
1 <= nums[i][j] <= 1000
nums[i] 中的所有值 互不相同

解题思路

(1). 统计二维数组中每一个数字出现的次数，使用 map 保存；
(2). 遍历 map，如果数字出现的次数等于 len(nums)，那么说明每一个数组中都出现过该数字；
(3). 对结果进行排序。

时间复杂度

$O(N^2)$

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func intersection(nums [][]int) []int {

	m := make(map[int]int,0)
	n := len(nums)

	for i:=0; i<len(nums); i++ {
		for j:=0; j<len(nums[i]); j++ {
			m[nums[i][j]]++
		}
	}

	ret := []int{}
	for num, v := range m {
		if v == n {
			ret = append(ret, num)
		}
	}

	sort.Ints(ret)

	return ret
}

LeetCode6042. 统计圆内格点数目

#枚举

题目描述

给你一个二维整数数组 circles ，其中 circles[i] = [xi, yi, ri] 表示网格上圆心为 (xi, yi) 且半径为 ri 的第 i 个圆，返回出现在 至少一个 圆内的 格点数目 。
注意：

  • 格点 是指整数坐标对应的点。
  • 圆周上的点 也被视为出现在圆内的点。
1
示例 1:

avatar

1
2
3
4
5
6
7
输入：circles = [[2,2,1]]
输出：5
解释：
给定的圆如上图所示。
出现在圆内的格点为 (1, 2)、(2, 1)、(2, 2)、(2, 3) 和 (3, 2)，在图中用绿色标识。
像 (1, 1) 和 (1, 3) 这样用红色标识的点，并未出现在圆内。
因此，出现在至少一个圆内的格点数目是 5 。
1
示例 2:

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：circles = [[2,2,2],[3,4,1]]
输出：16
解释：
给定的圆如上图所示。
共有 16 个格点出现在至少一个圆内。
其中部分点的坐标是 (0, 2)、(2, 0)、(2, 4)、(3, 2) 和 (4, 4) 。
 

提示：
1 <= circles.length <= 200
circles[i].length == 3
1 <= xi, yi <= 100
1 <= ri <= min(xi, yi)

解题思路

(1). 首先注意本题的数据范围：1 <= circles.length <= 200，那么就可以通过枚举这最多 400 个点来看是否符合情况（当然也可以使用 map 来记录，但是鉴于本题的数据量，直接枚举会更好）；
(2). 先对 circles 数组进行排序，排序的优先级是较大的半径在前，这样就可以囊括更多的点，节约遍历 circles 数组的时间；
(3). 对每个点是否在所有的圆中进行判定，如果在某个圆中，则输出结果 +1。

时间复杂度

$O(400*log(N))$

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func countLatticePoints(circles [][]int) (ans int) {

	// 按半径从大到小排序，这样能更早遇到包含 (x,y) 的圆
	sort.Slice(circles, func(i, j int) bool { return circles[i][2] > circles[j][2] })

	for x := 0; x <= 200; x++ {
		for y := 0; y <= 200; y++ {
			for _, c := range circles {
				// 判断 (x,y) 是否在圆 c 内
				if (x-c[0])*(x-c[0])+(y-c[1])*(y-c[1]) <= c[2]*c[2] {
					ans++
					break
				}
			}
		}
	}

	return
}

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

#二分查找

题目描述

给你一个二维整数数组 rectangles ，其中 $rectangles[i] = [l_i, h_i]$ 表示第 i 个矩形长为 $l_i$ 高为 $h_i$ 。给你一个二维整数数组 $points$ ，其中 $points[j] = [x_j, y_j]$ 是坐标为 $(x_j, y_j)$ 的一个点。
第 i 个矩形的 左下角 在 $(0, 0)$ 处，右上角 在 $(l_i, h_i)$。
请你返回一个整数数组 $count$ ，长度为 $points.length$，其中 $count[j]$是 包含 第 $j$ 个点的矩形数目。
如果 $0 <= x_j <= l_i$ 且 $0 <= y_j <= h_i$ ，那么我们说第 i 个矩形包含第 j 个点。如果一个点刚好在矩形的 边上 ，这个点也被视为被矩形包含。

1
示例 1:

avatar

1
2
3
4
5
6
7
8
9
输入：rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]
输出：[2,1]
解释：
第一个矩形不包含任何点。
第二个矩形只包含一个点 (2, 1) 。
第三个矩形包含点 (2, 1) 和 (1, 4) 。
包含点 (2, 1) 的矩形数目为 2 。
包含点 (1, 4) 的矩形数目为 1 。
所以，我们返回 [2, 1] 。
1
示例 2:

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入：rectangles = [[1,1],[2,2],[3,3]], points = [[1,3],[1,1]]
输出：[1,3]
解释：
第一个矩形只包含点 (1, 1) 。
第二个矩形只包含点 (1, 1) 。
第三个矩形包含点 (1, 3) 和 (1, 1) 。
包含点 (1, 3) 的矩形数目为 1 。
包含点 (1, 1) 的矩形数目为 3 。
所以，我们返回 [1, 3] 。
 
提示：
1 <= rectangles.length, points.length <= 5 * 10^4
rectangles[i].length == points[j].length == 2
1 <= li, xj <= 10^9
1 <= hi, yj <= 100
所有 rectangles 互不相同 。
所有 points 互不相同 。

解题思路

(1). 首先关注一下题目给的数据范围，可以观察到：$1 <= l_i, x_j <= 10^9$，且 $1 <= h_i, y_j <= 100$；
(2). 那么就意味着矩形的高最大也就是 $100$，那么就可以使用二分法，最多在 $y$ 轴上进行 $100$ 次二分就能得出答案；
(3). 首先就是要构造一个二维数组，该数组的外层索引是高度，内层索引是所有是该高度的矩形的宽的列表；
(4). 要使用二分那么就要使得列表有序，为避免重复排序，创建一个 bool 数组来记录是否已经排过序；
(5). 二分法的判断条件是找到第一个 大于等于 点横坐标的索引号，返回的是 列表长度 - 该索引号，表明包含了该点的矩形个数。

解题代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
func countRectangles(rectangles [][]int, points [][]int) []int {

	length := len(rectangles)
	m := make([][]int, 101)
	sorted := make([]bool, 101)

	for i:=0; i<length; i++ {
		x, y := rectangles[i][0], rectangles[i][1]
		for j:=0; j<=y; j++ {
			m[j] = append(m[j], x)
		}
	}

	var judgeCount func([]int, int) int
	judgeCount = func(arr []int, target int) int {
		r := len(arr)-1
		if target > arr[r] {
			return 0
		}

		n := sort.Search(len(arr), func(i int) bool {
			return arr[i] >= target
		})

		if n == len(arr) {
			return 0
		}
		
		return len(arr)-n
	}



	ret := make([]int, len(points))

	for i:=0; i<len(points); i++ {
		x, y := points[i][0], points[i][1]
		if len(m[y]) == 0 {
			continue
		}

		if !sorted[y] {
			sort.Ints(m[y])
			sorted[y] = true
		}

		ret[i] = judgeCount(m[y], x)
	}

	return ret
}

细节问题

  由于出现在 rectangles 数组中的矩形不能囊括所有的纵坐标，所以在更新对应纵坐标的二维数组时，要同时更新小于该纵坐标的二维数组的列表值。

LeetCode6044. 花期内花的数目

#排序 #重合区间

题目描述

给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [starti, endi] 表示第 i 朵花的 花期 从 starti 到 endi （都 包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 persons ，persons[i] 是第 i 个人来看花的时间。
请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的 数目 。

1
示例 1:

avatar

1
2
3
4
5
6
输入：flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
输出：[1,2,2,2]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。

示例 2：

avatar

1
2
3
4
5
6
7
8
9
10
11
输入：flowers = [[1,10],[3,3]], persons = [3,3,2]
输出：[2,2,1]
解释：上图展示了每朵花的花期时间，和每个人的到达时间。
对每个人，我们返回他们到达时在花期内花的数目。

提示：
1 <= flowers.length <= 5 * 10^4
flowers[i].length == 2
1 <= starti <= endi <= 10^9
1 <= persons.length <= 5 * 10^4
1 <= persons[i] <= 10^9

解题思路

(1). 经典问题之求一个点被几个区间覆盖;
(2). 把 flowers[i] 分成两个点：(flowers[i][0], INF) 表示花期的开始，(flowers[i][1], -1*INF) 表示花期的结束。每个询问也看成一个点 (persons[i], i);
(3). 然后对上述组合对进行排序，排序的方式是：首元素小的优先；如果首元素相等，那么第二个元素大的优先；
(4). 上面的规则可以保证在进行统计时开始点在统计前被计算，结束点在统计后被计算；
(5). 维护变量 now，遇到花期开始则 now++，花期结束则 now--，询问则答案就是当前的 now 值；

时间复杂度

$O(Nlog(N))$

解题代码

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
34
35
36
func fullBloomFlowers(flowers [][]int, persons []int) []int {
    const MaxNum = math.MaxInt32
    pair := make([][]int, 0)
    
    for i:=0; i<len(flowers); i++ {
        begin, end := flowers[i][0], flowers[i][1]
        pair = append(pair, []int{begin, MaxNum}, []int{end, -1*MaxNum})
    }
    
    for i:=0; i<len(persons); i++ {
        pair = append(pair, []int{persons[i], i})
    }
    
    sort.Slice(pair, func(i, j int) bool {
        if pair[i][0] == pair[j][0] {
            return pair[i][1] > pair[j][1]
        }
        
        return pair[i][0] < pair[j][0]
    })
    // fmt.Println(pair)
    now := 0
    ret := make([]int, len(persons))
    for i:=0; i<len(pair); i++ {
        l := pair[i]
        if l[1] == -1*MaxNum {
            now--
        } else if l[1] == MaxNum {
            now++
        } else {
            ret[l[1]] = now
        }
    }
    
    return ret
}
  • Post title：早起刷题（Day 17）
  • Post author：洪笳淏
  • Create time：2022-04-24 18:00:00
  • Post link：https://jiahaohong1997.github.io/2022/04/24/早起刷题（Day 17）/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments