已完成题单
枚举
2001. 可互换矩形的组数
用一个下标从 0 开始的二维整数数组 rectangles 来表示 n 个矩形，其中 rectangles[i] = [widthi, heighti] 表示第 i 个矩形的宽度和高度。
如果两个矩形 i 和 j（i < j）的宽高比相同，则认为这两个矩形 可互换。
问题
计算并返回 rectangles 中有多少对 可互换 矩形。
解题思路
将宽高比化简为最简分数，用哈希表统计最简分数的个数。若存在 m 个宽高比相同的矩形，则可互换的矩形对有 m * (m-1) / 2 个。
参考代码
用到的数据结构：cnt := map[[2]int]int64{}
// 如何化简？求 gcd
for a != 0 {
a, b = b%a, a
}
gcd -> b3623. 统计梯形的数目 I
给你一个二维整数数组 points，其中 points[i] = [xi, yi] 表示第 i 个点在笛卡尔平面上的坐标。
水平梯形 是一种凸四边形，具有 至少一对 水平边（即平行于 x 轴的边）。
问题
返回可以从 points 中任意选择四个不同点组成的 水平梯形 数量。答案对 10^9 + 7 取余。
解题思路
1. 统计每一行的节点数
2. 从每一行中选出 2 个节点作为水平边
3. 枚举每一行，设该行有 k = c * (c-1) / 2 条水平边，s 为之前遍历过的行的边数，则一共可以组成 s * k 个水平梯形。
参考代码
func countTrapezoids(points [][]int) (ans int) {
const mod = 1_000_000_007
cnt := make(map[int]int, len(points))
for _, p := range points {
cnt[p[1]]++
}
s := 0
for _, c := range cnt {
k := c * (c - 1) / 2
ans += s * k
s += k
}
return ans % mod
}3371. 识别数组中的最大异常值
给你一个整数数组 nums，其中恰好存在一个异常值。异常值是指在数组中出现次数与其他所有数都不同的值。
问题
返回 nums 中的异常值。若不存在则返回 -1。
解题思路
设异常值为 x，元素和为 y。根据题意：x + 2y = sum(nums)。
问题变为从 nums 中选出两个下标不同的数 x 和 y，求满足条件的最大 x。
参考代码
func getLargestOutlier(nums []int) int {
cnt := map[int]int{}
sum := 0
for _, x := range nums {
cnt[x]++
sum += x
}
ans := math.MinInt
for _, x := range nums {
cnt[x]--
if (sum-x)%2 == 0 && cnt[(sum-x)/2] > 0 {
ans = max(ans, x)
}
cnt[x]++
}
return ans
}更多题目整理中...