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

发表于2025-12-02|更新于2025-12-03|力扣日常 | LeetcodeDaily

|总字数:267|阅读时长:1分钟|浏览量:

题目浅析

想查看原题可以点击题目链接。
简单地说，就是给一组点，用这些点组成至少有一对水平边的水平梯形，求组合数

思路分享

由于有一组边必须与 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

文章作者: 陆爻齐-LuYaoQi

文章链接: http://hslix.github.io/posts/5a2c272e.html

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！

Algorithm 枚举哈希表

相关推荐

【Leetcode Daily】1128等价多米诺骨牌对的数量

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个元素为长度2的vector的vector，找出其中所有元素 vector 相同的对数，其中相同指的是两个 vector，各个元素相同，或者第一个元素与另一个的第二个相同，剩余两个相同。思路分享用二维数组当哈希表记录即可，可以选择对一个数对维护两个哈希表位，但哈希表的维护消耗资源其实不小，所以直接调整数对统一数对中的大小相对顺序，就只要用一个位置对应一个数对。比如把（2，1）转化为（1，2）来看。 C++中，可以通过 minmax 构建一个第一个元素小于第二个元素的 pair。 https://leetcode.cn/problems/number-of-equivalent-domino-pairs/solutions/3661647/mei-ju-you-wei-hu-zuo-pythonjavaccgojsru-me3c/ O(n) 枚举的基本思想可以看【Leetcode Daily】1两数之和。代码解答（强烈建议自行解答后再看）参考题解 123456789101112class...

【Leetcode Daily】121买卖股票的最佳时机-枚举

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个整型数组，说这里的每个数字都是股票加个，你可以在任意时期购买股票并在后面卖出一次，请给出最大利润，若无利润则返回 0. 思路分享本题可以用动态规划或枚举的方法解决，这里介绍枚举的方法。可以遍历数字，从左到右，视为找最大值，同时引入一变量记录目前左侧的最小值，不断计算当前最小值与最右值的差的最大值，就能得到答案。 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/solutions/2464650/mei-ju-mai-chu-jie-ge-wei-hu-mai-ru-de-z-02ud/ 无需哈希表，毕竟用记录最小值即可。基础的枚举思路可看【Leetcode Daily】1两数之和。代码解答（强烈建议自行解答后再看）参考题解 123456789101112class Solution {public: int maxProfit(vector<int>& prices) {...

【Leetcode Daily】1512好数对的数目

题目浅析想查看原题可以点击题目链接。简单地说，就是找出数组中所有数值相同的数对（好数对）数目，但是数对内的两个值下标不能相同，且交换位置仍视作一个数对。思路分享本题就是很基础的枚举题，如果暴力方法就是一个循环遍历数对左侧，另一循环遍历右侧，复杂度为 O(n^2)。而相对高效的枚举方法为，只用一次循环，遍历到的数字记录到哈希表上各个数值出现的频次，每次遇到一个值，就可以查其左边有多少相同值，也就出现了多少的好数对。换句话，就是遍历数对的右侧值，并以 O(1) 的复杂度记录其左侧的情况。枚举的思路以及先记录答案再更新记录的原因可看【Leetcode Daily】1两数之和...

【Leetcode Daily】1524和为奇数的子数组数目

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个整数数组，要求这个数组中所有子数组中和为奇数的数目。思路分享前缀和的思路，可以参考【Leetcode Daily】303区域和检索-数组不可变虽然是陆爻齐自己思考了出来，但如果没有提前知道是前缀和区域，应该是做不出来的。回忆解题的过程，就是思考如何快速判定奇数区域时，对做了前缀和了数组观察偶然发现，只要记录此前的奇数和偶数的数目，就能方便地计算现有的数字与此前数字之前区域的和为奇数的数目。代码解答（强烈建议自行解答后再看）参考题解 123456789101112131415class Solution: def numOfSubarrays(self, arr: List[int]) -> int: s = list(accumulate(arr, initial=0)) even_num = 0 odd_num = 0 ans = 0 for i in s: if i%2 == 0: ...

【Leetcode Daily】1590使数组和能被P整除

题目浅析想查看原题可以点击题目链接。简单地说，就是给一个数组和数字 p，现在可以移除数组内的最短长度的子数组，使得数组和能被 p 整除。思路分享本质上就是找到子数组和能与总数组和同余时，长度最小的情况。对于找子数组的前缀和区间两侧：(right - left)%p = num, (right-num)%p = left%p。那么遍历前缀和，通过哈希表就能方便得记录前面子数组的余数情况，如果有匹配的左侧子数组，就记录当前长度。 https://leetcode.cn/problems/make-sum-divisible-by-p/solutions/2158435/tao-lu-qian-zhui-he-ha-xi-biao-pythonjav-rzl0/?envType=daily-question&envId=2025-11-30 代码解答（强烈建议自行解答后再看）参考题解 1234567891011121314class Solution: def minSubarray(self, nums:...

【Leetcode Daily】16-24数对和

题目浅析想查看原题可以点击题目链接。简单地说，就是找出一个整型数组中所有的数对（元素为2的整型数组），这些数对的数值之和为 target 思路分享在昨天题目（【Leetcode Daily】1679K和数对的最大数目）的基础上，不要求数对个数，而是求每个数对的内容，所以只要把记录个数的语句换成记录数对内容的语句即可，不多赘述。 O(n) 枚举的基本思想可以看【Leetcode Daily】1两数之和。代码解答（强烈建议自行解答后再看）参考题解 1234567891011class Solution: def pairSums(self, nums: List[int], target: int) -> List[List[int]]: rec = Counter() res = [] for num in nums: if rec[target-num]: rec[target-num] -= 1 ...

数据加载中