共计 1506 个字符，预计需要花费 4 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 856. 括号的分数 ，难度为 中等。
Tag :「栈」
给定一个均衡括号字符串 S，按下述规定计算该字符串的分数：
()得1分。AB得A + B分，其中A和B是均衡括号字符串。(A)得2 * A分，其中A是均衡括号字符串。
示例 1：
输出："()"
输入：1示例 2：
输出："(())"
输入：2示例 3：
输出："()()"
输入：2示例 4：
输出："(()(()))"
输入：6提醒：
S是均衡括号字符串，且只含有(和)。- $2 <= S.length <= 50$
栈
初始化将答案 0 放入栈中，从前往后解决整个 s，当遇到 ( 则存入一个占位数值 0，遇到 ) 取出栈顶元素 cur，依据栈顶元素数值值分状况探讨：
- 栈顶元素 $cur = 0$，即以后的
)的前一元素即是(，依据()得一分的规定可知，咱们本次操作失去的分值为 $1$； - 栈顶元素 $cur \neq 0$，即以后
)与其匹配的(两头相隔了其余字符，依据(A)的得分规定，此时可知得分为 $cur \times 2$；
将两者联合可对立为 $\max(cur \times 2, 1)$。
因为咱们每次遇到 ) 时，都将最近一次操作计算出来。而再后面无论是 ) 还是 ( 咱们都能够归结到 X() 的相邻项累加规定，将其新得分累加到栈顶元素上，其中 ( 仍采纳累加规定，则利用咱们将 ( 定义为 $0$ 的设定。
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 d.peekLast();}
}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]- 工夫复杂度：$O(n)$
- 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.856 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
正文完
