いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 399 Evaluate Division

投稿日:

こんにちは

今回の学びは

・計算は計算グラフなので、graph問題に落とし込めないか?

 

問題はevaluate-division

(時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装  20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。

終始、わからないことは声にだして、明確にしていきましょう。

1,まずは入出力をしっかりおさえましょう。(問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと)

入力のバリデーションのパターンはたくさんありそう。

2,いくつかのソリューションを声にだして出してみましょう。(もちろんtime complexit, space complexityの分析や理由を付け加えて)

数式を書くように、a/b = 2.0, b/c = 3.0を連立方程式でとくのは複雑すぎる。ので

graph問題に落とし込めないか?とかんがえる。

 

3,どれでいくか、一緒に決定しましょう。(理由付きでね、よろしく)

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




 

4、実装しましょう。

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

5、エッジケースとサンプルテストを忘れずに!

実際の入力でやると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問題に落とし込めないか?

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.