856. 括号的分數 : 簡單棧運用題

題目描述

這是 LeetCode 上的 ​​856. 括号的分數​​ ，難度為 中等。

Tag : 「棧」

給定一個平衡括号字元串 ​

​S​

​，按下述規則計算該字元串的分數：

• ​

  ​()​

  ​​ 得​

  ​1​

  ​ 分。
• ​

  ​AB​

  ​​ 得​

  ​A + B​

  ​​ 分，其中​

  ​A​

  ​​ 和​

  ​B​

  ​ 是平衡括号字元串。
• ​

  ​(A)​

  ​​ 得​

  ​2 * A​

  ​​ 分，其中​

  ​A​

  ​ 是平衡括号字元串。

示例 1：

輸入： "()"

輸出： 1      

示例 2：

輸入： "(())"

輸出： 2      

示例 3：

輸入： "()()"

輸出： 2      

示例 4：

輸入： "(()(()))"

輸出： 6      

提示：

• ​

  ​S​

  ​​ 是平衡括号字元串，且隻含有​

  ​(​

  ​​ 和​

  ​)​

  ​ 。

棧

初始化将答案 ​

​0​

​​ 放入棧中，從前往後處理整個 ​

​s​

​​，當遇到 ​

​(​

​​ 則存入一個占位數值 ​

​0​

​​，遇到 ​

​)​

​​ 取出棧頂元素 ​

​cur​

​，根據棧頂元素數值值分情況讨論：

• 棧頂元素，即目前的​​

  ​)​

  ​​ 的前一進制素即是​

  ​(​

  ​​ ，根據​

  ​()​

  ​​ 得一分的規則可知，我們本次操作得到的分值為；
• 棧頂元素，即目前​​

  ​)​

  ​​ 與其比對的​

  ​(​

  ​​ 中間相隔了其他字元，根據​

  ​(A)​

  ​​ 的得分規則，此時可知得分為；

将兩者結合可統一為 。

由于我們每次遇到 ​

​)​

​​ 時，都将最近一次操作計算出來。而再前面無論是 ​

​)​

​​ 還是 ​

​(​

​​ 我們都可以歸結到 ​

​X()​

​​ 的相鄰項累加規則，将其新得分累加到棧頂元素上，其中 ​

​(​

​​ 仍采用累加規則，則利用我們将 ​

​(​

​​ 定義為

Java 代碼：

class Solution {
    public int scoreOfParentheses(String s) {
        Deque<Integer> d = new ArrayDeque<>();
        d.addLast(0);
        for (char c : s.toCharArray()) {
            if (c == '(') d.addLast(0);
            else {
                int cur = d.pollLast();
                d.addLast(d.pollLast() + Math.max(cur * 2 , 1));
            }
        }
        return      

TypeScript 代碼：

function scoreOfParentheses(s: string): number {
    const stk = new Array<number>()
    stk.push(0)
    for (const c of s) {
        if (c == '(') stk.push(0)
        else {
            const cur = stk.pop()
            stk.push(stk.pop() + Math.max(cur * 2, 1))
        }
    }
    return stk.pop()
}      

Python 代碼：

class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        stk = [0]
        for c in s:
            if c == '(':
                stk.append(0)
            else:
                cur = stk.pop()
                stk.append(stk.pop() + max(cur * 2, 1))
        return stk[-1]      

• 時間複雜度：
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.856​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。