深圳外贸网站,丹阳企业网站,网站建设如何盈利,wordpress my visitors记录了初步解题思路 以及本地实现代码#xff1b;并不一定为最优 也希望大家能一起探讨 一起进步 目录 2/10 913. 猫和老鼠2/11 1728. 猫和老鼠 II2/12 1760. 袋子里最少数目的球2/13 1742. 盒子中小球的最大数量2/14 1552. 两球之间的磁力2/15 1706. 球会落何处2/16 1299. 将…记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步 目录 2/10 913. 猫和老鼠2/11 1728. 猫和老鼠 II2/12 1760. 袋子里最少数目的球2/13 1742. 盒子中小球的最大数量2/14 1552. 两球之间的磁力2/15 1706. 球会落何处2/16 1299. 将每个元素替换为右侧最大元素 2/10 913. 猫和老鼠 1.动态规划 (TLE) dp[k][rat][cat] 第k轮表示老鼠位于rat位置 猫位于cat位置的游戏结果 dp[0][1][2]为初始状态的结果 老鼠进入0则老鼠获胜 dp[k][0][cat]1 猫和老鼠同个位置猫获胜 dp[k][x][x] 2 x!0 如果k2n 平局 猫和老鼠必定走到了之前各自走过的位置 依旧无法取胜 2.拓扑排序 https://leetcode.cn/problems/cat-and-mouse/?envTypedaily-questionenvId2025-02-10 def catMouseGame1(graph)::type graph: List[List[int]]:rtype: intn len(graph)dp [[[-1]*n for _ in range(n)] for _ in range(2*n*n)]mem{}def find(r,c,k):if k2*n*n:return 0res dp[k][r][c]if res!-1:return resif r0:return 1elif rc:return 2else:res move(r,c,k)dp[k][r][c] resreturn resdef move(rat,cat,k):if (rat,cat,k) in mem:return mem[(rat,cat,k)]cur rat if k%20 else catdefaultRes 1 if cur!rat else 2 #老鼠回合默认猫赢res defaultResfor loc in graph[cur]:if curcat and loc0:continuenextR loc if currat else ratnextC loc if curcat else catnextRes find(nextR,nextC,k1)if nextRes!defaultRes: ##找到一个能够赢得即可res nextResif res!0:breakmem[(rat,cat,k)] resreturn resreturn find(1,2,0)def catMouseGame2(graph)::type graph: List[List[int]]import collectionsMOUSE_TURN 0CAT_TURN 1DRAW 0MOUSE_WIN 1CAT_WIN 2n len(graph)degrees [[[0, 0] for _ in range(n)] for _ in range(n)]results [[[0, 0] for _ in range(n)] for _ in range(n)]for i in range(n):for j in range(1, n):degrees[i][j][MOUSE_TURN] len(graph[i])degrees[i][j][CAT_TURN] len(graph[j])for y in graph[0]:for i in range(n):degrees[i][y][CAT_TURN] - 1q collections.deque()for j in range(1, n):results[0][j][MOUSE_TURN] MOUSE_WINresults[0][j][CAT_TURN] MOUSE_WINq.append((0, j, MOUSE_TURN))q.append((0, j, CAT_TURN))for i in range(1, n):results[i][i][MOUSE_TURN] CAT_WINresults[i][i][CAT_TURN] CAT_WINq.append((i, i, MOUSE_TURN))q.append((i, i, CAT_TURN))while q:mouse, cat, turn q.popleft()result results[mouse][cat][turn]if turn MOUSE_TURN:prevStates [(mouse, prev, CAT_TURN) for prev in graph[cat]]else:prevStates [(prev, cat, MOUSE_TURN) for prev in graph[mouse]]for prevMouse, prevCat, prevTurn in prevStates:if prevCat 0:continueif results[prevMouse][prevCat][prevTurn] DRAW:canWin result MOUSE_WIN and prevTurn MOUSE_TURN or result CAT_WIN and prevTurn CAT_TURNif canWin:results[prevMouse][prevCat][prevTurn] resultq.append((prevMouse, prevCat, prevTurn))else:degrees[prevMouse][prevCat][prevTurn] - 1if degrees[prevMouse][prevCat][prevTurn] 0:results[prevMouse][prevCat][prevTurn] CAT_WIN if prevTurn MOUSE_TURN else MOUSE_WINq.append((prevMouse, prevCat, prevTurn))return results[1][2][MOUSE_TURN] 2/11 1728. 猫和老鼠 II 缓存lru_cache 参考https://leetcode.cn/problems/cat-and-mouse-ii/solution/python-ji-xiao-ji-da-bo-yi-by-himymben-ukbk/ def canMouseWin(grid, catJump, mouseJump)::type grid: List[str]:type catJump: int:type mouseJump: int:rtype: boolmove [(0,1),(0,-1),(-1,0),(1,0)]n,m len(grid),len(grid[0])for i in range(n):for j in range(m):if grid[i][j]C:cat (i,j)elif grid[i][j] F:food (i,j)elif grid[i][j] M:mouse (i,j)lru_cache(None)def dfs(mloc,cloc,i):if mloccloc or clocfood or i128:return Falseif mloc food:return Truepos,jump mloc,mouseJumpcat_turn Falseif i%2:pos,jump cloc,catJumpcat_turn Truefor dx,dy in move:for step in range(jump1):nx,ny pos[0]dx*step,pos[1]dy*stepif nx0 or ny0 or nxn or nym or grid[nx][ny]#:breakif not cat_turn and dfs((nx,ny),cloc,i1):return Trueelif cat_turn and not dfs(mloc,(nx,ny),i1):return Falsereturn cat_turnreturn dfs(mouse,cat,0) 2/12 1760. 袋子里最少数目的球 二分判断 每个袋子里最多为x时需要的操作次数 如果numx 则不需要 xnum2x 则需要1次 以此类推 如果此时操作次数opmaxOperations 则可以将x减小 def minimumSize(nums, maxOperations)::type nums: List[int]:type maxOperations: int:rtype: intl,r 1,max(nums)ans 0while lr:x (lr)//2ops sum((num-1)//x for num in nums)if opsmaxOperations:ans xr x-1else:l x1return ans 2/13 1742. 盒子中小球的最大数量 用map存储每个盒子内的小球数 def countBalls(lowLimit, highLimit)::type lowLimit: int:type highLimit: int:rtype: intdef func(x):tag 0while x0:tag x%10x x//10return tagdic {}ans 0for i in range(lowLimit,highLimit1):tag func(i)dic[tag] dic.get(tag,0)1if dic[tag]ans:ans dic[tag]return ans 2/14 1552. 两球之间的磁力 最大化最小值 二分判断mid距离是否合法 check检查距离x合法性 def maxDistance(position, m)::type position: List[int]:type m: int:rtype: intdef check(x):preposition[0]cnt 1for i in range(1,len(position)):if position[i]-prex:pre position[i]cnt1return cntmposition.sort()l,r1,position[-1]-position[0]ans -1while lr:mid (lr)//2if check(mid):ans midlmid1else:rmid-1return ans 2/15 1706. 球会落何处 模拟小球运动 小球从上至下运动 行数依次增加 col记录当前小球所在列 如果是1 则向右边移动 col1 如果是-1 则向左边移动 col-1 此时如果碰到左右两侧 则卡住 或者此时的格子状态与之前不同遇到V型 同样卡住 tag判断小球是否顺利通过 最后记录小球的结果 def findBall(grid)::type grid: List[List[int]]:rtype: List[int]m,n len(grid),len(grid[0])mem [[[float(inf),float(inf)]for _ in range(n)] for _ in range(m)]for i in range(n):if grid[m-1][i]1:mem[m-1][i][0] imem[m-1][i][1] -1if i1n:if grid[m-1][i1]1:mem[m-1][i][1]i1else:mem[m-1][i][1]imem[m-1][i][0] -1if i-10:if grid[m-1][i-1]-1:mem[m-1][i][0] i-1def check(i,j,loc):ans float(inf)if mem[i][j][loc]!float(inf):return mem[i][j][loc]if grid[i][j]1:if loc0:if grid[i1][j]1:ans check(i1,j,1)else:ans check(i1,j,0)else:ans -1if j1n and grid[i][j1]1:ans check(i,j1,0)else:if loc 0:ans -1if j-10 and grid[i][j-1]-1:ans check(i,j-1,1)else:if grid[i1][j]1:ans check(i1,j,1)else:ans check(i1,j,0)mem[i][j][loc]ansreturn ansret []for j in range(n):loc 0 if grid[0][j]-1 else 1ret.append(check(0,j,loc))return retdef findBall2(grid)::type grid: List[List[int]]:rtype: List[int]m,n len(grid),len(grid[0])ans [-1]*nfor j in range(n):col jtag Truefor i in range(m):mv grid[i][col]col mvif col0 or coln or grid[i][col]!mv:tag Falsebreakif tag:ans[j]colreturn ans 2/16 1299. 将每个元素替换为右侧最大元素 从后往前遍历 记录当前遇到最大的值 def replaceElements(arr)::type arr: List[int]:rtype: List[int]cur-1for i in range(len(arr)-1,-1,-1):tmpcurcurmax(cur,arr[i])arr[i]tmpreturn arr
