【leetcode刷题】T28-括号的分数
【英文题目】（学习英语的同时，更能理解题意哟~）
Given a balanced parentheses string S, compute the score of the string based on the following rule:
()has score 1ABhas scoreA + B, where A and B are balanced parentheses strings.(A)has score2 * A, where A is a balanced parentheses string.
Example 1:
Input: "()"
Output:
Example 2:
Input: "(())"
Output:
【中文题目】
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
()得 1 分。AB得A + B分，其中 A 和 B 是平衡括号字符串。(A)得2 * A分，其中 A 是平衡括号字符串。
示例 1：
输入： "()"
输出：
示例 2：
输入： "(())"
输出：
【思路】
第一种解法，使用栈结构：遇到"("则压入栈；遇到")"，若栈顶元素为"("，修改栈顶元素为1；若栈顶元素为数字，则不断判断栈顶元素是否为数字并弹出，计算累加值，直到栈顶元素为"("，这时修改栈顶元素为2倍累加值。最后返回栈中所有元素的和即可。
第二种解法，统计每个"()"（必须一起出现）的深度，计算相应得分，进行累加。比如“((())())”，计算粗体划线部分的深度"((())())"，分别为3和2，得分为2^(3-1)=4和2^(2-1)=2，总分为6
【代码】
python版本
栈结构
class Solution(object):
def scoreOfParentheses(self, s):
"""
:type s: str
:rtype: int
"""
ls = []
for si in s:
if si == '(':
ls.append('(')
else:
if ls[-1] == '(':
ls[-1] =
else:
tmp = ls.pop()
while ls[-1] != '(':
tmp += ls.pop()
tmp *=
ls[-1] = tmp
return sum(ls)
统计括号深度
class Solution(object):
def scoreOfParentheses(self, s):
"""
:type s: str
:rtype: int
"""
depth =
res =
for i, si in enumerate(s):
if si == '(':
depth +=
else:
depth -=
if s[i-1] == '(':
res += ** (depth)
return res
C++版本
栈结构
class Solution {
public:
int scoreOfParentheses(string S) {
stack<string> ls;
for(int i=; i<S.length(); i++){
if(S[i] == '(')
ls.push("(");
else{
// 字符串符合规范，不用考虑溢出
if(ls.top() == "("){
ls.pop();
ls.push("1");
}else{
int tmp = ;
while(ls.top() != "("){
tmp += atoi(ls.top().c_str());
ls.pop();
}
tmp *= ;
ls.pop();
std::stringstream s1;
s1 << tmp;
string s2;
s1 >> s2;
ls.push(s2);
}
}
}
int res=;
while(!ls.empty()){
cout << ls.top() << endl;
res += atoi(ls.top().c_str());
ls.pop();
}
return res;
}
};
统计括号深度
class Solution {
public:
int scoreOfParentheses(string S) {
int depth = ;
int res = ;
for(int i=; i<S.length(); i++){
if(S[i] == '(')
depth++;
else{
depth--;
// 字符串符合规范，不用考虑溢出
if(S[i-1] == '('){
res += << depth;
}
}
}
return res;
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读