LeetCode笔记：Weekly Contest 340
- LeetCode笔记：Weekly Contest 340
- 比赛链接：https://leetcode.com/contest/weekly-contest-340/
1. 题目一
给出题目一的试题链接如下：
- 2614. Prime In Diagonal
1. 解题思路
这一题较之以往的第一题来说多少复杂了一些，不过思路上还是很直接的，就是直接考察一下对角线元素，看一下其是不是质数，以及是否比之前的最大值大即可。
2. 代码实现
给出python代码实现如下：
class Solution:def diagonalPrime(self, nums: List[List[int]]) -> int:@lru_cache(None)def is_prime(num):if num < 2:return Falsefor i in range(2, int(math.sqrt(num)) + 1):if num % i == 0:return Falsereturn Truen = len(nums)res = 0for i in range(n):if nums[i][i] > res and is_prime(nums[i][i]):res = nums[i][i]if nums[i][n-1-i] > res and is_prime(nums[i][n-1-i]):res = nums[i][n-1-i]return res
提交代码评测得到：耗时729ms，占用内存26MB。
2. 题目二
给出题目二的试题链接如下：
- 2615. Sum of Distances
1. 解题思路
这一题思路上还是比较直接的，就是将相同元素的index按序聚类，然后对每一个值对应的位置考察对应的distance之和就行。
而对于如何求distance的和，事实上就是分前后用一个分别用累积数组求和即可。
2. 代码实现
给出python代码实现如下：
class Solution:def distance(self, nums: List[int]) -> List[int]:groups = defaultdict(list)for i, k in enumerate(nums):groups[k].append(i)res = [0 for _ in nums]for k, v in groups.items():m = len(v)s = [0] + list(accumulate(v))for i, idx in enumerate(v):res[idx] = idx * i - s[i] + s[-1] - s[i+1] - idx * (m-1-i)return res
提交代码评测得到：耗时891ms，占用内存46.4MB。
3. 题目三
给出题目三的试题链接如下：
- 2616. Minimize the Maximum Difference of Pairs
1. 解题思路
这一题直接求感觉比较难，没啥好的思路，所以就用二分法搜索了一下最小的可能的max diff的值。
2. 代码实现
给出python代码实现如下：
class Solution:def minimizeMax(self, nums: List[int], p: int) -> int:nums = sorted(nums)n = len(nums)def is_possible(k):i, cnt = 0, 0while i < n-1:if nums[i+1] - nums[i] <= k:cnt += 1i += 2else:i += 1if cnt >= p:breakreturn cnt >= pi, j = -1, nums[-1]-nums[0]while j-i > 1:m = (i+j) // 2if is_possible(m):j = melse:i = mreturn j
提交代码评测得到：耗时1210ms，占用内存28.7MB。
4. 题目四
给出题目四的试题链接如下：
- 2617. Minimum Number of Visited Cells in a Grid
1. 解题思路
这一题思路上就是用了一个深度优先遍历。
2. 代码实现
给出python代码实现如下：
class Solution:def minimumVisitedCells(self, grid: List[List[int]]) -> int:n, m = len(grid), len(grid[0])q = [(1, 0, 0)]seen = {(0, 0)}while q:step, i, j = heapq.heappop(q)i, j = -i, -jif i == n-1 and j == m-1:return stepfor k in range(1, grid[i][j]+1):if i+k < n and (i+k, j) not in seen:seen.add((i+k, j))heapq.heappush(q, (step+1, -(i+k), -j))if j+k < m and (i, j+k) not in seen:seen.add((i, j+k))heapq.heappush(q, (step+1, -i, -(j+k)))return -1
提交代码评测得到：耗时5822ms，占用内存56.5MB。