做调查可以赚钱的网站,wordpress选项卡分页,山西省城乡建设厅网站,个人网站制作的主要内容2023-8-6 题1体会我的代码 题2我的超时代码题目体会我的代码 题3体会我的代码 题1 体会 这道题完全就是唬人#xff0c;只要想明白了#xff0c;只要有两个连续的数的和#xff0c;大于target#xff0c;那么一定可以#xff0c;两边一次切一个就好了。
我的代码
题2
我… 2023-8-6 题1体会我的代码 题2我的超时代码题目体会我的代码 题3体会我的代码 题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,i1,j,mini,note,m,n)self.dfs(grid,i-1,j,mini,note,m,n)self.dfs(grid,i,j1,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] miniif 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 i0: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] miniif 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 i0: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] miniif i m-1 and j ! n-1:kk dp[i][j1]elif j n-1 and i!m-1:kk dp[i1][j]elif j n-1 and im-1:kk infelse :kk max(dp[i1][j],dp[i][j1])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[idx][jdy] inf:dist[idx][jdy] dist[i][j] 1tmp.append((idx, jdy))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[i1][j] m: union.merge(i * n j, (i 1) * n j)if j n - 1 and dist[i][j1] 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(reverseTrue)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
我的代码
