提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

LeetCode笔记：Biweekly Contest 67

笔记 代码
2023-04-18 15:56:45 时间

1. 题目一

给出题目一的试题链接如下：

1. 解题思路

这一题思路其实还好，其实就是找到最大的k个数，然后构成一个子集进行输出，但是需要注意的是，返回的序列需要保持其原始的顺序，因此我们在排序时需要首先保留其原始的位置信息，然后根据位置信息恢复其原始的排序。

2. 代码实现

给出python代码实现如下：

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        nums = [(i, k) for i, k in enumerate(nums)]
        nums = sorted(nums, key=lambda x: x[1])[-k:]
        return [x[1] for x in sorted(nums, key=lambda x: x[0])]

提交代码评测得到：耗时48ms，占用内存14.4MB。

2. 题目二

给出题目二的试题链接如下：

1. 解题思路

这一题我们的思路同样也比较直接，就是直接考察每一个位置左侧和右侧守卫不多于当日的日子的数目，然后只需要满足左右均多于目标值time的日子进行返回即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
        n = len(security)
        down = [0 for _ in range(n)]
        up = [0 for _ in range(n)]
        for i in range(n-1):
            if security[i] >= security[i+1]:
                down[i+1] = down[i] + 1
            if security[n-1-i] >= security[n-2-i]:
                up[n-2-i] = up[n-1-i] + 1
        
        is_good = [i for i in range(n) if up[i] >= time and down[i] >= time]
        return is_good

提交代码评测得到：耗时1120ms，占用内存33.9MB。

3. 题目三

给出题目三的试题链接如下：

1. 解题思路

这一题我的思路也比较暴力，就是先通过一个二重循环找到每一个炸弹可以蔓延开的炸弹，然后通过一个深度优先遍历即可找到每一个炸弹引爆时可以引爆的总的炸弹数。

2. 代码实现

给出python代码实现如下：

class Solution:
    def maximumDetonation(self, bombs: List[List[int]]) -> int:
        n = len(bombs)
        cover = defaultdict(list)
        for i, (x, y, r) in enumerate(bombs):
            for j in range(n):
                if j == i:
                    continue
                x1, y1, _ = bombs[j]
                if (x-x1)**2 + (y-y1)**2 <= r*r:
                    cover[i].append(j)
        
        def dfs(u, seen):
            for v in cover[u]:
                if v not in seen:
                    seen.add(v)
                    dfs(v, seen)
            return len(seen)
        
        return max(dfs(i, {i}) for i in range(n))

提交代码评测得到：耗时784ms，占用内存14.8MB。

4. 题目四

给出题目四的试题链接如下：

1. 解题思路

这一题坦率地说没看出来为啥是一个hard的题目，维护一个有序数组即可完成了。

2. 代码实现

给出python代码实现如下：

class SORTracker:

    def __init__(self):
        self.idx = 0
        self.q = []

    def add(self, name: str, score: int) -> None:
        bisect.insort(self.q, (-score, name))

    def get(self) -> str:
        res = self.q[self.idx][1]
        self.idx += 1
        return res

提交代码评测得到：耗时1360ms，占用内存37.4MB。

相关文章