社区讨论LinuxDo 最新
Leetcode每日一题 —— 856. 括号的分数
力扣 LeetCode 856. 括号的分数 - 力扣（LeetCode） 856. 括号的分数 - 给定一个平衡括号字符串 S，按下述规则计算该字符串的分数： () 得 1 分。 AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。 (A) 得 2 A 分，其中 A 是平衡括号字符串。 示例 1： 输入： "()" 输出： 1 示例 2： 输入： "(())" 输出： 2 示例 3： 输入： "()()" 输出： 2 示例 4： 输入： "(()(()))" 输出： 6 提示： 1.... 思路 栈应…
内容摘要
作者：#SomeBottle
板块：#开发调优
力扣 LeetCode
856. 括号的分数 - 力扣（LeetCode）
856. 括号的分数 - 给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
* () 得 1 分。
* AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
* (A) 得 2 * A 分，其中 A 是平衡括号字符串。
示例 1：
输入： "()"
输出： 1
示例 2：
输入： "(())"
输出： 2
示例 3：
输入： "()()"
输出： 2
示例 4：
输入： "(()(()))"
输出： 6
提示：
1....
思路
栈应用题，表达式解析。
实际上我们只用在栈中维护得分以及标记出现的左括号，这里咱用 -1 来标记了左括号。遇到右括号时就可以开始弹栈，直至遇到左括号 (-1) 为止的分数都可以相加起来得到 sum，这个 sum 就是当前这一对括号的内层分数，需要计算 \mathrm{sum} \times 2。但注意内层可能没有括号，所以取的是 \max(\mathrm{sum} \times 2,\ 0)。
最后位于最外层，把栈中剩余的分数累加即可。
代码
class Solution {
public:
int scoreOfParentheses(string s) {
// 保证 s 是闭合的括号
// 维护一个存储得分的栈
stack<int> stk;
for(int i=0;i<s.size();i++){
if(s[i]=='('){
// 栈中用 -1 标记左括号
stk.emplace(-1);
}else if(s[i]==')'){
// 遇到右括号，弹栈直至遇到左括
资讯来源
LinuxDo