# LeetCode Medium 133. Clone Graph

tags: leetcode

問題

• Explore
• Problems

アイデア

｢無向グラフの 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

問題

• Explore
• Problems

アイデア

｢ポーランド記法で記述された数式を評価しろ｣という問題です｡

数式はいつも正しく解くことが出来るそうで､特にエラー処理についか考える必要はなさそうです｡

解法

そのままやるだけですが､プログラミング言語によって負の値での除算の結果が変わるのでそこは注意しましょう｡

計算量

配列の大きさを$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

問題

• Explore
• Problems

アイデア

｢文字列が与えられ､正しいカッコであるかどうかを判定せよ｣という問題です｡

正しいカッコかどうかはスタックを使えば簡単に判定することが可能です｡

解法

文字列を走査して､文字の種類に応じて処理をします｡

スタックで今まで走査した文字を管理します｡

計算量

与えられる文字列 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

問題

• Explore
• Problems

アイデア

｢毎日の気温の配列 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

問題

• Explore
• Problems

アイデア

｢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()