LeetCode856-括号的分数

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/score-of-parentheses/

中文链接：https://leetcode-cn.com/problems/score-of-parentheses/

题目详述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

题目详解

  • 括号的分数由它的深度决定，为深度的 2 次幂。
  • 只用计算最内层括号的分数，遍历累加即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class LeetCode_00856 {

    public int scoreOfParentheses(String S) {
        int res = 0;
        for (int i = 0, d = 0; i < S.length(); ++i) {
            if (S.charAt(i) == '(') {
                ++d;
            } else {
                --d;
                if (S.charAt(i - 1) == '(') {
                    res += 1 << d;
                }
            }
        }
        return res;
    }
}