侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【栈】括号的分数

GabrielxD
2022-10-09 / 0 评论 / 0 点赞 / 22 阅读 / 438 字 / 正在检测是否收录...

题目

856. 括号的分数


给定一个平衡括号字符串 S,按下述规则计算该字符串的分数:

  • () 得 1 分。
  • AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。
  • (A) 得 2 * A 分,其中 A 是平衡括号字符串。

示例 1:

输入: "()"
输出: 1

示例 2:

输入: "(())"
输出: 2

示例 3:

输入: "()()"
输出: 2

示例 4:

输入: "(()(()))"
输出: 6

提示:

  1. S 是平衡括号字符串,且只含有 ( 和 ) 。
  2. 2 <= S.length <= 50

解题

方法一:栈模拟

思路

维护一个栈(stk)记录分数,首先把 0 压入栈表示没有括号的时候得到的是 00 分,然后开始正序遍历字符串:

  • 如果遇到了 '(' ,向栈中压入一个 00 占位,因为该括号还未封闭。
  • 如果遇到了 ')' ,弹出栈顶元素(score):
    • 如果此时 score00 说明该括号中间没有嵌套,那么根据规则一该括号可以贡献的分数就是 11
    • 如果此时 score 不为 00 说明该括号中间有嵌套,那么根据规则三该括号可以贡献的分数就要翻倍为 score * 2
    • 然后再加上前一个括号的分数(规则二)就得到了字符串遍历到这里时的总分数。

最后返回栈顶元素就是 s 的分数。

代码

class Solution {
    public int scoreOfParentheses(String s) {
        Deque<Integer> stk = new LinkedList<>();
        stk.push(0);
        for (char ch : s.toCharArray()) {
            if (ch == '(') stk.push(0);
            else {
                int score = stk.pop();
                stk.push(stk.pop() + (score == 0 ? 1 : score * 2));
            }
        }
        return stk.pop();
    }
}
0

评论区