Leetcode周赛 | 2023-8-6

题1

体会

这道题完全就是唬人，只要想明白了，只要有两个连续的数的和，大于target，那么一定可以，两边一次切一个就好了。

我的代码

题2

我的超时代码

尽力了，想不出来别的方法，只能通过一半的测试用例，其他超时。

将向左和向下的代码去掉后，因为我觉得向左和向右是无意义的，通过的用例多了一些，但还是超时。

class Solution:def maximumSafenessFactor(self, grid: List[List[int]]) -> int:note = []m = len(grid)n = len(grid[0])for i in range(m):for j in range(n):if grid[i][j] == 1 :note.append([i,j])if i == 0 and j == 0 :return 0if i == m-1 and j == n-1 :return 0self.mm = 0i = j = 0mini = infself.dfs(grid,i,j,mini,note,m,n)return self.mmdef dfs(self,grid,i,j,mini,note,m,n):if i < 0 or i >= m or j < 0 or j >= n :returnif grid[i][j] == 2 :returntemp = [[p[0]-i,p[1]-j] for p in note]     for k in temp :mini = min(mini,abs(k[0])+abs(k[1]))if mini <= self.mm :returnif i == m-1 and j == n-1 :self.mm = max(self.mm,mini)return                grid[i][j] = 2self.dfs(grid,i+1,j,mini,note,m,n)self.dfs(grid,i-1,j,mini,note,m,n)self.dfs(grid,i,j+1,mini,note,m,n)self.dfs(grid,i,j-1,mini,note,m,n)grid[i][j] = 0

改成了动态规划的方法，还是解答错误，但是通过的用例更多了
（983 / 1035）

class Solution:def maximumSafenessFactor(self, grid: List[List[int]]) -> int:note = []m = len(grid)n = len(grid[0])for i in range(m):for j in range(n):if grid[i][j] == 1 :note.append([i,j])if i == 0 and j == 0 :return 0if i == m-1 and j == n-1 :return 0dp = [[0]*(n) for _ in range(m)]for i in range(0,m):for j in range(0,n):mini = inftemp = [[p[0]-(i),p[1]-(j)] for p in note]     for k in temp :mini = min(mini,abs(k[0])+abs(k[1]))'''               if mini < dp[i-1][j] and mini < dp[i][j-1] :dp[i][j] = minielif mini > dp[i-1][j] and mini > dp[i][j-1] :dp[i][j] = max(dp[i-1][j],dp[i][j-1])else :dp[i][j] = mini'''if i == 0 and j != 0:kk = dp[i][j-1]elif j == 0 and i!=0:kk =  dp[i-1][j]elif j == 0 and i==0:kk =  infelse :kk = max(dp[i-1][j],dp[i][j-1])if mini < kk :dp[i][j] = minielse :dp[i][j] = kk#return dpreturn dp[-1][-1]

两次动归也不对。

class Solution:def maximumSafenessFactor(self, grid: List[List[int]]) -> int:note = []m = len(grid)n = len(grid[0])for i in range(m):for j in range(n):if grid[i][j] == 1 :note.append([i,j])if i == 0 and j == 0 :return 0if i == m-1 and j == n-1 :return 0dp = [[0]*(n) for _ in range(m)]for i in range(0,m):for j in range(0,n):mini = inftemp = [[p[0]-(i),p[1]-(j)] for p in note]     for k in temp :mini = min(mini,abs(k[0])+abs(k[1]))'''               if mini < dp[i-1][j] and mini < dp[i][j-1] :dp[i][j] = minielif mini > dp[i-1][j] and mini > dp[i][j-1] :dp[i][j] = max(dp[i-1][j],dp[i][j-1])else :dp[i][j] = mini'''if i == 0 and j != 0:kk = dp[i][j-1]elif j == 0 and i!=0:kk =  dp[i-1][j]elif j == 0 and i==0:kk =  infelse :kk = max(dp[i-1][j],dp[i][j-1])if mini < kk :dp[i][j] = minielse :dp[i][j] = kkdp2 = [[0]*(n) for _ in range(m)]for i in range(m-1,-1,-1):for j in range(n-1,-1,-1):mini = inftemp = [[p[0]-(i),p[1]-(j)] for p in note]     for k in temp :mini = min(mini,abs(k[0])+abs(k[1]))'''               if mini < dp[i-1][j] and mini < dp[i][j-1] :dp[i][j] = minielif mini > dp[i-1][j] and mini > dp[i][j-1] :dp[i][j] = max(dp[i-1][j],dp[i][j-1])else :dp[i][j] = mini'''if i == m-1 and j != n-1:kk = dp[i][j+1]elif j == n-1 and i!=m-1:kk =  dp[i+1][j]elif j == n-1 and i==m-1:kk =  infelse :kk = max(dp[i+1][j],dp[i][j+1])if mini < kk :dp[i][j] = minielse :dp[i][j] = kk#return dpreturn max(dp[-1][-1],dp2[-1][-1])

题目

体会

不能用DP的原因：

因为不仅可以向右和向下走，还可以向上和向左，所以不能dp。

从来没接触过这道题的解法，也看不懂。

class UnionFind:def __init__(self, n):self.parent = list(range(n))def find(self, a):a = self.parent[a]acopy = awhile a != self.parent[a]:a = self.parent[a]while acopy != a:self.parent[acopy], acopy = a, self.parent[acopy]return adef merge(self, a, b):pa, pb = self.find(a), self.find(b)if pa == pb: return Falseself.parent[pb] = pareturn Trueclass Solution:def maximumSafenessFactor(self, grid: List[List[int]]) -> int:n = len(grid)dist = [[inf] * n for _ in range(n)]tmp = deque([(i, j) for i in range(n) for j in range(n) if grid[i][j]])for i, j in tmp:dist[i][j] = 0while tmp:i, j = tmp.popleft()for dx, dy in pairwise([-1, 0, 1, 0, -1]):if 0 <= i + dx < n and 0 <= j + dy < n and dist[i+dx][j+dy] == inf:dist[i+dx][j+dy] = dist[i][j] + 1tmp.append((i+dx, j+dy))l, r = 0, 2 * n - 2while l <= r:m = (l + r) // 2union = UnionFind(n * n)for i in range(n):for j in range(n):if dist[i][j] >= m:if i < n - 1 and dist[i+1][j] >= m: union.merge(i * n + j, (i + 1) * n + j)if j < n - 1 and dist[i][j+1] >= m: union.merge(i * n + j, i * n + j + 1)if union.find(0) == union.find(n * n - 1): l = m + 1else: r = m - 1return r

我的代码

题3

体会

class Solution:def findMaximumElegance(self, items: List[List[int]], k: int) -> int:items.sort(reverse=True)chosen = set()to_delete = []tot = 0for i in range(k):x, t = items[i]tot += xif t in chosen: heappush(to_delete, x)else: chosen.add(t)ans = tot + len(chosen) ** 2for i in range(k, len(items)):x, t = items[i]if t not in chosen and len(to_delete):chosen.add(t)tot -= heappop(to_delete)tot += xans = max(ans, tot + len(chosen) ** 2)return ans

我的代码