力扣第 444 场周赛

1.1k
Contest
LeetCode
本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。

Q1. 移除最小数对使数组有序 I ​

解题思路 ​

递归，枚举相加最小值和下标，替换后进行递归，满足非递增数组后返回

示例代码 ​

python
class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        if nums == sorted(nums):
            return 0
        mn = inf
        idx = 0
        for i in range(len(nums) - 1):
            if nums[i] + nums[i + 1] < mn:
                mn = nums[i] + nums[i + 1]
                idx = i
        if mn < inf:
            nums[idx: idx + 2] = [mn]
        return self.minimumPairRemoval(nums) + 1

Q2. 设计路由器 ​

解题思路 ​

设计题，packet 记录现存数据包，packet_set 记录现存的数据包，time 记录现存数据包的时间戳

示例代码 ​

python
from sortedcontainers import SortedList
class Router:

    def __init__(self, memoryLimit: int):
        self.limit = memoryLimit
        self.packets = deque()
        self.packet_set = set()
        self.times = defaultdict(SortedList)


    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        packet = (source, destination, timestamp)
        if packet in self.packet_set:
            return False
        if len(self.packets) == self.limit:
            self.forwardPacket()
        self.packets.append(packet)
        self.packet_set.add(packet)
        self.times[destination].add(timestamp)
        return True


    def forwardPacket(self) -> List[int]:
        packet = []
        if len(self.packets):
            packet = self.packets.popleft()
            self.packet_set.remove(packet)
            self.times[packet[1]].discard(packet[-1])
        return packet


    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        pairs = self.times[destination]
        l = pairs.bisect_left(startTime)
        r = pairs.bisect_left(endTime + 1)
        return r - l

# Your Router object will be instantiated and called as such:
# obj = Router(memoryLimit)
# param_1 = obj.addPacket(source,destination,timestamp)
# param_2 = obj.forwardPacket()
# param_3 = obj.getCount(destination,startTime,endTime)
python
class Router:

    def __init__(self, memoryLimit: int):
        self.limit = memoryLimit
        self.packets = deque()
        self.packet_set = set()
        self.times = defaultdict(deque)


    def addPacket(self, source: int, destination: int, timestamp: int) -> bool:
        packet = (source, destination, timestamp)
        if packet in self.packet_set:
            return False
        if len(self.packets) == self.limit:
            self.forwardPacket()
        self.packets.append(packet)
        self.packet_set.add(packet)
        self.times[destination].append(timestamp)
        return True


    def forwardPacket(self) -> List[int]:
        packet = []
        if len(self.packets):
            packet = self.packets.popleft()
            self.packet_set.remove(packet)
            self.times[packet[1]].remove(packet[-1])
        return packet


    def getCount(self, destination: int, startTime: int, endTime: int) -> int:
        pairs = self.times[destination]
        l = bisect_left(pairs, startTime)
        r = bisect_left(pairs, endTime + 1)
        return r - l

# Your Router object will be instantiated and called as such:
# obj = Router(memoryLimit)
# param_1 = obj.addPacket(source,destination,timestamp)
# param_2 = obj.forwardPacket()
# param_3 = obj.getCount(destination,startTime,endTime)

Q3. 最大化交错和为 K 的子序列乘积 ​

解题思路 ​

记忆化搜索，i 表示当前下标，op 表示当前操作符，s 表示当前交错和，mul 表示当前乘积。对 mul 的最值做一个剪枝

同时对 mn[i]做一个预处理，当 mul 大于 limit 时，mn[i]不为 0 时返回-1

示例代码 ​

python
class Solution:
    def maxProduct(self, nums: List[int], k: int, limit: int) -> int:
        n = len(nums)
        mn = [inf] * (n + 1)
        for i in range(n - 1, -1, -1):
            mn[i] = min(mn[i + 1], nums[i])

        @cache
        def dfs(i, op, s, mul):
            res = -1
            if mul > limit and mn[i]:
                return res
            if s == k and mul <= limit and mul > -1:
                res = max(res, mul)
            if i >= n:
                return res
            m = 1 if mul == -1 else mul
            res = max(res, dfs(i + 1, op, s, mul))
            res = max(res, dfs(i + 1, -op, s + op * nums[i], min(limit + 1, m * nums[i])))
            return res
        ans = dfs(0, 1, 0, -1)
        dfs.cache_clear()
        return ans

Q4. 移除最小数对使数组有序 II ​

解题思路 ​

统计逆序对的个数，通过两个 SortedList 维护相邻元素对和最小值，和更新后的下标

删除一个元素（合并后相邻元素对）会影响到前面两个元素和后一个元素，

参考：模拟：两个有序集合

示例代码 ​

python
from sortedcontainers import SortedList
class Solution:
    def minimumPairRemoval(self, nums: List[int]) -> int:
        n = len(nums)
        sl = SortedList()
        idx = SortedList(range(n))
        dec = 0
        for i, (x, y) in enumerate(pairwise(nums)):
            if x > y:
                dec += 1
            sl.add((x + y, i))

        ans = 0
        while dec:
            ans += 1
            s, i = sl.pop(0)
            k = idx.bisect_left(i)

            nxt = idx[k + 1]
            if nums[i] > nums[nxt]:
                dec -= 1
            if k:
                pre = idx[k - 1]
                if nums[pre] > nums[i]:
                    dec -= 1
                if nums[pre] > s:
                    dec += 1
                sl.remove((nums[pre] + nums[i], pre))
                sl.add((nums[pre] + s, pre))
            if k + 2 < len(idx):
                nxtt = idx[k + 2]
                if nums[nxt] > nums[nxtt]:
                    dec -= 1
                if s > nums[nxtt]:
                    dec += 1
                sl.remove((nums[nxt] + nums[nxtt], nxt))
                sl.add((s + nums[nxtt], i))

            nums[i] = s
            idx.remove(nxt)
        return ans
LeetCode Biweekly Contest 154
LeetCode Weekly Contest 443