OFFERのために勉強を深め、スタックを理解しました.

@Author:Runsrn
@Date:2020/9/8
今の4つの基本はデータ構造とアルゴリズムを再ブラシすることです.筆記試験は本当に重要だからです.私はまた大物のコラムを争う宿を温めて、また強固にした.そして、伝言エリアの大物のノートがたくさんあることに気づきました.次の多くは大物からまとめられています.
文書ディレクトリ

一、スタックとは何ですか?

二、なぜスタックが必要ですか?

三、どのようにスタックを実現しますか?

四、スタックの応用

1.関数呼び出しにおけるスタックの適用

2.式の評価におけるスタックの適用(34+13*9+44-12/3など)

3.括弧マッチングにおけるスタックの応用`(例えば{}{[()}}})`Leetcode 20題

4.ブラウザの前進後退機能を実現するにはどうすればいいですか?

五、思考問題

六、20有効な拡張番号

7、155最小スタック(方法:補助スタック)

8,232はスタックでキュー

を実現する.

9、844は、退格を含む文字列

を比較する.

10、682野球

11、496次のより大きな要素I

一、スタックとは何ですか.
1.スタックは操作が制限されたデータ構造であり、インスタックとアウトスタックの操作のみをサポートする.2、典型的な「スタック」構造:後進者が先に出て、先進者が後に出る.3、スタックの操作特性から見ると、スタックは「操作制限」の線形表であり、一端でデータの挿入と削除しか許されない.4、特定のデータ構造は特定のシーンに対する抽象であり、また、配列やチェーンテーブルに多くの操作インタフェースが露出しており、操作上は確かに柔軟で自由であるが、使用時には制御不能であり、自然とエラーが発生しやすい.
二、どうしてスタックが必要ですか.
1.スタックは操作が制限されたデータ構造であり、その操作特性は配列とチェーンテーブルで実現できる.2.しかし、どのデータ構造も特定のアプリケーションシーンの抽象であり、配列やチェーンテーブルはより柔軟に使用されているが、ほとんどの操作が暴露され、誤った操作のリスクを引き起こすことは避けられない.3.したがって、あるデータセットが、あるエンドでのデータの挿入と削除のみに関連し、後進者が先に出て、先進者が後で出てくる操作特性を満たす場合、スタックというデータ構造を優先すべきである.
三、どのようにスタックを実現しますか?
1.スタックのAPI、Javaコード実装、コードは競合者から来ている.

//           
public class ArrayStack {
     
  private String[] items;  //   
  private int count;       //       
  private int n;           //    

