ゼロから始めるLeetCode Day32「437. Path Sum III」

概要

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

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

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

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day31「581. Shortest Unsorted Continuous Subarray」
次回
ゼロから始めるLeetCode Day33「1. Two Sum」

問題

437. Path Sum III
難易度はeasy。
Top 100 Liked Questionsのeasyがこれを入れて残り三問となりました。

各ノードに整数値が含まれている二分木が与えられます。

ノードの値を合計して特定の値sumになるパスの数を求めます。

経路は親または葉で開始または終了する必要はありませんが、下方向に移動する必要があります(親ノードから子ノードへの移動のみ)。

なお、ツリーのノード数は1,000以下で、値の範囲は-1,000,000〜1,000,000です。

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8


      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

  1. 5 -> 3
  1. 5 -> 2 -> 1
  2. -3 -> 11

解法

再帰を使ったdfsで解きました。

# 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:
    ans = 0
    def pathSum(self, root: TreeNode, sum: int) -> int:
        def dfs(root,sums,start):
            if not root:
                return 0
            sums -= root.val
            if sums == 0:
                self.ans += 1
            dfs(root.left,sums,False)
            dfs(root.right,sums,False)
            if start:
                dfs(root.left,sum,True)
                dfs(root.right,sum,True)
        dfs(root,sum,True)
        return self.ans
# Runtime: 940 ms, faster than 24.67% of Python3 online submissions for Path Sum III.
# Memory Usage: 15.1 MB, less than 6.82% of Python3 online submissions for Path Sum III.

最初はrootsumsだけでかけるかと思って書いていたのですが、どうもそれだけでは書けなかった(書けるかもしれないが今の私の頭では思いつかなかった)ので、discussを覗いたらほとんど一緒の解答があり、そこでは現在のnodeを始点として扱うためにbooleanを用いており、非常にすっきりとした実装ができたのでそのままこちらを載せておきます。

それにしてもアルゴリズム強い人すごい・・・

もっと精進しなければならないですね。

良さげな解答があれば追記します。

コメント

このブログの人気の投稿

Braveブラウザの同期機能をiPhoneで設定した話。

failed: unable to get local issuer certificate (_ssl.c:1123)と出たので解決した話

自作のChrome Extensionをインポートした時に "Invalid value for 'content_scripts[0].matches[0]': Empty path."というエラーが出たので解決した