记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步
目录
- 2/10 913. 猫和老鼠
- 2/11 1728. 猫和老鼠 II
- 2/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
如果k>=2n 平局 猫和老鼠必定走到了之前各自走过的位置 依旧无法取胜
2.拓扑排序
https://leetcode.cn/problems/cat-and-mouse/?envType=daily-question&envId=2025-02-10
def catMouseGame1(graph):""":type graph: List[List[int]]:rtype: int"""n = len(graph)dp = [[[-1]*n for _ in range(n)] for _ in range(2*n*n)]mem={}def find(r,c,k):if k==2*n*n:return 0res = dp[k][r][c]if res!=-1:return resif r==0:return 1elif r==c: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%2==0 else catdefaultRes = 1 if cur!=rat else 2 #老鼠回合默认猫赢res = defaultResfor loc in graph[cur]:if cur==cat and loc==0:continuenextR = loc if cur==rat else ratnextC = loc if cur==cat else catnextRes = find(nextR,nextC,k+1)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: bool"""move = [(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 mloc==cloc or cloc==food or i>128: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(jump+1):nx,ny = pos[0]+dx*step,pos[1]+dy*stepif nx<0 or ny<0 or nx>=n or ny>=m or grid[nx][ny]=="#":breakif not cat_turn and dfs((nx,ny),cloc,i+1):return Trueelif cat_turn and not dfs(mloc,(nx,ny),i+1):return Falsereturn cat_turnreturn dfs(mouse,cat,0)2/12 1760. 袋子里最少数目的球
二分判断 每个袋子里最多为x时需要的操作次数
如果num<=x 则不需要
x<num<=2x 则需要1次 以此类推
如果此时操作次数op<=maxOperations 则可以将x减小
def minimumSize(nums, maxOperations):""":type nums: List[int]:type maxOperations: int:rtype: int"""l,r = 1,max(nums)ans = 0while l<=r:x = (l+r)//2ops = sum((num-1)//x for num in nums)if ops<=maxOperations:ans = xr = x-1else:l = x+1return ans2/13 1742. 盒子中小球的最大数量
用map存储每个盒子内的小球数
def countBalls(lowLimit, highLimit):""":type lowLimit: int:type highLimit: int:rtype: int"""def func(x):tag = 0while x>0:tag += x%10x = x//10return tagdic = {}ans = 0for i in range(lowLimit,highLimit+1):tag = func(i)dic[tag] = dic.get(tag,0)+1if dic[tag]>ans:ans = dic[tag]return ans2/14 1552. 两球之间的磁力
最大化最小值 二分判断mid距离是否合法
check检查距离x合法性
def maxDistance(position, m):""":type position: List[int]:type m: int:rtype: int"""def check(x):pre=position[0]cnt = 1for i in range(1,len(position)):if position[i]-pre>=x:pre = position[i]cnt+=1return cnt>=mposition.sort()l,r=1,position[-1]-position[0]ans = -1while l<=r:mid = (l+r)//2if check(mid):ans = midl=mid+1else:r=mid-1return ans2/15 1706. 球会落何处
模拟小球运动
小球从上至下运动 行数依次增加 col记录当前小球所在列
如果是1 则向右边移动 col+1
如果是-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 i+1<n:if grid[m-1][i+1]==1:mem[m-1][i][1]=i+1else:mem[m-1][i][1]=imem[m-1][i][0] = -1if i-1>=0: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 loc==0:if grid[i+1][j]==1:ans = check(i+1,j,1)else:ans = check(i+1,j,0)else:ans = -1if j+1<n and grid[i][j+1]==1:ans = check(i,j+1,0)else:if loc ==0:ans = -1if j-1>=0 and grid[i][j-1]==-1:ans = check(i,j-1,1)else:if grid[i+1][j]==1:ans = check(i+1,j,1)else:ans = check(i+1,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 col<0 or col>=n or grid[i][col]!=mv:tag = Falsebreakif tag:ans[j]=colreturn ans2/16 1299. 将每个元素替换为右侧最大元素
从后往前遍历 记录当前遇到最大的值
def replaceElements(arr):""":type arr: List[int]:rtype: List[int]"""cur=-1for i in range(len(arr)-1,-1,-1):tmp=curcur=max(cur,arr[i])arr[i]=tmpreturn arr
