こんにちは
今回の学びは
・計算は計算グラフなので、graph問題に落とし込めないか？
（時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装 20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。
終始、わからないことは声にだして、明確にしていきましょう。
１，まずは入出力をしっかりおさえましょう。（問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと）
入力のバリデーションのパターンはたくさんありそう。
２，いくつかのソリューションを声にだして出してみましょう。（もちろんtime complexit, space complexityの分析や理由を付け加えて）
数式を書くように、a/b = 2.0, b/c = 3.0を連立方程式でとくのは複雑すぎる。ので
graph問題に落とし込めないか？とかんがえる。
３，どれでいくか、一緒に決定しましょう。（理由付きでね、よろしく）
timespace analysis (時間とスペースの分析）は 〇〇です
O(N + M)
場合によっては、pseudocode（擬似コード）をかいてみてもよい。
A / B = k
A:str, B:str, k:float
Goal => return answer or -1 if answer doesn't exist.
equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]
# 1 construct graph, bidirected, a -> b 2.0, b <- a 1/2.0
# for equ in equaations # O(N)
# for q in queries # O(M)
# bfs, then tract the in order of q. # O(1)
"""
{
a : {b:2.0}
b : {a:0.5}
b : {c:3.0}
c : {b:1/3}
}
"""
def make(graph, equation, value):
# add to graph
x, y = equation # a, b = 2
# Todo. not to use udpate, but graph[x][y] = value, is faster
graph[x].update({y:value})
graph[y].update({x:1/value})
def solve(equations, values, quries):
# edge
if len(equations) != len(values) or len(values) == 0: return []
graph = defaultlist(dict)
for i in range(len(values)):
make(graph, equation, value)
"""
{
a : {b:2.0}
b : {a:0.5}
b : {c:3.0}
c : {b:1/3}
}
a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .
"""
def bfs(start, end):
visited = { k : 0 for k in graph.keys()} }
stack = [(start, None)]
while stack:
n, acc = stack.pop()
if visited[n] == 1: continue
if n == end: return acc
for j, value in graph[n].items():
tmp = 1 if acc == None else acc
stack.append((j, value * tmp))
visited[n] = 1
return -1
A = []
for a, b in quries:
A.append(bfs(a, b))
return A
４、実装しましょう。
from collections import defaultdict
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
# edge
if len(equations) != len(values) or len(values) == 0: return []
graph = defaultdict(dict)
def make(graph, equation, value):
(x, y) = equation
graph[x].update({y:value}) # Todo. not to use udpate, but graph[x][y] = value, is faster
graph[y].update({x:1/value})
#graph[x][y] = value
#graph[y][x] = 1/value
for i in range(len(values)):
make(graph, equations[i], values[i])
def bfs(start, end):
visited = defaultdict(int)
stack = [(start, 1)]
while stack:
n, acc = stack.pop()
if visited[n] == 1: continue
if n == end: return acc if n in graph else -1.0
for j, value in graph[n].items():
stack.append((j, value * acc))
visited[n] = 1
return -1
A = []
for a, b in queries:
A.append(bfs(a, b))
return A
５、エッジケースとサンプルテストを忘れずに！
実際の入力でやるとvisitedとか、足りないと見えてきますね。
振り返り
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
計算は計算グラフなので、graph問題に落とし込めないか？
驚いたのは、以下の処理はupdateを使ったほうがだいぶ速かった。
stackoverflowを見ても、これ！という事象がないので、leetcodeの実行環境によりけりの可能性もあるので、今は深追いしないでおこう。場合によってはpythonのしくみで扱おう
graph[x].update({y:value}) # Todo. not to use udpate, but graph[x][y] = value, is faster
graph[y].update({x:1/value})
#graph[x][y] = value
#graph[y][x] = 1/value
まとめ
・計算は計算グラフなので、graph問題に落とし込めないか？
以上です