递归，分治，栈，顺序遍历深度，4 解法求解《856. 括号的分数》
例题
856. 括号的分数
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。
示例 1：
输入： "()"
输出： 1
示例 2：
输入： "(())"
输出： 2
示例 3：
输入： "()()"
输出： 2
示例 4：
输入： "(()(()))"
输出： 6
提示：
S 是平衡括号字符串，且只含有 ( 和 ) 。
2 <= S.length <= 50
答案
递归
var scoreOfParentheses = function(s) {
const n = s.length
let r = 0
for (let i = 0, d = 0, start = 0; i < n; i++) {
if (s[i] === '(') d++
else d--
if (d === 0) {
if (i - start === 1) r += 1
else r += 2 * scoreOfParentheses(s.slice(start + 1, i))
start = i + 1
}
}
return r
};分治
var scoreOfParentheses = function(s) {
const n = s.length
let i = 0
for (let d = 0; i < n; i++) {
if (s[i] === '(') d++
else d--
if (d === 0) break
}
const t = i + 1 < n ? scoreOfParentheses(s.slice(i + 1)) : 0
if (i === 1) return 1 + t
return 2 * scoreOfParentheses(s.slice(1, i)) + t
};栈
var scoreOfParentheses = function(s) {
const stack = [0], n = s.length
for (let i = 0; i < n; i++) {
if (s[i] === '(') stack.push(0)
else stack.push(Math.max(stack.pop() << 1, 1) + stack.pop())
}
return stack[0]
};class Solution {
public int scoreOfParentheses(String s) {
ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
int n = s.length();
stack.push(0);
for (int i = 0; i < n; i++) {
if (s.charAt(i) == '(') stack.push(0);
else stack.push(Math.max(stack.pop() << 1, 1) + stack.pop());
}
return stack.peek();
}
}顺序遍历深度
分数 = () 贡献分数之和
() 贡献分数 = 1 << () 所在深度
var scoreOfParentheses = function(s) {
const n = s.length
let r = 0
for (let i = 0, d = 0; i < n; i++) {
if (s[i] === '(') d++
else {
d--
if (s[i - 1] === '(') r += 1 << d
}
}
return r
};function scoreOfParentheses(s: string): number {
const n = s.length
let r = 0
for (let i = 0, d = 0; i < n; i++) {
if (s[i] === '(') d++
else {
d--
if (s[i - 1] === '(') r += 1 << d
}
}
return r
};class Solution {
function scoreOfParentheses($s) {
$n = strlen($s);
$r = 0;
for ($i = 0, $d = 0; $i < $n; $i++) {
if ($s[$i] === '(') $d++;
else {
$d--;
if ($s[$i - 1] === '(') $r += 1 << $d;
}
}
return $r;
}
}func scoreOfParentheses(s string) int {
r, d := 0, 0
for i, c := range s {
if c == '(' {
d++
} else {
d--
if s[i - 1] == '(' {
r += 1 << d
}
}
}
return r
}class Solution {
public int scoreOfParentheses(String s) {
int n = s.length(), r = 0;
for (int i = 0, d = 0; i < n; i++) {
if (s.charAt(i) == '(') d++;
else {
d--;
if (s.charAt(i - 1) == '(') r += 1 << d;
}
}
return r;
}
}public class Solution {
public int ScoreOfParentheses(string s) {
int n = s.Length, r = 0;
for (int i = 0, d = 0; i < n; i++) {
if (s[i] == '(') d++;
else {
d--;
if (s[i - 1] == '(') r += 1 << d;
}
}
return r;
}
}int scoreOfParentheses(char * s){
int n = strlen(s), r = 0;
for (int i = 0, d = 0; i < n; i++) {
if (s[i] == '(') d++;
else {
d--;
if (s[i - 1] == '(') r += 1 << d;
}
}
return r;
}class Solution {
public:
int scoreOfParentheses(string s) {
int n = s.size(), r = 0;
for (int i = 0, d = 0; i < n; i++) {
if (s[i] == '(') d++;
else {
d--;
if (s[i - 1] == '(') r += 1 << d;
}
}
return r;
}
};class Solution:
def scoreOfParentheses(self, s: str) -> int:
n, r, d = len(s), 0, 0
for i, c in enumerate(s):
if c == '(': d += 1
else:
d -= 1
if s[i - 1] == '(': r += 1 << d
return r