计数

括号的分数

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

• () 得 1 分。

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

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

856. 括号的分数 - 力扣（LeetCode）

我们通过观察发现，() 是唯一贡献分数的结构，外括号只是为该结构添加了一些乘数。所以我们只需要关心 ()。

我们用 d 维护当前括号的深度，对于每个 (，我们将深度加一，对于每个 )，我们将深度减一。当我们遇到 () 时，我们将 $$2^d$$ 加到答案中。

我们举个实际的例子，以 (()(())) 为例，我们首先找到内部两个闭合括号 ()，然后将分数加上对应的 $$2^d$$。实际上，我们是在计算 (()) + ((())) 的分数。

1
2
3
4
5

( ( ) ( ( ) ) )
  ^ ^   ^ ^

( ( ) ) + ( ( ( ) ) )
  ^ ^         ^ ^ 

1
2
3
4
5
6
7
8
9
10
11
12

int scoreOfParentheses(string s) {
      int d=0;
      int ans=0;
      for(int i=0;i<s.size();++i){
          if(s[i]=='(') d++;
          else{
              d--;
              if(s[i-1]=='(') ans+=1<<d;
          }
      }
      return ans;
    }

• ← Previous Post
• Next Post →