LeetCode笔记：Weekly Contest 340

LeetCode笔记：Weekly Contest 340
- 1. 题目一
  - 1. 解题思路
  - 2. 代码实现
- 2. 题目二
  - 1. 解题思路
  - 2. 代码实现
- 3. 题目三
  - 1. 解题思路
  - 2. 代码实现
- 4. 题目四
  - 1. 解题思路
  - 2. 代码实现

比赛链接：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 False
            for i in range(2, int(math.sqrt(num)) + 1):
                if num % i == 0:
                    return False
            return True
        
        n = len(nums)
        res = 0
        for 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, 0
            while i < n-1:
                if nums[i+1] - nums[i] <= k:
                    cnt += 1
                    i += 2
                else:
                    i += 1
                if cnt >= p:
                    break
            return cnt >= p
        
        i, j = -1, nums[-1]-nums[0]
        while j-i > 1:
            m = (i+j) // 2
            if is_possible(m):
                j = m
            else:
                i = m
        return 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, -j
            if i == n-1 and j == m-1:
                return step
            for 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