【Leetcode Daily】3623统计梯形的数目I

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一组点，用这些点组成至少有一对水平边的水平梯形，求组合数

思路分享

• 由于有一组边必须与 x 轴平行，所以可以记录每一行的点数，然后每一行的点两两组合就有 i*(i-1)//2 种，接着每两行的组合数相乘就是这两行的水平梯形的个数。由于最坏情况下，两行之间的水平梯形的个数也不超过 9*10^18， 不超过 64 位数字的最大值，所以可以不用在循环里面取模。

  https://leetcode.cn/problems/count-number-of-trapezoids-i/solutions/3728518/mei-ju-you-wei-hu-zuo-pythonjavacgo-by-e-lwnv/?envType=daily-question&envId=2025-12-02

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        MOD = 1_000_000_007
        rec = Counter(p[1] for p in points)
        ans = other = 0
        for i in rec.values():
            com = i*(i-1)//2 
            ans += other * com
            other += com
            ans %= MOD
            other %= MOD
        return ans % MOD