Pythonブラシノート:深さ優先検索テーマ

13449 ワード

今日は専門用語である深さ優先検索アルゴリズムに触れます(英語:Depth-First-Search,DFS)
深度優先検索アルゴリズム(英語:Depth-First-Search,DFS)は、ツリーまたは図を巡回または検索するためのアルゴリズムです.木の深さに沿って木のノードを巡り、できるだけ深く木の分岐を検索します.ノードvの存在するエッジが探索されると、探索は、ノードvが発見されたエッジの開始ノードに遡る.このプロセスは、ソースノードから到達可能なすべてのノードが発見されるまで行われます.発見されていないノードがまだ存在する場合は、いずれかをソースノードとして選択し、すべてのノードがアクセスされるまでプロセス全体を繰り返します.盲目的な検索に属します.
深さ優先探索は図論における古典的なアルゴリズムであり,深さ優先探索アルゴリズムを用いてターゲットマップの対応するトポロジーソートテーブルを生成することができ,トポロジーソートテーブルを用いて最大パス問題など多くの関連する図論問題を容易に解決することができる.リンク:https://leetcode-cn.com/tag/depth-first-search/出典:力ボタン(LeetCode)
ここで、アルゴリズムは、ツリーまたは図を巡回または検索するために多く使用されるが、二叉木を例にとると、このアルゴリズムは、可能な限りルートノードからリーフノードまで終了し、リーフノードに到達した後、ルートノードから再び下に延びる.
しかし,リーフノードに到達したときにルートノードに戻って再開するにはどうすればよいのだろうか.初接触、私の理解は再帰を通じて実現します.ルートノードの関数でサブノードに関する関数を呼び出し、親子間の関連付けを確立します.同時にそのサブノードが1つだけでない場合,遡及とは再帰同期によって実現される.
3つのLeetCodeのテーマを例に挙げて、深さ優先検索をどのように実現しているかを見てみましょう.
タイトル1
100番:同じ木
難易度:簡単
2つのツリーを指定し、同じかどうかを確認するために関数を作成します.
2つのツリーが構造的に同じで、ノードが同じ値を持っている場合は、同じとみなされます.

   1:
  :       1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
  : true

   2:
  :      1          1
          /           \
         2             2
        [1,2],     [1,null,2]
  : false

   3:
  :       1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
  : false

#  ：  （LeetCode）
#  ：https://leetcode-cn.com/problems/same-tree

テーマ分析
深さを優先的に検索する以上、ルートノードからサブノードに行けないまでチェーンを生成します.2つのツリーが同じであることを比較するには、このチェーンを生成する過程で各ノードが同じであることを保証すればよい.
構想は簡単ですが、コードまでどうやって実現しますか?この問題は2本の二叉木が同じかどうかを検出するため,自然に検出関数を定義する.二叉木はルートノードとサブツリーからなり、二本の二叉木が同じかどうかを検出します.私たちはルートノードが同じ場合、サブツリーが同じかどうかを検査することを保証します.注意して、サブツリーを検査し、定義した検出関数を呼び出して、再帰的な使い方を形成することができます.これにより、再帰的に深さ優先検索を実現することができます.
コード実装

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

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
    	#        ，   True
        if p is None  and q is None:
            return True
        #      、     ，   False
        elif p is None or q is None:
            return False
        #         ，       ，   False
        if p.val != q.val:
            return False
		#       ，                   
		#                
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)

テストパフォーマンスの送信:

     : 36 ms,     Python3        80.96%    
     : 13.5 MB,     Python3        7.14%

タイトル2
第101題:対称二叉木
難易度:簡単
二叉木を指定し、ミラー対称であるかどうかを確認します.
例えば、二叉木[1,2,2,3,4,4,3]は対称である.

しかし、以下の[1,2,2,null,3,null,3]はミラー対称ではありません.

テーマ分析
深度優先検索を使用しない場合は、レイヤシーケンスの遍歴を考慮できますが、空のサブノードでもレコードを遍歴することで、各レイヤのノードリストが対称かどうかを検出できます.
しかし、深さ優先検索を使用すると、2つのツリーが同じかどうかを比較するのと似ている場合は、サブノードを介して対称かどうかを比較するために設計された関数を多重化する方法を設計します.
この問題では、ルートノードと完全なツリーを1つだけ入力しますが、対称かどうかを確認するには、サブツリーが対称かどうかに基づいてください.サブツリーが対称であるかどうかをチェックする過程で、サブツリーのルートノードの位置は等しくなり、さらに下層のサブツリーは対応する位置のサブツリーと対称になり続け、2本のサブツリーが対称であるかどうかを検出する関数によって再帰を実現することができる.
コード実装

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

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
    	#        ，   True
        if not root:
            return True
        #             
        def check_sym(node1,node2):
        	#       ，   True
            if node1 is None and node2 is None:
                return True
            #       ，   False
            elif node1 is None or node2 is None:
                return False
            #          ，   ，   False
            if node1.val!=node2.val:
                return False
            #               ，    
            return check_sym(node1.left,node2.right) and check_sym(node1.right,node2.left)
		#       
        return check_sym(root.left,root.right)

テストパフォーマンスの送信:

     : 52 ms,     Python3        29.42%    
     : 13.7 MB,     Python3        6.06%

複雑度分析を加えてみましょう.私たちは二叉樹全体を1回遍歴し、n個のノードを共有しているので、時間複雑度はO(n)です.空間的には,運が良ければ各層が非対称を検出して返す必要はないかもしれないが,対称であればすべてのノードを再帰的に呼び出す必要があり,空間複雑度はO(n)である.
テーマ3
第104題:二叉木の最大深さ
難易度:簡単
ツリーに最大深さを指定します.
ツリーの深さは、ルートノードから最も遠いリーフノードまでの最長パス上のノード数です.
説明:リーフノードとは、サブノードがないノードを指します.
例:
与えられた二叉木[3,9,20,null,null,15,7]は、

最大深度3を返します.
テーマ分析
ルートノードは左右2本のサブツリーに対応し,二叉木の高さが大きいサブツリーの高さをさらに1つ加えると,サブツリーの高さはさらに大きなサブツリーの高さに1つ加算され,このように再帰的に形成される.
コード実装

# 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:
    	#         0
        if not root:
            return 0
        #              +1
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

テストパフォーマンスの送信:

     : 40 ms,     Python3        97.63%    
     : 15.5 MB,     Python3        5.55%

この時間の割合は正確ではないが,数msの差はずっと悪い.各サブツリーの高さを計算して比較するために、n個のノードが遍歴されるため、時間複雑度O(n);再帰もn回呼び出され、呼び出しスタックの記憶をO(n)に保つ.
結論
昨日は二叉樹の問題型が終わったのに、今日はアルゴリズムの特性で三つの問題が二叉樹だった.このアルゴリズムを学習し理解する過程で,深さ優先探索は概念的に増強されるだけで,かえって再帰的な応用に熟練している可能性がある.
下深さ優先探索の構想を簡単に整理し,ルートノードからリーフノードへの過程で多重化可能な関数を見つけて再帰過程を実現することで,再帰によって上から下へのつながりを非常に省力的に実現し,深さ探索の効果を達成する.
速く勉強するために、今日選んだのは簡単な問題で、その後はやはり難易度が違うので組み合わせたほうがいいです.

BitmapをSDカードに保存

XLBIew内にviewpagerを埋め込んで無限にANDマルチエントリを放送します