刷穿劍指offer-Day17-棧I 棧的使用與基礎題型！

刷穿劍指offer-Day17-棧I 棧的使用與基礎題型

棧的介紹

棧(stack) 本身是一種簡單、常用的數(shù)據(jù)結構，它常常用來和隊列進行比較。

  • 隊列： 先入先出
  • 棧： 后入先出

棧的所有操作都發(fā)生在棧頂，其實就三個操作，入棧(壓棧)、出棧(彈棧)、獲取棧頂元素。

Python & Java 中的棧

Java中存在Stack的數(shù)據(jù)結構，但Python是沒有棧的，它們的實現(xiàn)與操作方式如下：

操作 Python Java 說明
初始化 Stack<Integer> stack = new Stack<>(); stack = []
入棧 stack.push(1); stack.append(1)
出棧 stack.pop(); stack.pop() 為空時報錯
獲取棧頂元素 stack.peek(); stack[-1] 為空時報錯

棧的操作就是這幾個，是不是很簡單，要不直接下一章？too young，too simple！

棧的操作是簡單的，但是棧在算法中的應用確實變化多端....有些題目打眼一看就是棧操作，比如 括號匹配。但更多的題目并不是能直接看出來通過棧去解決的。比如單調(diào)棧等類型的題目，真的是新手勸退神器....

但飯要一口一口吃，讓我們先來看一道簡單的括號匹配問題，熟悉下棧的操作吧。

1021.刪除最外層的括號

https://leetcode-cn.com/problems/remove-outermost-parentheses/solution/1021shan-chu-zui-wai-ceng-de-gua-hao-li-v8c1c/

難度：簡單

題目

有效括號字符串為空 ""、"(" + A + ")" 或 A + B ，其中 A 和 B 都是有效的括號字符串，+ 代表字符串的連接。

例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括號字符串。
如果有效字符串 s 非空，且不存在將其拆分為 s = A + B 的方法，我們稱其為原語（primitive），其中 A 和 B 都是非空有效括號字符串。

給出一個非空有效字符串 s，考慮將其進行原語化分解，使得：s = P_1 + P_2 + ... + P_k，其中 P_i 是有效括號字符串原語。

對 s 進行原語化分解，刪除分解中每個原語字符串的最外層括號，返回 s 。

提示：

  • 1 <= s.length <= 10 ^ 5
  • s[i] 為 '(' 或 ')'
  • s 是一個有效括號字符串

示例

示例 1：
輸入：s = "(()())(())"
輸出："()()()"
解釋：
輸入字符串為 "(()())(())"，原語化分解得到 "(()())" + "(())"，
刪除每個部分中的最外層括號后得到 "()()" + "()" = "()()()"。

示例 2：
輸入：s = "(()())(())(()(()))"
輸出："()()()()(())"
解釋：
輸入字符串為 "(()())(())(()(()))"，原語化分解得到 "(()())" + "(())" + "(()(()))"，
刪除每個部分中的最外層括號后得到 "()()" + "()" + "()(())" = "()()()()(())"。

示例 3：
輸入：s = "()()"
輸出：""
解釋：
輸入字符串為 "()()"，原語化分解得到 "()" + "()"，
刪除每個部分中的最外層括號后得到 "" + "" = ""。

分析

這道題本身并不麻煩，主要是理解這句原語的含義：

如果有效字符串 s 非空，且不存在將其拆分為 s = A + B 的方法，我們稱其為原語

其實就是每獲取一組左右括號相等的搭配后，將左右括號各刪除一個，并保存即可。
由于這道題目提供的用例都是滿足括號匹配關系的內(nèi)容，使得這道題的難度就更低了。

  1. 我們創(chuàng)建一個字符串用于接收每次獲取的原語進行拼接
  2. 然后創(chuàng)建一個棧，開始循環(huán)s，進行棧的入棧操作，每次入棧的是s的下標
  3. 左括號直接入棧，右括號時彈出棧頂，并判斷棧是否為空，為空則代表找到一對匹配內(nèi)容
  4. 此時獲取棧頂index以及當前循環(huán)的下標i，ret += s[left+1:i]（刪除最外層的左右括號）即可。

