2024.5.8 LeetCode 刷题记

面试题 17.14. 最小K个数

题目链接

class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        import heapq
        ans=[]
        for num in arr:
            heapq.heappush(ans,-num)
            if len(ans)>k:
                heapq.heappop(ans)
        return [-num for num in ans]

Python 中 heapq 模块默认是 小顶堆（超出ans容量后，每次弹出最小的元素，保留较大元素）
实现 大顶堆 方法：小顶堆的插入和弹出操作均将元素 取反 即可

若实现最大 K 个数

class Solution:
    def smallestK(self, arr: List[int], k: int) -> List[int]:
        import heapq
        ans=[]
        for num in arr:
            heapq.heappush(ans,num)
            if len(ans)>k:
                heapq.heappop(ans)
        return ans

1365. 有多少小于当前数字的数字

题目链接

计数排序 可能是所有排序里最快的一种，因为它不涉及比较。但是它有个问题就是需要的空间很大。所以一般只涉及数字的时候，还能应付，一旦涉及到字母混数字排序，它就抓瞎了。你总不能搞一个各种字母组合的计数表吧。这个应该是个重点，本题只有0 - 100的数字，就非常适合计数排序。

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        place = [0] * 101
        output = []

        for n in nums:
            place[n] += 1  # 把从0 - 100的所有数的个数都数出来了。

        lessthan = []  # 把从0 - 100的所有数的比它小的数的个数都列出来。
        temp = 0  # 其实就是刚才的place数组的累加
        for p in place:
            lessthan.append(temp)
            temp += p

        for n in nums:  # 最后对应nums把lessthan的值掏出来作为输出。
            output.append(lessthan[n])

        return output

539. 最小时间差

题目链接

根据题意，一共有 24×60=1440 种不同的时间。由鸽巢原理可知，如果 timePoints 的长度超过 1440，那么必然会有两个相同的时间，此时可以直接返回 0。

class Solution:
    def getMinutes(self,t):
        return ((ord(t[0]) - ord('0')) * 10 + ord(t[1]) - ord('0')) * 60 + (ord(t[3]) - ord('0')) * 10 + ord(t[4]) - ord('0')

    def findMinDifference(self, timePoints: List[str]) -> int:
        n = len(timePoints)
        if n > 1440:
            return 0
        timePoints.sort()
        ans = float('inf')
        t0Minutes = self.getMinutes(timePoints[0])
        preMinutes = t0Minutes
        for i in range(1, n):
            minutes = self.getMinutes(timePoints[i])
            ans = min(ans, minutes - preMinutes)  # 相邻时间的时间差
            preMinutes = minutes
        ans = min(ans, t0Minutes+1440-preMinutes)  # 首尾时间的时间差
        return ans

410. 分割数组的最大值

题目链接

「使……最大值尽可能小」是二分搜索题目常见的问法。

本题意思其实就是有一个数组，你要分割成 k 份，每一份都有一个和，这些和当中的最大值
你要让它最小。我们设这个值为 x 。详细题解 参见

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
    	# 用于检查是否能将数组划分为 cnt（<=k）个子数组，且每个子数组的和 total<=x
        def check(x: int) -> bool:
            # total表示当前分割子数组的和
            # cnt表示已经分割出的子数组的数量
            total, cnt = 0, 1
            for num in nums:
                if total + num > x:
                    cnt += 1
                    total = num
                else:
                    total += num
            return cnt <= k

        left = max(nums)
        right = sum(nums)
        while left < right:
            mid = (left + right) // 2
            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left