算法题记录 13

1656.设计有序流（1419）

有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，value 是一个字符串。不存在 id 相同的两个 (id, value) 对。

设计一个流，以 任意 顺序获取 n 个 (id, value) 对，并在多次调用时 按 id 递增的顺序 返回一些值。

实现 OrderedStream 类：

OrderedStream(int n) 构造一个能接收 n 个值的流，并将当前指针 ptr 设为 1 。
String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后：
如果流存储有 id = ptr 的 (id, value) 对，则找出从 id = ptr 开始的 最长 id 连续递增序列 ，并 按顺序 返回与这些 id 关联的值的列表。然后，将 ptr 更新为最后那个 id + 1 。
否则，返回一个空列表。

涉及知识点

看图说话

解决思路

秒答题，看图说话即可。

class OrderedStream:

    def __init__(self, n: int):
        self.a=[""]*(n+1)
        self.ptr=1

    def insert(self, idKey: int, value: str) -> List[str]:
        self.a[idKey]=value
        start=self.ptr
        while self.ptr<len(self.a) and self.a[self.ptr]:
            self.ptr+=1
        return self.a[start:self.ptr]

731.我的日程安排表2（中等）

实现一个程序来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生 三重预订。

事件能够用一对整数 startTime 和 endTime 表示，在一个半开区间的时间 [startTime, endTime) 上预定。实数 x 的范围为 startTime <= x < endTime。

实现 MyCalendarTwo 类：

MyCalendarTwo() 初始化日历对象。
boolean book(int startTime, int endTime) 如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

涉及知识点

看图说话

解决思路

秒答题，看图说话即可。

class MyCalendarTwo:
    def __init__(self):
        self.booked = []  # 存储所有已经成功预定的区间
        self.overlaps = []  # 存储所有重叠的区间

    def book(self, start: int, end: int) -> bool:
        # 检查是否与已有的重叠区间发生冲突
        for s, e in self.overlaps:
            if s < end and start < e:  # 有交集，表示冲突
                return False

        # 查找所有重叠部分
        for s, e in self.booked:
            if s < end and start < e:  # 重叠
                self.overlaps.append((max(s, start), min(e, end)))

        # 当前预定区间可以成功预定
        self.booked.append((start, end))
        return True

2073.买票需要的时间（1325）

有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。

给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。

每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。

返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。

涉及知识点

队列、数学

解决思路

秒答题，可以直接队列模拟，也可以多想一步，用数学也可以解题。

队列

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        ans = 0
        idx = 0
        n = len(tickets)
        # 循环买票
        while tickets[k] != 0:
            if tickets[idx] > 0:
                tickets[idx] -= 1
                ans += 1
            # 下标循环
            idx = (idx + 1) % n
        return ans

数学

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        tk = tickets[k]
        return sum(min(t, tk - (i > k)) for i, t in enumerate(tickets))

3162.优质数对的总数1（1169）

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以除尽 nums2[j] * k，则称数对 (i, j) 为 优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回 优质数对 的总数。

涉及知识点

看图说话

解决思路

秒答题，看图说话即可。

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], k: int) -> int:
        ans=0
        for i in nums1:
            for j in nums2:
                if i%(j*k)==0:
                    ans+=1
        return ans

598.区间加法2（简单）

给你一个 m x n 的矩阵 M 和一个操作数组 op 。矩阵初始化时所有的单元格都为 0 。ops[i] = [ai, bi] 意味着当所有的 0 <= x < ai 和 0 <= y < bi 时， M[x][y] 应该加 1。

在 执行完所有操作后 ，计算并返回 矩阵中最大整数的个数 。

涉及知识点

表格

解决思路

秒答题，稍微思考一下就知道最小区间的数最大。

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        min_a = min((op[0] for op in ops), default=m)
        min_b = min((op[1] for op in ops), default=n)
        return min_a * min_b

3193.统计逆序对的数目（2266）

给你一个整数 n 和一个二维数组 requirements ，其中 requirements[i] = [endi, cnti] 表示这个要求中的末尾下标和 逆序对 的数目。

整数数组 nums 中一个下标对 (i, j) 如果满足以下条件，那么它们被称为一个 逆序对 ：

i < j 且 nums[i] > nums[j]
请你返回 [0, 1, 2, …, n - 1] 的 排列 perm 的数目，满足对 所有 的 requirements[i] 都满足 perm[0..endi] 中恰好有 cnti 个逆序对。

由于答案可能会很大，将它对 10^9 + 7 取余 后返回。

涉及知识点

动态规划

解决思路

有难度，讨论最后一个数填什么：

填2，那么左边不会有比2大的数，这意味着剩下的n−1=2个数的逆序对需要等于2−0=2。（这是不存在的）
填1，那么左边一定有1个比1大的数，这意味着剩下的n−1=2个数的逆序对需要等于2−1=1。（这只有1种构造方式，即[2,0]）
填0，那么左边一定有2个比0大的数，这意味着剩下的n−1=2个数的逆序对需要等于2−2=0。（这只有1种构造方式，即[1,2]）
这些问题都是和原问题相似的、规模更小的子问题，可以用递归解决。

根据上面的讨论，定义dfs(i,j)表示perm[0]到perm[i]（剩余i+1个数）逆序对为j的排列个数。

设perm[i]和左边perm[0]到perm[i−1]组成了k个逆序对：

枚举k=0,1,2,⋯,min(i,j)。其中min(i,j)是因为左边只有i个数，至多和perm[i]组成i个逆序对。
组成了k个逆序对（也就是左边有k个数比perm[i]大），还剩下j−k个逆序对，问题变成perm[0]到perm[i−1]的逆序对为j−k的排列个数，即dfs(i−1,j−k)。

class Solution:
    def numberOfPermutations(self, n: int, requirements: List[List[int]]) -> int:
        MOD = 1_000_000_007
        req = [-1] * n
        req[0] = 0
        for end, cnt in requirements:
            req[end] = cnt
        if req[0]:
            return 0

        @cache  # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
        def dfs(i: int, j: int) -> int:
            if i == 0:
                return 1
            r = req[i - 1]
            if r >= 0:
                return dfs(i - 1, r) if r <= j <= i + r else 0
            return sum(dfs(i - 1, j - k) for k in range(min(i, j) + 1)) % MOD
        return dfs(n - 1, req[-1])

声明

题目均来源于leetcode公开题库，部分方法解析来源于高赞题解，如有不妥请联系。