  //      ，       n     
  public ArrayStack(int n) {
     
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  //     
  public boolean push(String item) {
     
    //        ，    false，    。
    if (count == n) return false;
    //  item     count   ，  count  
    items[count] = item;
    ++count;
    return true;
  }
  
  //     
  public String pop() {
     
    //    ，     null
    if (count == 0) return null;
    //      count-1     ，        count  
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

2.配列実装(自動拡張)
時間複雑度分析:均等複雑度の定義に基づいて、配列実装(自動拡張)が多くの場合O(1)レベル複雑度、個別の場合O(n)レベル複雑度、例えば自動拡張時に完全なデータのコピーを行うことができる.
空間複雑度解析:インスタックとアウトスタックの間に一時変数ストレージ領域が1つまたは2つしか必要ないため、O(1)レベルです.空間の複雑さとは,元のデータ記憶空間に加えてアルゴリズムの実行に余分な記憶空間が必要であることを意味する.
3.チェーンテーブル実装
時間複雑度解析:スタックとスタックの時間複雑度は、単一ノードのインデックスを変更するだけで済むため、O(1)レベルです.空間複雑度解析:インスタックとアウトスタックの間に一時変数ストレージ領域が1つまたは2つしか必要ないため、O(1)レベルです.空間の複雑さとは,元のデータ記憶空間に加えてアルゴリズムの実行に余分な記憶空間が必要であることを意味する.
四、スタックの応用
1.関数呼び出しにおけるスタックの適用
オペレーティングシステムは、関数呼び出し時の一時変数を格納するために「スタック」という構造に組織された独立したメモリ領域を各スレッドに割り当てます.1つの関数に入るたびに、その中の一時変数をスタックフレームとしてスタックに入れ、呼び出された関数の実行が完了し、戻った後、この関数に対応するスタックフレームをスタックから出す.
2.式評価におけるスタックの適用(例:34+13*9+44-12/3)
2つのスタックを使用して、1つはオペランドを保存し、もう1つは演算子を保存します.私たちは左から右に式を巡り、数字に出会ったら、操作数スタックに直接押し込みます.演算子に遭遇すると、演算子スタックのスタックトップ要素と比較し、演算子スタックトップ要素より優先度が高い場合は、現在の演算子をスタックに押し込み、演算子スタックトップ要素より優先度が低い場合や同じ場合は、演算子スタックからスタックトップ演算子を取り出し、オペランドスタックトップから2つのオペランドを取り出し、計算を行い、計算した結果をオペランドスタックに押し込み、比較を続行します.
3.括弧マッチングにおけるスタックの応用（ ：{}{[()]()}） Leetcode 20題
スタックで一致する左かっことして保存し、左から右に文字列をスキャンし、左かっこにスキャンするとスタックに押し込みます.右かっこにスキャンすると、スタックの上部から左かっこが取り出され、一致する場合は残りの文字列のスキャンが続行されます.スキャン中にペアリングできない右かっこが発生した場合、またはスタックにデータがない場合は、不正なフォーマットとして説明されます.
すべてのカッコのスキャンが完了すると、スタックが空の場合、文字列が合法的なフォーマットであることを示します.それ以外の場合は、一致しない左かっこが不正なフォーマットであることを示します.
4.ブラウザの前進後退機能をどのように実現しますか?
2つのスタックXとYを使用して、初めて閲覧したページをスタックXのように順番に押して、後退ボタンをクリックすると、スタックXから順番にスタックを出て、スタックのデータを一度にYスタックに入れます.前進ボタンをクリックすると,スタックYから順にデータを取り出し,スタックXに入れる.スタックXにデータがない場合、ページがないことを説明して後退して閲覧を続けることができます.Yスタックにデータがない場合は、ページがないのでクリックして閲覧できます.
五、思考問題
スタックの応用について、関数呼び出しスタックで一時変数を保存することについて話しますが、なぜ関数呼び出しは「スタック」で一時変数を保存するのでしょうか.他のデータ構造ではだめですか?
答え:関数呼び出しの実行順序は後進者先出,先進者後出の特徴に合致するからである.例えば、関数の局所変数のライフサイクルの長さは、先に定義されたライフサイクルが長く、後に定義されたライフサイクルが短い.また、関数の呼び出し関数も同様であり、先に実行を開始した関数は、内部で呼び出された他の関数が実行されるまで待ってこそ、その関数が実行される.
これらの関数呼び出しの特徴により,データ構造が特定の応用シーンの抽象的な原則であることから,スタック構造を優先的に考慮した.
JVMメモリ管理には「スタック」という概念があることはよく知られています.スタックメモリはローカル変数とメソッド呼び出しを格納し、スタックメモリはJava内のオブジェクトを格納します.では、JVMの中の「スタック」は私たちがここで言っている「スタック」と同じではないでしょうか.そうでなければ、なぜ「桟」と呼ばれているのでしょうか.
答え:JVMの中のスタックは私たちがここで言っているのと同じことで、メソッドスタックと呼ばれています.メソッド内のローカル変数を格納するために、前の関数呼び出しの役割と一致します.
leetcodeのスタックに関するテーマは、まず201552328442244682496を作ることができます.もう一度書いてください.難易度は以前ほど大きくありません.
六、20有効な拡張子

'''
@Author： Runsen
@WeChat：RunsenLiu 
@     ： Python  
@CSDN： https://blog.csdn.net/weixin_44510615
@Github： https://github.com/MaoliRUNsen
@Date： 2020/9/8
'''
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        d = {
     "{": "}", "[": "]", "(": ")"}
        for i in s:
            if i in d:
                stack.append(i)
            else:
                #        stack.pop()            pop       
                #   not stack  len(stack) == 0  
                if  (len(stack) == 0) or (d[stack.pop()] != i):
                    return False
        return len(stack) == 0 

7、155最小スタック(方法:補助スタック)

class MinStack:
    def __init__(self):
    #      ，q2      
        self.q1 = []
        self.q2 = []

    def push(self, x):
        self.q1.append(x)
        #       q2     ，  q2[-1]  x，       q2[-1]，
        if (len(self.q2) == 0) or (x <=self.q2[-1]):
            self.q2.append(x)
        else:
            #   q2   q2[-1】
            self.q2.append(self.q2[-1])

    def pop(self):
        #      q1 q2    
        self.q1.pop()
        self.q2.pop()

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

    def getMin(self):
        return self.q2[-1]

8、232スタックでキューを実現

class MyQueue:
    def __init__(self):
        self.s = []
    def push(self, x: int) -> None:
        self.s.append(x)
    def pop(self) -> int:    
        return self.s.pop(0)
    def peek(self) -> int:
        return self.s[0]
    def empty(self) -> bool:
        return not bool(self.s)
        # return not self.s      

ここで、上記の有効な拡張番号のnot stackを思い出し、bool stackと比較しました

>>> a = []
>>> not a
True
>>> bool(a)
False
>>> a = [1]
>>> not a
False
>>> bool(a)
True

not aはlen(a) == 0で、boolはlen(a) != 0です.感じてくる
9、844チェックアウト文字列の比較

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
         #              
        def solve(s):
            #      ，      #      
            stack = []
            for i in s:
                if i == "#":
                    if len(stack) !=0:
                        stack.pop()
                    else:
                        continue
                else:
                    stack.append(i)
                
            return ''.join(stack)
        return solve(S) == solve(T)

10、682野球

class Solution:
    def calPoints(self, ops: List[str]) -> int:
        #               
        stack1  = []
        for i in ops:
            if i == "C":
                #         
                stack1.pop()
            elif i =="D":
                stack1.append(stack1[-1] * 2)
            elif i == "+":
                stack1.append(stack1[-1] + stack1[-2])
            else:
                stack1.append(int(i))
        return sum(stack1)

11、496次の大きな要素I
入力:nums 1=[4,1,2]、nums 2=[1,3,4,2].出力:[-1,3,-1]解釈:num 1の数字4では、2番目の配列で次のより大きな数字を見つけることができないので、-1を出力します.num 1の数字1の場合、2番目の配列の数字1の右側の次の大きな数字は3です.num 1の数字2の場合、2番目の配列には次のより大きな数字がないため、-1が出力されます.

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        for i in nums1:
            index = nums2.index(i)
            #   index           
            if index == (len(nums2) - 1):
                stack.append(-1)
                continue
            else:
                #          index+1       
                while index < len(nums2):
                    if nums2[index] > i:
                        stack.append(nums2[index])
                        break
                    if index == len(nums2) -1 and (nums2[index] > i):
                        stack.append(nums2[index])
                    if index == len(nums2) -1 and (nums2[index] <= i):
                        stack.append(-1)
                    index  = index + 1
        return stack

上はすべて合格して、后でスタックに出会って、恐怖のアルゴリズムの面接の中で爱情に出会ったのです!!!
ブロガーと親密な関係を築きたい場合は、ブロガーに注目したり、ブロガーの公衆番号「Pythonの王」に注目したりして、学部以外のプログラマーがどのように成長しているかを知ることができます.ブロガーID:潤森(weixin_44510615)、皆さんにいいね、コメント、コレクションをお願いします