解題

Python:

class Solution:
    def removeOuterParentheses(self, s):
        ret = ""
        stack = []
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            else:
                left = stack.pop()
                if not stack:
                    ret += s[left + 1:i]
        return ret

Java:

class Solution {
    public String removeOuterParentheses(String s) {
        Stack<Integer> stack = new Stack<>();
        StringBuilder ret = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') stack.push(i);
            else {
                int index = stack.pop();
                if (stack.empty()) {
                    ret.append(s.substring(index + 1, i));
                }
            }
        }
        return ret.toString();
    }
}

看過了上面這道簡單的棧題目，下來就該完成書中相關的題目了。

劍指OfferII036.后綴表達式

https://leetcode-cn.com/problems/8Zf90G/solution/shua-chuan-jian-zhi-offer-day10-zi-fu-ch-c9f1/

難度：中等

題目

根據(jù) 逆波蘭表示法，求表達式的值。
有效的算符包括+、-、*、/。每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達式。

說明：

  • 整數(shù)除法只保留整數(shù)部分。
  • 給定逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數(shù)值且不存在除數(shù)為 0 的情況。

提示：

  • 1 <= tokens.length <= 10 ^ 4
  • tokens[i] 要么是一個算符（"+"、"-"、"*" 或 "/"），要么是一個在范圍 [-200, 200] 內(nèi)的整數(shù)

逆波蘭表達式：

逆波蘭表達式是一種后綴表達式，所謂后綴就是指算符寫在后面。

  • 平常使用的算式則是一種中綴表達式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
  • 該算式的逆波蘭表達式寫法為 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波蘭表達式主要有以下兩個優(yōu)點：

  • 去掉括號后表達式無歧義，上式即便寫成 1 2 + 3 4 + * 也可以依據(jù)次序計算出正確結果。
  • 適合用棧操作運算：遇到數(shù)字則入棧；遇到算符則取出棧頂兩個數(shù)字進行計算，并將結果壓入棧中。

示例

示例1：
輸入：tokens = ["2","1","+","3","*"]
輸出：9
解釋：該算式轉(zhuǎn)化為常見的中綴算術表達式為：((2 + 1) * 3) = 9

示例2：
輸入：tokens = ["4","13","5","/","+"]
輸出：6
解釋：該算式轉(zhuǎn)化為常見的中綴算術表達式為：(4 + (13 / 5)) = 6

示例3：
輸入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
輸出：22

解釋：
該算式轉(zhuǎn)化為常見的中綴算術表達式為：

  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

分析

  1. 根據(jù)題目所知，輸入的逆波蘭表達式都是有效的，所以無需考慮特殊的場景。
  2. 既然是一道棧的題目，肯定要先創(chuàng)建一個stack，然后依次將元素入棧，但什么時候出棧呢？
  3. 后綴表達式是指算符寫在后面，即當我們遇到操作符時，需要將操作符緊鄰的前兩項拿出來進行計算
  4. 在第3步計算完成后，還需要將結果重新加入棧中
  5. 最終將計算結果返回即可

解題

Python:

class Solution:
    def evalRPN(self, tokens):
        stack = []
        calc = {'+': lambda x, y: x + y,
                '-': lambda x, y: x - y,
                '*': lambda x, y: x * y,
                '/': lambda x, y: int(x / y), }
        for i in tokens:
            if i in calc:
                num2, num1 = stack.pop(), stack.pop()
                stack.append(calc[i](num1, num2))
            else:
                stack.append(int(i))
        return stack[0]

Java:

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String c : tokens) {
            switch (c) {
                case "+":
                case "-":
                case "*":
                case "/":
                    int num2 = stack.pop();
                    int num1 = stack.pop();
                    stack.push(calc(num1, num2, c));
                    break;
                default:
                    stack.push(Integer.parseInt(c));
            }
        }
        return stack.pop();
    }

    private int calc(int a, int b, String op) {
        switch (op) {
            case "+":
                return a + b;
            case "-":
                return a - b;
            case "*":
                return a * b;
            default:
                return a / b;
        }
    }
}

雖說是一道中等題目，但僅僅是多了幾種判斷而已，主要能第一時間想到棧的套路，那離AC也就不差多少了....

