Leetcode 1857. 有向图中最大颜色值
1.题目基本信息
1.1.题目描述
给你一个 有向图 ，它含有 n 个节点和 m 条边。节点编号从 0 到 n – 1 。
给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的 颜色 （下标从 0 开始）。同时给你一个二维数组 edges ，其中 edges[j] = [a_j, b_j] 表示从节点 a_j 到节点 b_j 有一条 有向边 。
图中一条有效 路径 是一个点序列 x_1 -> x_2 -> x_3 -> … -> x_k ，对于所有 1 <= i < k ，从 x_i 到 x_i+1 在图中有一条有向边。路径的 颜色值 是路径中 出现次数最多 颜色的节点数目。
请你返回给定图中有效路径里面的 最大颜色值 。如果图中含有环，请返回 -1 。
1.2.题目地址
https://leetcode.cn/problems/largest-color-value-in-a-directed-graph/description/
2.解题方法
2.1.解题思路
拓扑排序+动态规划
2.2.解题步骤
第一步，状态构建；dp[i][j]为以i节点结尾的路径的颜色j的最大数量
第二步，构建邻接表和入度表（注意初始化图，边并不一定会包括所有的节点）
第三步，先获取拓扑排序，再在过程中进行状态转移；同时获取拓扑排序的长度，用来判断有无环
- 其中，状态转移方程：dp[i][j]=max([dp[node][j]+nodeIIsJColor(j) for node in prev(i)])
- 如果拓扑排序的长度不等于总节点个数，则有环，直接返回-1
最终状态dp中的最大值即为最终的结果
3.解题代码
Python代码
from collections import defaultdict,deque
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
length=len(colors)
# 第一步，状态构建；dp[i][j]为以i节点结尾的路径的颜色j的最大数量
dp=[[0]*26 for _ in range(length)]
# 第二步，构建邻接表和入度表（注意初始化图，边并不一定会包括所有的节点）
graph={i:[] for i in range(length)}
inDegrees=defaultdict(int)
for from_,to_ in edges:
graph[from_].append(to_)
inDegrees[to_]+=1
# 第三步，先获取拓扑排序，再在过程中进行状态转移；同时获取拓扑排序的长度，用来判断有无环
# 其中，状态转移方程：dp[i][j]=max([dp[node][j]+nodeIIsJColor(j) for node in prev(i)])
topuSortArrLength=0
que=deque()
for node in graph.keys():
if inDegrees[node]==0:
que.append(node)
while que:
node=que.popleft()
topuSortArrLength+=1
dp[node][ord(colors[node])-ord('a')]+=1 # 将当前node的颜色添加到状态数组中
for subNode in graph[node]:
inDegrees[subNode]-=1
for i in range(26): # 更新子节点的每一种颜色状态
dp[subNode][i]=max(dp[subNode][i],dp[node][i])
if inDegrees[subNode]==0:
que.append(subNode)
# 如果拓扑排序的长度不等于总节点个数，则有环，直接返回-1
if topuSortArrLength!=length:
return -1
# print(dp)
# 最终状态中的最大值即为最终的结果
return max([max(t) for t in dp])
4.执行结果
原文地址：https://blog.csdn.net/m0_51437455/article/details/142974293
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！