概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

基本的にeasyのacceptanceが高い順から解いていこうかと思います。

前回
ゼロから始めるLeetCode Day6 「1342. Number of Steps to Reduce a Number to Zero」

サボらず1週間続きました。めでたい。

問題

104. Maximum Depth of Binary Tree

かなり初期の問題ですが、二分木の構造を理解する上で良い問題だと感じました。

二分木が与えられるのでその深さの最大値を探し出すようなアルゴリズムを書くことを求められます。

example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        depth = 0
        stack = [(root,1)]

        while stack:
            root,length = stack.pop()
            if not root:
                return 0

            if length > depth:
                depth = length
            if root.right:
                stack.append((root.right,length + 1))
            if root.left:
                stack.append((root.left,length + 1))
        return depth
# Runtime: 40 ms, faster than 70.51% of Python3 online submissions for Maximum Depth of Binary Tree.
# Memory Usage: 14.9 MB, less than 90.62% of Python3 online submissions for Maximum Depth of Binary Tree.

以前の二分探索木に関する問題、ゼロから始めるLeetCode Day4 「938. Range Sum of BST」でも書いたような深さ優先探索で書いてみました。

Discussなどで調べてみて知ったのですが、こういう書き方もあるんですね。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

from collections import deque

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        queue = deque([(root, 1)])
        while queue:
            curr, val = queue.popleft()
            if not curr.left and not curr.right and not queue:
                return val
            if curr.left:
                queue.append((curr.left, val+1))
            if curr.right:
                queue.append((curr.right, val+1))
# Runtime: 36 ms, faster than 89.87% of Python3 online submissions for Maximum Depth of Binary Tree.
# Memory Usage: 15 MB, less than 90.62% of Python3 online submissions for Maximum Depth of Binary Tree.

dequeを使って実装してあります。

Deque とは、スタックとキューを一般化したものです (この名前は「デック」と発音され、これは「double-ended queue」の省略形です)。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。

とあるように速いです。実際にRuntimeに関しても他の回答に比べて速いですね。

ゼロから始めるLeetCode Day7 「104. Maximum Depth of Binary Tree」

概要

問題