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

• 比赛链接：https://leetcode.com/contest/weekly-contest-334

1. 题目一

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

• 2574. Left and Right Sum Differences

1. 解题思路

这一题用一个累积数组就能够快速求解。

2. 代码实现

给出python代码实现如下：

class Solution:def leftRigthDifference(self, nums: List[int]) -> List[int]:lsum = list(accumulate(nums))s = lsum[-1]res = [abs(x - (s-x+nums[i])) for i, x in enumerate(lsum)]return res

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

2. 题目二

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

• 2575. Find the Divisibility Array of a String

1. 解题思路

这一题就是不断地取前i个字符组成的数对m进行求模即可。

2. 代码实现

给出python代码实现如下：

class Solution:def divisibilityArray(self, word: str, m: int) -> List[int]:res = []s = 0for ch in word:s = (s * 10 + int(ch)) % mif s == 0:res.append(1)else:res.append(0)return res

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

3. 题目三

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

• 2576. Find the Maximum Number of Marked Indices

1. 解题思路

这一题有一点丢脸，本质上这道题就是排序之后给出一个最大的变换构造，但是居然没构造出来，最后是看了答案之后才想到的构造，简直丢脸到家了。

显然，这道题假设数组长度为n，那么最多可以pick的组数至多为$n/2$，因此，我们只要令i都来自于前半组，j都来自于后半组，然后greedy地选出对应可能的pair即可。

2. 代码实现

给出python代码实现如下：

class Solution:def maxNumOfMarkedIndices(self, nums: List[int]) -> int:nums = sorted(nums)n = len(nums)i, j = (n-1) // 2, n-1res = 0while i >= 0 and j > (n-1) // 2:if nums[i]*2 > nums[j]:i-= 1continueres += 2i -= 1j -= 1return res   

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

4. 题目四

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

• 2577. Minimum Time to Visit a Cell In a Grid

1. 解题思路

这一题思路上倒是不复杂，就是一个广度优先遍历，我们用时间t来作为广度判断，来确定遍历顺序，然后扩展直到终点即可。

这里，我们只需要注意以下几个点：

1. 如果第一个点周围的位置都无法访问，那么会导致游客无法行动，只能返回-1，反之，游客总可以在两点间游荡来等到下一个点可以访问，因此绝不会出现-1的情况；
2. 如果某一个点当前无法访问，那么访问该点的时间就是$min(2k+t,t_{open})$;
3. 注意剪枝来优化时间复杂度。

2. 代码实现

给出python代码实现如下：

class Solution:def minimumTime(self, grid: List[List[int]]) -> int:if grid[0][1] > 1 and grid[1][0] > 1:return -1n, m = len(grid), len(grid[0])t_reach = {(0, 0): 0}q = [(grid[0][0], 0, 0)]while q != []:t, x, y = heapq.heappop(q)if t > t_reach.get((x, y), math.inf):continueif (x,y) == (n-1, m-1):return tif x-1 >= 0:nxt = t+1 + 2 * max(0, (grid[x-1][y]-t)//2)if t_reach.get((x-1, y), math.inf) > nxt:heapq.heappush(q, (nxt, x-1, y))t_reach[(x-1, y)] = nxtif x+1 < n:nxt = t+1 + 2 * max(0, (grid[x+1][y]-t)//2)if t_reach.get((x+1, y), math.inf) > nxt:heapq.heappush(q, (nxt, x+1, y))t_reach[(x+1, y)] = nxtif y-1 >= 0:nxt = t+1 + 2 * max(0, (grid[x][y-1]-t)//2)if t_reach.get((x, y-1), math.inf) > nxt:heapq.heappush(q, (nxt, x, y-1))t_reach[(x, y-1)] = nxtif y+1 < m:nxt = t+1 + 2 * max(0, (grid[x][y+1]-t)//2)if t_reach.get((x, y+1), math.inf) > nxt:heapq.heappush(q, (nxt, x, y+1))t_reach[(x, y+1)] = nxtreturn -1

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