アルゴリズム-再帰とスタック、遅延計算

文書ディレクトリ

再帰

スタック

スタックおよび再帰

両端キューの条件再帰

再帰
再帰とは何か、大まかに言えば、前のステップに依存した結果を計算することです.
前のステップの計算を完了してこそ、最初の明確な値まで、現在の計算操作を行うことができます.
leecode 230でお話しします

         ，       kthSmallest        k       。

  ：
      k      ，1 ≤ k ≤          。

明らかに,中順に遍歴し,対応する配列のk−1 k−1 k−1番目の要素を取ればよい.
前順遍歴:r o o t→l e f t→r i g h t rootrightarrow leftrightarrow right root→left→right
中順遍歴:l e f t→r o o t→r i g h t leftrightarrow rootrightarrow right left→root→right
後順遍歴:l e f t→r i g h t→r o o t leftrightarrow rightrightarrow root left→right→root
このうち とは、rootの位置に対応していますので、間違えないでくださいね.

class Solution:
    def kthSmallest(self, root: TreeNode, k: int) -> int:
        container = []
        
        def collect(node: TreeNode):
            #    ，    
            if node is None:
                return
            #     ，     
            if (node.left is None) and (node.right is None):
                container.append(node.val)
            else:
                #    
                collect(node.left)
                #     
                container.append(node.val)
                #    
                collect(node.right)

        collect(root)
        return container[k - 1]

再帰を示すだけでなく、いくつかの法則を教えてくれます.

境界条件

再帰には、具体的な計算や操作、さらには直接的な答え(フィボナッチ数列)に対応する境界が必要です.

法則伝達

各ステップの計算は常に次のステップに依存し、その関係を設定する必要があります.
依存は計算依存とプロセス依存に分けられ,フィボナッチは計算依存に属するが,この例はプロセス依存にすぎない.
具体的な操作では,以前の計算に依存しない.
スタック
まずスタックの特性を復習します:単口出入り.

class Stack(object):

    def __init__(self):
        self.container = []

    def empty(self):
        return len(self.container) == 0

    def push(self, item):
        self.container.append(item)

    def pop(self):
        if self.empty():
            return None
        return self.container.pop(-1)

    def top(self):
        return self.container[-1]

leecode20

        '('，')'，'{'，'}'，'['，']'     ，         。

        ：

                。
             。
                。

class Solution:
    def isValid(self, s: str) -> bool:
        mapping = {'}': '{', ']': '[', ')': '('}
        stack = Stack()
        for item in s:
            #      
            if ' ' == item:
                continue
            if item in mapping:
                #      
                if stack.empty():
                    return False
                #       ，       
                if mapping[item] == stack.top():
                    stack.pop()
                #    ，    
                else:
                    return False
            else:
                stack.push(item)
        #      ，    
        return stack.empty()

スタックと再帰
本質的には、 は で実現されます.スタックには出口が1つしかないので、計算するたびに のデータしかありません.
同時に、スタックポートのデータはスタックトップのデータとインタラクティブになり、積み重ねられ、一歩一歩近づくことができます.
依存する遅延計算は、スタックに押し込むことができ、計算の番になると、前置的な依存が準備されています.
ただ、肝心なのは、一つの問題に対して再帰的な考え方を抽象化できるかどうかです.
leecode739

           ，        。        ：          ，         。             ，       0    。

  ，       temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，        [1, 1, 4, 2, 1, 1, 0, 0]。

直接解法は,繰返し計算が存在し,所定の数値が存在するのに,我々はなぜ何度も繰り返し計算するのか.
この考え方によれば,直接計算を行い,次のようなバージョンを得ることができる.

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        result = [0 for _ in range(len(T))]
        unknown = []
        for item in enumerate(T):
            #         
            if len(unknown) == 0:
                unknown.append(item)
                continue
            #           
            last = -1
            while -len(unknown) <= last < 0:
                someday = unknown[last]
                #              
                if item[1] > someday[1]:
                    result[someday[0]] = item[0] - someday[0]
                    del unknown[last]
                else:
                    #             
                    break
            #         
            unknown.append(item)

        return result