下面再來一道同等難度的題目，考驗下大家在場景分析中對棧的理解！

劍指OfferII037.小行星碰撞

https://leetcode-cn.com/problems/XagZNi/solution/shua-chuan-jian-zhi-offer-day17-zhan-i-0-5yho/

難度：中等

題目

給定一個整數(shù)數(shù)組 asteroids，表示在同一行的小行星。
對于數(shù)組中的每一個元素，其絕對值表示小行星的大小，正負表示小行星的移動方向（正表示向右移動，負表示向左移動）。每一顆小行星以相同的速度移動。
找出碰撞后剩下的所有小行星。碰撞規(guī)則：兩個行星相互碰撞，較小的行星會爆炸。如果兩顆行星大小相同，則兩顆行星都會爆炸。兩顆移動方向相同的行星，永遠不會發(fā)生碰撞。

提示：

  • 2 <= asteroids.length <= 10 ^ 4
  • -1000 <= asteroids[i] <= 1000
  • asteroids[i] != 0

示例

示例 1：
輸入：asteroids = [5,10,-5]
輸出：[5,10]
解釋：10 和 -5 碰撞后只剩下 10 。 5 和 10 永遠不會發(fā)生碰撞。

示例 2：
輸入：asteroids = [8,-8]
輸出：[]
解釋：8 和 -8 碰撞后，兩者都發(fā)生爆炸。

示例 3：
輸入：asteroids = [10,2,-5]
輸出：[10]
解釋：2 和 -5 發(fā)生碰撞后剩下 -5 。10 和 -5 發(fā)生碰撞后剩下 10 。

示例 4：
輸入：asteroids = [-2,-1,1,2]
輸出：[-2,-1,1,2]
解釋：-2 和 -1 向左移動，而 1 和 2 向右移動。 
     由于移動方向相同的行星不會發(fā)生碰撞，所以最終沒有行星發(fā)生碰撞。

分析

這道棧的題目難點應該主要是在分析場景上了。 我們需要明確什么時候無腦入棧，什么時候需要判斷，理解這兩點就可以輕松解題了。 首先，循環(huán)每一個元素時，在什么情況下無腦入棧呢？

  1. 棧為空
  2. 棧頂元素為負數(shù)(下一個為負數(shù)則一起向左，下一個為正數(shù)則分向兩邊)
  3. 當前元素為正數(shù)（棧頂為正一起向左，棧頂為負分向兩邊）

下來，我們需要看碰撞的場景又細分為什么情況：

  1. 棧頂元素大于abs(當前元素)，當前元素被撞毀
  2. 棧頂元素等于abs(當前元素)，棧頂彈出和當前元素抵消
  3. 棧頂元素小于abs(當前元素)，棧頂彈出，并與新棧頂完成上述判斷

最終返回棧即可。

解題

Python:

class Solution:
    def asteroidCollision(self, asteroids):
        s, p = [], 0
        while p < len(asteroids):
            if not s or s[-1] < 0 or asteroids[p] > 0:
                s.append(asteroids[p])
            elif s[-1] <= -asteroids[p]:
                if s.pop() < -asteroids[p]:
                    continue
            p += 1
        return s

Java:

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        Stack<Integer> s = new Stack<>();
        int p = 0;
        while (p < asteroids.length) {
            if (s.empty() || s.peek() < 0 || asteroids[p] > 0) {
                s.push(asteroids[p]);
            } else if (s.peek() <= -asteroids[p]) {
                if (s.pop() < -asteroids[p]) {
                    continue;
                }
            }
            p++;
        }
        int[] ret = new int[s.size()];
        for (int i = ret.length - 1; i >= 0; i--) {
            ret[i] = s.pop();
        }
        return ret;
    }
}

那么，今天關于棧的基礎操作就先學習到這里，關于棧的特殊場景單調(diào)棧，將在明天開始學習。

歡迎關注我的公眾號: 清風Python，帶你每日學習Python算法刷題的同時，了解更多python小知識。

我的個人博客：https://qingfengpython.cn

力扣解題合集：https://github.com/BreezePython/AlgorithmMarkdown

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容