LeetCode 每日一题 2026/6/29-2026/7/5

记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

6/29 1967. 作为子字符串出现在单词中的字符串数目

word长度最大100 将所有子字符串加入set中

遍历patterns 如果子字符串在set中 则计数加1

返回计数

defnumOfStrings(patterns,word):""" :type patterns: List[str] :type word: str :rtype: int """ans=0s=set()foriinrange(len(word)):forjinrange(i,len(word)):s.add(word[i:j+1])forpatterninpatterns:ifpatternins:ans+=1returnans

6/30 1358. 包含所有三种字符的子字符串数目

使用滑动窗口统计每个区间内 a、b、c 的出现次数。

右指针向右扩展窗口，直到窗口同时包含三种字符。

当条件满足时，不断右移左指针收缩窗口。

每收缩一次，当前左端点为起始点对应的合法子串数量增加 n - right。

将所有贡献累加后得到答案。

defnumberOfSubstrings(s):""" :type s: str :rtype: int """n=len(s)cnt=[0,0,0]left=0ans=0forright,chinenumerate(s):cnt[ord(ch)-ord('a')]+=1whilecnt[0]>0andcnt[1]>0andcnt[2]>0:ans+=n-right cnt[ord(s[left])-ord('a')]-=1left+=1returnans

7/1 2812. 找出最安全路径

BFS

从所有有小偷的位置开始BFS

每走一步表示安全系数+1

g[x][y]表示x,y位置的安全系数

最大堆：找一条路径，使路径上的最小安全系数最大

best[x][y] 表示到达 (x,y) 时，路径最小安全系数的最大值

defmaximumSafenessFactor(grid):""" :type grid: List[List[int]] :rtype: int """fromcollectionsimportdequeimportheapq n=len(grid)g=[[-1]*nfor_inrange(n)]q=deque()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,y=q.popleft()fordx,dyindirs:nx,ny=x+dx,y+dyif0<=nx<nand0<=ny<nandg[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,y=heapq.heappop(heap)cur_safe=-cur_safe_negifx==n-1andy==n-1:returncur_safeifcur_safe<best[x][y]:continuefordx,dyindirs:nx,ny=x+dx,y+dyif0<=nx<nand0<=ny<n:nxt_safe=min(cur_safe,g[nx][ny])ifnxt_safe>best[nx][ny]:best[nx][ny]=nxt_safe heapq.heappush(heap,(-nxt_safe,nx,ny))return0

7/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 m=len(grid)n=len(grid[0])inf=10**9dist=[[inf]*nfor_inrange(m)]dist[0][0]=grid[0][0]dq=deque([(0,0)])dirs=((1,0),(-1,0),(0,1),(0,-1))whiledq:x,y=dq.popleft()cur=dist[x][y]fordx,dyindirs:nx,ny=x+dx,y+dyif0<=nx<mand0<=ny<n:w=grid[nx][ny]nd=cur+wifnd<dist[nx][ny]:dist[nx][ny]=ndifw==0:dq.appendleft((nx,ny))else:dq.append((nx,ny))returndist[m-1][n-1]<health

7/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 n=len(online)adj=[[]for_inrange(n)]indeg=[0]*n costs=[]defnode_allowed(x):returnonline[x]orx==0orx==n-1# 预处理：去掉经过离线中间节点的边foru,v,winedges:ifnotnode_allowed(u)ornotnode_allowed(v):continueadj[u].append((v,w))indeg[v]+=1costs.append(w)ifnotcosts:return-1# DAG 拓扑序q=deque(iforiinrange(n)ifindeg[i]==0)topo=[]whileq:u=q.popleft()topo.append(u)forv,_inadj[u]:indeg[v]-=1ifindeg[v]==0:q.append(v)INF=10**30defcheck(limit):dist=[INF]*n dist[0]=0foruintopo:du=dist[u]ifdu>k:continueifdu==INF:continueforv,winadj[u]:ifw<limit:continuend=du+wifnd<dist[v]:dist[v]=ndreturndist[n-1]<=k vals=sorted(set(costs))ifnotcheck(vals[0]):return-1l,r=0,len(vals)-1whilel<r:mid=(l+r+1)//2ifcheck(vals[mid]):l=midelse:r=mid-1returnvals[l]

7/4

7/5