つかむべきものはすべてつかんで、唯一の肝心な点は再帰の思想を理解していないことです.
その後未知を添加するのは必ず温度が以前より小さい、すなわち、後ろを比較するには、前を比較しなければならない.
ここで採用した-1は,再帰の真髄ではなく,unknowの除去,配列操作の必要性にすぎない.

class Solution:
    def dailyTemperatures(self, T: List[int]) -> List[int]:
        result = [0 for _ in range(len(T))]
        unknown = Stack()

        for item in enumerate(T):
            if unknown.empty():
                unknown.push(item)
                continue
            while not unknown.empty():
                top = unknown.top()
                if item[1] > top[1]:
                    result[top[0]] = item[0] - top[0]
                    unknown.pop()
                else:
                    break
            unknown.push(item)

コードの簡潔さについては、listを使用してstackをシミュレートしたためと言いますが、これはその一方にすぎません.listシミュレーションstackを使用すると、動作は増加するが、前の方法は、既知の未知をどのように除去するかをよりよく考えているだけである.
データ構造の選択については,最初にlistを選択するのは誤りであり,再帰的には当然stackを用いるが,上は誤打に似ているだけである.
データ構造の選択を取り除くには、 の違いが鍵であり、同じやり方で、思想が異なり、価値が異なる.なぜなら、思想は移行できるからだ.
両端キューの条件再帰
leecode 239を見てみましょう

       nums，       k                      。              k    。             。

           。

暴力的なやり方は言わないで、私たちは両端の列の条件が再帰すると言っています.
最大値をフィルタします.

def max(*args):
    maxValue = args[0]
    for value in args[1:]:
        if value > maxValue:
            maxValue = value

はい、シングル出口の繰り返しは、もちろん再帰をご利用いただけます

def max(*args):
    stack = Stack()
    for value in args:
        if stack.empty():
            stack.push(value)
            continue
        if value > stack.top():
            stack.pop()
            stack.push(value)
    return stack.pop()

少し愚かなようですが、本質は同じで、特に非単一要素のフィルタリングでは、このようなやり方は絶対にもっと良いです.
この問題のポイントは2点にある.

期限切れ

つまりウィンドウの外、他のシーンでは、時間をウィンドウとすることが多いです.

サイズ

値の大きさの判断は、言うまでもなく.
最も重要なのは、有効な最大値のフィルタリングです.そのためには、選挙値を保留しなければならない.
特に、あなたが残した選挙値は、有効で、必ず有効でなければなりません.
問題全体は,本質的に有効候補値の最大値フィルタリングを行い,重複ペアリングをどのように回避するかに重点を置いている.
単一の値を使用すると、増加または減少しない限り、タスクを完了できません.listを使用すると、私たちはすべての記録ではなく、特殊な操作が余計に見えます.stackを考えると、有効な最大値を押し込むだけで、無効な最大値を除去することを保証すればいいだけです.
しかし、出口は一つしかありません.私たちは底を漏らす必要があります.

class Stack(object):

    def __init__(self, limit):
        self.limit = limit
        self.container = []

    def max(self):
        return self.container[0]

    '''
          ，    
    '''
    def valid(self, index):
        if index - self.container[0][0] >= self.limit:
            self.container.pop(0)

    '''
               ，      
    '''
    def push(self, item):
        while len(self.container) > 0:
            if self.container[-1][1]< item[1]:
                self.container.pop(-1)
            else:
                break
        self.container.append(item)
        self.valid(item[0])

ここでは、底漏れの機能をstack内部に維持しました.つまり、validはデータの有効性を検証し、その方向は正反対です.

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        stack = Stack(k)
        result = []
        for item in enumerate(nums):
            stack.push(item)
            if item[0] < k - 1:
                continue
            result.append(stack.max()[1])
        return result

最大値は、実際にはスタックの底にあり、リアルタイムの更新を保証し、その後は候補の有効最大値です.
後続の有効な最大値がスタックの最大値より大きいか、スタックの最大値が期限切れになっている場合にのみ、更新する必要はありません.
さらに重要なのは,スタック方向に秩序があり,フィルタリングの問題を考慮したことがないことである.
両端の列ですが、このようなシーンでは、 のstackと見なすのが好きです.