概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day43「5. Longest Palindromic Substring」
今はTop 100 Liked QuestionsのMediumを解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。
Twitterやってます。
問題
難易度はeasy。
Top 100 Liked Questionsからの抜粋です。
解いていたのに記事を書くのを忘れていたのを見つけたので書きます！
問題としては、二分木が与えられます。
その木の直径を調べ、二点間のノードの最も長い経路の長さを返すようなアルゴリズムを設計する、というものです。
1
/ \
2 3
/ \
4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
この場合は3が返されるとなっていますね。
解説
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.ans = 0
def dfs(node):
if not node:
return 0
right = dfs(node.right)
left = dfs(node.left)
self.ans = max(self.ans,left+right)
return max(left,right) + 1
dfs(root)
return self.ans
# Runtime: 40 ms, faster than 89.86% of Python3 online submissions for Diameter of Binary Tree.
# Memory Usage: 16 MB, less than 34.48% of Python3 online submissions for Diameter of Binary Tree.
深さ優先探索で深さを測り、直径なので最終的に親を経由するので+1をすれば解けます。
木の構造を理解できてれば比較的すんなり実装できるかと思います。
地味にてこずったとはいえない・・・
今回はここまで。お疲れ様でした！