记录了初步解题思路 以及本地实现代码并不一定为最优 也希望大家能一起探讨 一起进步目录6/29 1967. 作为子字符串出现在单词中的字符串数目6/30 1358. 包含所有三种字符的子字符串数目7/1 2812. 找出最安全路径7/2 3286. 穿越网格图的安全路径7/3 3620. 恢复网络路径7/47/56/29 1967. 作为子字符串出现在单词中的字符串数目word长度最大100 将所有子字符串加入set中遍历patterns 如果子字符串在set中 则计数加1返回计数defnumOfStrings(patterns,word): :type patterns: List[str] :type word: str :rtype: int ans0sset()foriinrange(len(word)):forjinrange(i,len(word)):s.add(word[i:j1])forpatterninpatterns:ifpatternins:ans1returnans6/30 1358. 包含所有三种字符的子字符串数目使用滑动窗口统计每个区间内 a、b、c 的出现次数。右指针向右扩展窗口直到窗口同时包含三种字符。当条件满足时不断右移左指针收缩窗口。每收缩一次当前左端点为起始点对应的合法子串数量增加 n - right。将所有贡献累加后得到答案。defnumberOfSubstrings(s): :type s: str :rtype: int nlen(s)cnt[0,0,0]left0ans0forright,chinenumerate(s):cnt[ord(ch)-ord(a)]1whilecnt[0]0andcnt[1]0andcnt[2]0:ansn-right cnt[ord(s[left])-ord(a)]-1left1returnans7/1 2812. 找出最安全路径BFS从所有有小偷的位置开始BFS每走一步表示安全系数1g[x][y]表示x,y位置的安全系数最大堆找一条路径使路径上的最小安全系数最大best[x][y] 表示到达 (x,y) 时路径最小安全系数的最大值defmaximumSafenessFactor(grid): :type grid: List[List[int]] :rtype: int fromcollectionsimportdequeimportheapq nlen(grid)g[[-1]*nfor_inrange(n)]qdeque()foriinrange(n):forjinrange(n):ifgrid[i][j]1:q.append((i,j))g[i][j]0dirs[(-1,0),(1,0),(0,-1),(0,1)]whileq:x,yq.popleft()fordx,dyindirs:nx,nyxdx,ydyif0nxnand0nynandg[nx][ny]-1:g[nx][ny]g[x][y]1q.append((nx,ny))best[[-1]*nfor_inrange(n)]best[0][0]g[0][0]heap[(-g[0][0],0,0)]whileheap:cur_safe_neg,x,yheapq.heappop(heap)cur_safe-cur_safe_negifxn-1andyn-1:returncur_safeifcur_safebest[x][y]:continuefordx,dyindirs:nx,nyxdx,ydyif0nxnand0nyn:nxt_safemin(cur_safe,g[nx][ny])ifnxt_safebest[nx][ny]:best[nx][ny]nxt_safe heapq.heappush(heap,(-nxt_safe,nx,ny))return07/2 3286. 穿越网格图的安全路径把每个格子看成图上的点移动到相邻格子的代价是目标格子的值。因为格子值只有 0 和 1所以这是 0-1 最短路问题可以用 0-1 BFS。定义 dist[i][j] 为从起点到 i,j 的最小扣血值。初始 dist[0][0] grid[0][0]其余为无穷大。从双端队列取点扩展四个方向若新代价更小则更新 dist。当移动代价是 0 时放到队首代价是 1 时放到队尾。最后若 dist[m-1][n-1] health说明最少扣血后仍至少剩 1 点生命值可以安全到达。否则无法到达。deffindSafeWalk(grid,health): :type grid: List[List[int]] :type health: int :rtype: bool fromcollectionsimportdeque mlen(grid)nlen(grid[0])inf10**9dist[[inf]*nfor_inrange(m)]dist[0][0]grid[0][0]dqdeque([(0,0)])dirs((1,0),(-1,0),(0,1),(0,-1))whiledq:x,ydq.popleft()curdist[x][y]fordx,dyindirs:nx,nyxdx,ydyif0nxmand0nyn:wgrid[nx][ny]ndcurwifnddist[nx][ny]:dist[nx][ny]ndifw0:dq.appendleft((nx,ny))else:dq.append((nx,ny))returndist[m-1][n-1]health7/3 3620. 恢复网络路径路径分数定义为路径上的最小边权要求在总成本不超过 k 的前提下让这个最小边权尽量大。可以二分这个“最小边权”阈值 mid只保留边权 mid 的边问题变成是否存在一条从 0 到 n-1 的路径总成本 k且中间节点在线。原图是有向无环图先做一次拓扑排序。每次 check(mid) 时按拓扑序做最短路松弛只使用满足边权 mid 的边二分通过后得到最大可行 mid若最小边权都不可行返回 -1。deffindMaxPathScore(edges,online,k): :type edges: List[List[int]] :type online: List[bool] :type k: int :rtype: int fromcollectionsimportdeque nlen(online)adj[[]for_inrange(n)]indeg[0]*n costs[]defnode_allowed(x):returnonline[x]orx0orxn-1# 预处理去掉经过离线中间节点的边foru,v,winedges:ifnotnode_allowed(u)ornotnode_allowed(v):continueadj[u].append((v,w))indeg[v]1costs.append(w)ifnotcosts:return-1# DAG 拓扑序qdeque(iforiinrange(n)ifindeg[i]0)topo[]whileq:uq.popleft()topo.append(u)forv,_inadj[u]:indeg[v]-1ifindeg[v]0:q.append(v)INF10**30defcheck(limit):dist[INF]*n dist[0]0foruintopo:dudist[u]ifduk:continueifduINF:continueforv,winadj[u]:ifwlimit:continuendduwifnddist[v]:dist[v]ndreturndist[n-1]k valssorted(set(costs))ifnotcheck(vals[0]):return-1l,r0,len(vals)-1whilelr:mid(lr1)//2ifcheck(vals[mid]):lmidelse:rmid-1returnvals[l]7/47/5