LeetCode 每日一题 2025/5/26-2025/6/1

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

---

5/26 1857. 有向图中最大颜色值

g存放邻接表
f[x,c]代表到x节点 颜色c的最大值
广搜 如果当前节点x的颜色为c 那么f[x,c]+=1
后续节点y f[y,c]=max(f[x,c],f[y,c])

def largestPathValue(colors, edges):""":type colors: str:type edges: List[List[int]]:rtype: int"""import collectionsn=len(colors)g=collections.defaultdict(list)indeg=[0]*nfor x,y in edges:indeg[y]+=1g[x].append(y)found=0f=[[0]*26 for _ in range(n)]q=collections.deque()for i in range(n):if indeg[i]==0:q.append(i)while q:found+=1u=q.popleft()f[u][ord(colors[u])-ord('a')]+=1for v in g[u]:indeg[v]-=1for c in range(26):f[v][c]=max(f[v][c],f[u][c])if indeg[v]==0:q.append(v)if found!=n:return -1ans=0for i in range(n):ans=max(ans,max(f[i]))return ans

---

5/27 2894. 分类求和并作差

求和 减去 所有m的倍数和*2

def differenceOfSums(n, m):""":type n: int:type m: int:rtype: int"""s=(1+n)*n//2for i in range(m,n+1,m):s-=2*ireturn s

---

5/28 3372. 连接两棵树后最大目标节点数目 I

对于第一棵树节点i 连线的一头一定是他自己 深搜第二棵树的节点

def maxTargetNodes(edges1, edges2, k):""":type edges1: List[List[int]]:type edges2: List[List[int]]:type k: int:rtype: List[int]"""def calctree(edges,k):g=[[] for _ in range(len(edges)+1)]for x,y in edges:g[x].append(y)g[y].append(x)global dd=0def dfsd(x,fa):global dmaxl=0for y in g[x]:if y!=fa:subl=dfsd(y,x)+1d=max(d,subl+maxl)maxl=max(maxl,subl)return maxldfsd(0,-1)def dfs(x,fa,d):if d>k:return 0cnt=1for y in g[x]:if y!=fa:cnt+=dfs(y,x,d+1)return cntreturn d,dfsn,m=len(edges1)+1,len(edges2)+1max2 = 0if k:d,dfs=calctree(edges2, k-1)if d<k:max2=melse:max2=max(dfs(i,-1,0) for i in range(m))d,dfs=calctree(edges1, k)if d<=k:return [n+max2]*nreturn [max2+dfs(i,-1,0) for i in range(n)]

---

5/29 3373. 连接两棵树后最大目标节点数目 II

将两个数染黑白两色 同一色的互为目标节点
选中第一个数的一个节点 在这颗树里的目标节点为同色节点
在第二棵树可以选择颜色多的为目标节点即可

def maxTargetNodes(edges1, edges2):""":type edges1: List[List[int]]:type edges2: List[List[int]]:rtype: List[int]"""def dfs(node,fa,depth,childs,color):ans=1-depth%2color[node]=depth%2for child in childs[node]:if child==fa:continueans+=dfs(child,node,depth+1,childs,color)return ansdef build(edges,color):n=len(edges)+1childs=[[] for _ in range(n)]for u,v in edges:childs[u].append(v)childs[v].append(u)ans=dfs(0,-1,0,childs,color)return [ans,n-ans]n,m=len(edges1)+1,len(edges2)+1color1=[0]*ncolor2=[0]*mcnt1=build(edges1,color1)cnt2=build(edges2,color2)ans=[max(cnt2[0],cnt2[1])]*nfor i in range(n):ans[i]+=cnt1[color1[i]]return ans

---

5/30 2359. 找到离给定两个节点最近的节点

先遍历节点一 记录它的路径s1[x] 为节点一到x距离
再遍历节点二 记录它的路径s2[x]
找到共同点 记录最远路径最小值

def closestMeetingNode(edges, node1, node2):""":type edges: List[int]:type node1: int:type node2: int:rtype: int"""n = len(edges)def find(x):d = [-1]*np = xdis = 0while p!=-1 and d[p]==-1:d[p]=disdis+=1p=edges[p]return ds1=find(node1)s2=find(node2)ans = -1for i in range(n):if s1[i]!=-1 and s2[i]!=-1 and (ans==-1 or max(s1[ans],s2[ans])>max(s1[i],s2[i])):ans=ireturn ans

---

5/31

---

6/1

---