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