AlgoPressAppearance
0856-括号的分数
题目描述
https://leetcode.cn/problems/score-of-parentheses
给定一个平衡括号字符串S，按下述规则计算该字符串的分数：
- () 得 1 分。
- AB 得A + B分，其中 A 和 B 是平衡括号字符串。
- (A) 得2 * A分，其中 A 是平衡括号字符串。
示例 1：
输入： "()"
输出： 1
示例 2：
输入： "(())"
输出： 2
示例3：
输入： "()()"
输出： 2
示例4：
输入： "(()(()))"
输出： 6
提示：
- S是平衡括号字符串，且只含有(和)。
- 2 <= S.length <= 50
思路1:递归【ME】
3种情况
- 如果是()直接返回
- 第一个括号一定是( 所以我们找和它对应闭合的括号 ) ，如果发现已经到末尾了，则取出中间的部分递归求解，然后 * 2
- 如果发现闭合的括号 ) 没有到尾部，则截取成两段，递归求解两段然后相加
csharp
public class Solution {
public int ScoreOfParentheses(string s) {
if(s.Length == 2){
return 1;
}
//处理分段找到第一个闭合的括号
int left = 1;
int right = 0;
int index = 0;
for(int i=1; i<s.Length; i++){
if(s[i] == '('){
left++;
}
else{
right++;
}
if(right == left){
index = i;
break;
}
}
if(index == s.Length - 1){ //双倍
//Console.WriteLine("double:{0}",index);
return 2 * ScoreOfParentheses(s.Substring(1,s.Length-2));
}
else{//分段
return ScoreOfParentheses(s.Substring(0,index+1)) + ScoreOfParentheses(s.Substring(index+1,s.Length-index-1));
}
}
}
思路2：栈【官方】
重点在于，先要push一个初始值0，然后依次计算中间值，并压入栈更新初始值
csharp
public class Solution {
public int ScoreOfParentheses(string s) {
Stack<int> stack = new Stack<int>();
stack.Push(0);
for(int i=0; i<s.Length; i++){
if(s[i] == '('){
stack.Push(0);
}
else{
int v = stack.Pop();
int result = stack.Pop() + Math.Max(2*v,1);
stack.Push(result);
}
}
return stack.Pop();
}
}
思路3：计算和【官方】
csharp
public class Solution {
public int ScoreOfParentheses(string s) {
int bal = 0, n = s.Length, res = 0;
for (int i = 0; i < n; i++) {
bal += (s[i] == '(' ? 1 : -1);
if (s[i] == ')' && s[i - 1] == '(') {
res += 1 << bal;
}
}
return res;
}
}