【Leetcode题解】Weekly Contest 340 周赛题目解析

Posted on Sun 09 April 2023 in Leetcode

Weekly Contest 340

第 340 场周赛

今天题目整体难度有所提升。往常大多数Easy题目都是闭着眼睛两三行搞定，今天竟然直接上求质数。后面的题目也延续了难度，题目看起来人畜无害，在意想不到地方小小的调戏你一下。第二题看起来只是个简单的map题，结果推prefix sum累加公式推了老半天。第三题在看起来像是双指针的题目上给了个二分能解的做法。第四题则是用常规思路一做就TLE的矩阵路径题目。各位读题的时候还是不能掉以轻心，尤其是在周赛的情况下，要是做法选错了不能快速调整的话，基本就双手离开键盘了（这种感觉很难说.jpeg）。

题目列表

2614. Prime In Diagonal 对角线上的质数

按照题意进行模拟即可。这里我们采用了一个朴素的便利方法进行求质数的操作，时间复杂度为\(O(\sqrt(n))\)。最后再按照题意检查对角线。

代码

def isprime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

class Solution:
    def diagonalPrime(self, nums: List[List[int]]) -> int:
        result = 0
        for i in range(len(nums)):
            if isprime(nums[i][i]):
                result = max(result, nums[i][i])
            if isprime(nums[i][len(nums) - i - 1]):
                result = max(result, nums[i][len(nums) - i - 1])
        return result

2615. Sum of Distances 等值距离和

给定一个数组nums，需要返回一个结果数组arr。其中arr[i]的值需要这样求得：对于每一个满足i != j且nums[i] == nums[j]的索引j，求i对于每一个j的绝对值abs(i - j) 的总和。

首先我们的第一反应应该是遍历nums并把值相同的索引归并成列表，然后再对每一个索引列表做上述的计算操作。给定一个索引列表idxs，我们可以用最简单遍历的方式去求上述结果要求的值，但这样最坏情况下的时间复杂度为\(O(n^2)\)。

Example 1
Input: [1, 5, 8, 9]
Output:
1: 3 + 6 + 7 - 3 * 1 =>  19
5: (5 - 1) + (8 + 9 - 5 * 2)= 11
8: (8 * 2 - 1 - 5) + (9 - 8) = 11
9: 9 * 3 - 1 - 5 - 8 = 13

这里从例子中我们可以看到，上述的操作我们可以分为两部分，并且其中都包括对于idxs一个连续部分求和的操作。、假设对于索引i在idxs的位置为k，那么左边部分的结果就是left = i * k - sum(idxs[:k])，右边部分的结果为right = sum(idxs[k + 1:]) - i * (len(idxs) - k)。我们有两个求和操作，因此考虑用前缀和去求解。至于对于找到i在idxs的位置k，因为我们构建的时候顺序遍历数组找到的idx是顺序的，我们可以直接用二分搜索。

代码

def prefixsum(l):
    prefix = [0] * (len(l) + 1)
    for i, n in enumerate(l):
        prefix[i + 1] = prefix[i] + n
    return prefix

class Solution:
    def distance(self, nums: List[int]) -> List[int]:
        d = defaultdict(list)
        for i, n in enumerate(nums):
            d[n].append(i)

        prefix = {n : prefixsum(l) for n, l in d.items()}

        result = [0] * len(nums)

        for i, n in enumerate(nums):
            idx = bisect_left(d[n], i)

            # print(i, n, d[n], idx, prefix[n], prefix[n][idx - 1])
            left = i * idx - prefix[n][idx]
            right = (prefix[n][-1] - prefix[n][idx]) - i * (len(d[n]) - idx)

            # print("\t", left, right)
            result[i] += left + right
        return result

2616. Minimize the Maximum Difference of Pairs 最小化数对的最大差值

给定一个数组nums和数字p，我们要在数组中匹配p对数使得所有对的差值的绝对值最小化。返回这p对数中最大的。此外，要注意每个数字只能使用一次。

对于给定的数组，我们可以对数组排序，那么前后两个数肯定是最小的。乍一看有点像是直接使用贪心的进行匹配，但是贪心并不能匹配到最优解。我们看一个例子。

Example 1
Input: arr = [1, 5, 5, 7], p = 2
Output: 1

如果我们贪心匹配的话可能会得到[5,5],[1,7] => 6的差值，但实际最优解是[1,5], [5,7] => 4。此外，p的这个限制也比较困难，因为每个数字只能使用一次。如果我们能把最大值固定下来，是不是更好找呢？假设我们有一个固定的m最大值，我们可以通过贪心的判断nums[i] - nums[j] < m，从而判断是否将这部分数组囊括到最多p对数值里面。有了这个快速判断的方法，我们可以进一步使用二分搜索去寻找这个m。

代码

class Solution:
    def minimizeMax(self, nums: List[int], p: int) -> int:
        def check(m):
            k = 0
            i = 1
            while i < len(nums) and k < p:
                # print(i, nums[i], nums[i - 1])
                if nums[i] - nums[i - 1] <= m:
                    k += 1
                    i += 1
                i += 1
            return k >= p

        nums.sort()

        left = 0
        right = nums[-1] - nums[0] + 1

        while left < right:
            mid = left + (right - left) // 2

            if check(mid):
                right = mid
            else:
                left = mid + 1
        return left

2617. Minimum Number of Visited Cells in a Grid 网格图中最少访问的格子数

给定一个m x n的矩阵grid，一开始出生点为左上角(0,0)。在每一个点(i, j)，我们可以向下或者向右走，可走到的格子跟grid[i][j]的值相关，

  • 向右走：(i, k)且j < k <= grid[i][j] + j
  • 向下走：(k, j)且i < k <= grid[i][j] + i

要求找到最少需要经过多少个格子才能走到右下角(m - 1, n - 1)。

这道题乍一看是简单的BFS或者DP，因为子问题组成了后续问题的答案。但我们不得不解决的一个问题是，我们不得不遍历[j, min(grid[i][j] + j, n)]或者[i, min(grid[i][j] + i, m)]个点去更新状态。这样的话总共时间复杂度为\(O(m * n * (m + n))\)，不可避免会TLE。因此我们想想能不能优化O(m + n)这一项。因为我们只要求最少的格子，使用BFS的方式，若i -> k先于j -> k出现的话，那么i -> k这一步的结果一定优于j -> k。这里可以类比一个无权重的图，先走到的那个步数一定最小。那么我们在找j的下一步的时候，其实是不用考虑之前已经经过的点k的。此外，我们也可以观察到，给定当前的行或者列，我们都是取连续的一段数作为我们下一个目标，因此我们这里使用维护sortedlist作为当前未被遍历到的行或者列，可以在\(O(log(n))\)时间找到连续的区间。剩下的就跟普通的BFS一样了。

代码

from sortedcontainers import SortedList

class Solution:
    def minimumVisitedCells(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        s0 = [SortedList(range(n)) for _ in range(m)]
        s1 = [SortedList(range(m)) for _ in range(n)]

        q = deque([(0, 0, 1)])

        while q:
            i, j, steps = q.popleft()

            if (i, j) == (m - 1, n -1):
                return steps

            for k in list(s0[i].irange(j + 1, min(j + grid[i][j], n - 1))):
                q.append((i, k, steps + 1))
                s0[i].remove(k)
                s1[k].remove(i)

            for k in list(s1[j].irange(i + 1, min(i + grid[i][j], m - 1))):
                q.append((k, j, steps + 1))
                s1[j].remove(k)
                s0[k].remove(j)
        return -1

小结

如果你想变得更强的话，可以做做

Contest