Keshawn_lu's Blog

Leetcode 856. 括号的分数

栈
字数统计: 295阅读时长: 1 min
2022/10/09 Share

题目简介：

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

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

示例 1：

1
2
输入： "()"
输出： 1

示例 2：

1
2
输入： "()()"
输出： 2

示例 3：

1
2
输入： "(()(()))"
输出： 6

提示：

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

思路：

利用栈，遇到(时压入0，遇到)时则将栈中遇到0（也就是对应的左括号）之前的所有数进行相加，如果相加count为0，则说明是()形式，否则，则为(A+B)形式，所以将max(2 * count, 1)压入栈。

最后，返回栈中所有数的和即可。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int scoreOfParentheses(string s) {

        stack<int> stk;
        stk.push(0);

        int count = 0;
        for(int i = 1; i < s.size(); i++){

            if(s[i] == '('){

                stk.push(0);
            }

            else{

                count = 0;
                while(stk.top() != 0){

                    count += stk.top();
                    stk.pop();
                }
                stk.pop();  //弹出对应的0
                stk.push(max(1, count * 2));       
            }
        }

        int res = 0;
        while(!stk.empty()){

            res += stk.top();
            stk.pop();
        }

        return res;
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网