# LeetCode Medium 133. Clone Graph
tags: leetcode
問題
アイデア
「無向グラフの deepcopy
を作成し、返せ」という問題です。
BFS、DFSで実装出来ると思いますが、今回はBFSで実装します。
解法
Queue
を使います。つまりBFSです。
- 与えられた
node
をqueue
に格納します。 - 今まで通ったオリジナルのノードのコピーを格納する連想配列
copy_of_original
を作成します。 - そして、
queue
の中身が空でなければ以下を実行します。cur
はqueue
の先頭のノードで、このノードのneighbors
を全て調べます。- もし、
copy_of_original
に入っていなければ、そのneighbor
をcopy_neighbor
としてneighbor
と結びつけます。そして、グラフの更新をし、最後にneighbor
をキューに追加します。 - もし、既に入っていれば、 その
cur
のコピーを作り、neighbor
に対応するコピーをそのneighbors
に追加します。
- もし、
計算量
ノードの数を $N$ とします。
- 時間計算量
- $O(N)$
- 空間計算量
- $O(N)$
Python
""" # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] """ class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: return copy_node = Node(node.val, []) copy_of_original = {node: copy_node} queue = collections.deque([node]) while queue: cur = queue.popleft() for neighbor in cur.neighbors: if neighbor not in copy_of_original: # neighbor is not visited copy_neighbor = Node(neighbor.val, []) copy_of_original[neighbor] = copy_neighbor copy_of_original[cur].neighbors.append(copy_neighbor) queue.append(neighbor) else: copy_of_original[cur].neighbors.append(copy_of_original[neighbor]) return copy_node
# LeetCode Medium 150. Evaluate Reverse Polish Notation
tags: leetcode
問題
アイデア
「ポーランド記法で記述された数式を評価しろ」という問題です。
数式はいつも正しく解くことが出来るそうで、特にエラー処理についか考える必要はなさそうです。
解法
そのままやるだけですが、プログラミング言語によって負の値での除算の結果が変わるのでそこは注意しましょう。
計算量
配列の大きさを$N$とします。
- 時間計算量
- $O(N)$
- 空間計算量
- $O(N)$
Python
class Solution: def evalRPN(self, tokens: List[str]) -> int: results = [] for token in tokens: try: results.append(int(token)) except ValueError: if len(results) > 1: a = results.pop() b = results.pop() if token == "+": results.append(a + b) if token == "-": results.append(b - a) if token == "*": results.append(a * b) if token == "/": results.append(int(float(b) / a)) else: raise Exception("Error: The list size is not enough.") return results[-1]
# LeetCode Easy 20. Valid Parentheses
tags: leetcode
問題
アイデア
「文字列が与えられ、正しいカッコであるかどうかを判定せよ」という問題です。
正しいカッコかどうかはスタックを使えば簡単に判定することが可能です。
解法
文字列を走査して、文字の種類に応じて処理をします。
スタックで今まで走査した文字を管理します。
計算量
与えられる文字列 s
の長さを $N$ とします。
- 時間計算量
- $O(N)$
- 空間計算量
- $O(N)$
Python
class Solution: def isValid(self, s: str) -> bool: paren_stack = [] for paren in s: if paren in "({[": paren_stack.append(paren) elif not paren_stack: return False elif paren == ")" and paren_stack[-1] == "(": paren_stack.pop() elif paren == "}" and paren_stack[-1] == "{": paren_stack.pop() elif paren == "]" and paren_stack[-1] == "[": paren_stack.pop() else: return False return not paren_stack
# LeetCode Medium 739. Daily Temperatures
tags: leetcode
問題
アイデア
「毎日の気温の配列 T
が与えられたとき、次にその日よりも温かい日が後何日で来るかを伝える配列を返せ」という問題です。こないならば 0
を代わりに返すようです。
これは要素を1つずつ見て、それ以降の要素を見るという風に解こうとすると計算量が非常に大きくなります。このようなときはそれらをスタックとして保管して、条件に合うものがあったら pop()
して見ていくという風にやります。
解法
- 気温の配列を最初から走査します。
- この際に、既に通った要素の添字を保管する
indices
というスタックを用意します。- スタックに要素が入っていて、かつその添字が示す
T
の要素が走査中の要素よりも小さい時、indices
をpop()
し、走査中の要素との差を格納します
- スタックに要素が入っていて、かつその添字が示す
- そして、現在の要素の添字をスタックに格納します。
計算量
配列の大きさを N
とします。
- 時間計算量
- $O(N)$
- 空間計算量
- スタックの大きさに比例して $O(N)$
Python
class Solution: def dailyTemperatures(self, T: List[int]) -> List[int]: ans = [0] * len(T) indices = [] for idx, ele in enumerate(T): while indices and T[indices[-1]] < ele: last_found_idx = indices.pop() ans[last_found_idx] = idx - last_found_idx indices.append(idx) return ans
# LeetCode Easy 155. Min Stack
tags: leetcode
問題
アイデア
「push
,pop
,top
,getMin
というメソッドをサポートするスタックを実装せよ」という問題です.ただし,getMin
の時間計算量は定数時間です.
実装するだけです.
解法
stack
に(x, <xが出るまでの最小値)
を保存する.コレに対して,stack
を実行する
計算量
- 時間計算量
- 初期化
- $O(1)$
push
- $O(1)$
pop
- $O(1)$
top
- $O(1)$
getMin
- $O(1)$
- 初期化
- 空間計算量
- 初期化
- $O(1)$
push
- $O(n)$
pop
- $O(1)$
top
- $O(1)$
getMin
- $O(1)$
- 初期化
Python
class MinStack: def __init__(self): self.stack = [] def push(self, x): self.stack.append((x, min(self.getMin(), x))) def pop(self): self.stack.pop() def top(self): if self.stack: return self.stack[-1][0] def getMin(self): if self.stack: return self.stack[-1][1] return sys.maxsize # Your MinStack object will be instantiated and called as such: # obj = MinStack() # obj.push(x) # obj.pop() # param_3 = obj.top() # param_4 = obj.getMin()