leetcode 2251 花期内花的数目（2023.9.28）
题目
给你一个下标从 0 开始的二维整数数组 flowers ，其中 flowers[i] = [starti, endi] 表示第 i 朵花的 花期 从 starti 到 endi （都 包含）。同时给你一个下标从 0 开始大小为 n 的整数数组 people ，people[i] 是第 i 个人来看花的时间。
请你返回一个大小为 n 的整数数组 answer ，其中 answer[i]是第 i 个人到达时在花期内花的 数目 。
1 <= flowers.length <= 5 * 1e4 flowers[i].length == 2 1 <= starti <= endi <= 1e9 1 <= people.length <= 5 * 1e4 1 <= people[i] <= 1e9
题解
这道题乍一看就是差分+前缀和，实际上我写完提交了才发现，区间的范围最大值是1e9，所以得考虑离散化的方案。
感谢房宝给的解法：因为已经提前知道了查询的内容，所以可以做离线，简单来说就是开一个map用来代替差分数组，map记为presum，然后开始处理区间之前，先初始化presum[person[i]] = 0 接下来是走正常的差分流程。 presum[l]++ presum[r + 1]–
最后按照key的大小来排序，求前缀和。因为已经初始化了presum[person[i]] = 0，所以求完前缀和之后presum[person[i]]就是答案。
func fullBloomFlowers(flowers [][]int, people []int) []int {
max := 0
for _, flower := range flowers {
if flower[1] > max {
max = flower[1]
}
}
presum := make(map[int]int)
for _, p := range people {
presum[p] = 0
}
for _, flow := range flowers {
if _, ok := presum[flow[0]]; ok {
presum[flow[0]]++
} else {
presum[flow[0]] = 1
}
if _, ok := presum[flow[1] + 1]; ok {
presum[flow[1] + 1]--
} else {
presum[flow[1] + 1] = -1
}
}
// fmt.Println(presum)
keys := make([]int, 0)
for k, _ := range presum {
keys = append(keys, k)
}
sort.Ints(keys)
for i := 1; i < len(keys); i++{
presum[keys[i]] = presum[keys[i]] + presum[keys[i - 1]]
}
// fmt.Println(presum)
res := make([]int, 0)
for _, p := range people {
res = append(res, presum[p])
}
return res
}
leetcode 947 移除最多的同行或同列石头 2023.09.27
题意
https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column/
n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
示例 1：
输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] 输出：5 解释：一种移除 5 块石头的方法如下所示：
- 移除石头 [2,2] ，因为它和 [2,1] 同行。
- 移除石头 [2,1] ，因为它和 [0,1] 同列。
- 移除石头 [1,2] ，因为它和 [1,0] 同行。
- 移除石头 [1,0] ，因为它和 [0,0] 同列。
- 移除石头 [0,1] ，因为它和 [0,0] 同行。 石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。 示例 2：
输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] 输出：3 解释：一种移除 3 块石头的方法如下所示：
- 移除石头 [2,2] ，因为它和 [2,0] 同行。
- 移除石头 [2,0] ，因为它和 [0,0] 同列。
- 移除石头 [0,2] ，因为它和 [0,0] 同行。 石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。 示例 3：
输入：stones = [[0,0]] 输出：0 解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/most-stones-removed-with-same-row-or-column 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1 <= stones.length <= 1000 0 <= xi, yi <= 1e4
题解
这道题是一个并查集的应用，但问题就在于，如何构建并查集？
主要目的是：让相同列或者相同行的石子处于同一个集合里。一开始思路是把每个石子的x和y放到同一个集合，但提交之后发现这行不通。一个反例就是 [1, 0], [0, 1] 这两个点是不同行且不同列的，如果单纯把x y放同一个集合的话，第一个点1 0一个集合，第二个点0 1一个集合，最终他们会组成一个集合。这就不对了。
这里学习了题解里最巧妙的地方：union(x + 10001, y)，因为x和y的最大取值是1e4，所以让x+10001。这样就能保证，只要两个点的x值是相等的，它们+10001之后也相等，所以他们会落入同一个集合中。并且x的取值范围变成了10001~20001，与y不冲突，所以不会出现上面说的[0,1],[1,0]被加入同一个集合的情况。
另外，因为这道题的取值范围1e4，所以用map来代替并查集的数组会好一些。在本题中还收到另外的启发，集合的个数，可以记录下来。集合的个数=根的个数，一个元素成为了根，集合个数就+1，当一个元素被另外一个集合合并，它就不是根了，集合个数-1。
/*
* @lc app=leetcode.cn id=2251 lang=golang
*
* [2251] 花期内花的数目
*/
package main
import (
"fmt"
"sort"
)
// @lc code=start
func fullBloomFlowers(flowers [][]int, people []int) []int {
max := 0
for _, flower := range flowers {
if flower[1] > max {
max = flower[1]
}
}
presum := make(map[int]int)
for _, p := range people {
presum[p] = 0
}
for _, flow := range flowers {
if _, ok := presum[flow[0]]; ok {
presum[flow[0]]++
} else {
presum[flow[0]] = 1
}
if _, ok := presum[flow[1] + 1]; ok {
presum[flow[1] + 1]--
} else {
presum[flow[1] + 1] = -1
}
}
// fmt.Println(presum)
keys := make([]int, 0)
for k, _ := range presum {
keys = append(keys, k)
}
sort.Ints(keys)
for i := 1; i < len(keys); i++{
presum[keys[i]] = presum[keys[i]] + presum[keys[i - 1]]
}
// fmt.Println(presum)
res := make([]int, 0)
for _, p := range people {
res = append(res, presum[p])
}
return res
}
// @lc code=end
func main() {
flowers := [][]int{
{1, 6},
{3, 7},
{9, 12},
{4, 13},
}
people := []int{
2, 3, 7, 11,
}
fmt.Println(fullBloomFlowers(flowers, people))
}