1857. Largest Color Value in a Directed Graph
给你一个有向图，每个顶点有各自的颜色
一条路径的 color value 定义为这条路径上出现次数最多的颜色数量
要你找出这张图所有路径中最大的 color value
颜色有26种，用小写字母代替
Example 1:
https://assets.leetcode.com/uploads/2021/04/21/leet1.png
Input: colors = "abaca", edges = [[0,1],[0,2],[2,3],[3,4]]
Output: 3
最大的 color value 3 在 0->2->3->4 这条路径上，颜色 a 出现了 3 次
Example 2:
Input: colors = "a", edges = [[0,0]]
Output: -1
有 cycle 的情况下回传 -1
思路:
1.很容易想到的暴力法是枚举每个点当成 root 跑一次 DFS
这样就能检查到所有 path
但因为每次 DFS 都有机会检查到重复的边
可以想像 4->3->2->1->0 这个 case
如果照顺序从 0 开始当顶点 检查的边数会来到O(n^2)
2.这时候就想怎么让一条边只走一次
假如有一条 a->b->c
如果我们知道以 a 为结尾的所有路径 每个不同的 color 最多会出现几次
就可以用他去更新以 b 为结尾的所有路径
如果这时 b 没有其他人会走到了 就可以用它的结果去更新 b->c
如果除了 a 还有另一个像是 d->b
那在用 b 更新 c 之前就要先处理完 d->b 这条 edge
不然就会漏掉 d->b->c
3.简单说就是能更新别人的 node 只有指向自己的 inedge 数量是0的那些
类似 topological sort 的概念
维护一个 queue 装那些 inedge = 0 的 node
更新他们的邻居 让他们的邻居 inedge -= 1
如果邻居的 inedge = 0 就把他丢进 queue 里
至于有 cycle 的话就会发生有的点还没走过 但 queue 已经空了的状况
Python code:
class Solution:
def largestPathValue(self, colors: str, edges: List[List[int]]) -> int:
graph = defaultdict(list)
n = len(colors)
color = [defaultdict(int) for _ in range(n)]
inedge = [0]*n
for a, b in edges:
graph[a].append(b)
inedge[b] += 1
top = deque()
for i in range(n):
if inedge[i] == 0:
top.append(i)
res = 0
while top:
node = top.pop()
color[node][colors[node]] += 1
res = max(res, color[node][colors[node]])
for next in graph[node]:
for key in color[node]:
color[next][key] = max(color[next][key], color[node][key])
inedge[next] -= 1
if inedge[next] == 0:
top.append(next)
if any(inedge):
return -1
else:
return res
20. Valid Parentheses
检查左右括号是否合法 经典题
Example 1:
Input: s = "()"
Output: true
Example 2:
Input: s = "()[]{}"
Output: true
Example 3:
Input: s = "(]"
Output: false
思路:
1.stack 经典题 应该不用解释太多
左括号就丢进 stack
右括号就看 stack.top 有没有办法和他配 没有就 fail
class Solution:
def isValid(self, s: str) -> bool:
stk = []
paren = set(['()', '{}', '[]'])
for c in s:
if c in "([{":
stk.append(c)
elif stk and stk[-1]+c in paren:
del stk[-1]
else:
return False
return not stk