括号的分数 图解题解

这道题到底在问什么

输入

S = "()"

输出

1　(一对空括号)

输入

S = "(())"

输出

2　(里面 1 分,外面包一层翻倍)

输入

S = "()()"

输出

2　(两对并排,1 加 1)

先想最直接的笨办法

开始之前,先在栈底放一个 0。这个 0 代表「最外面一层」当前的累计分数,所有算出来的分最终都会汇总到它身上。上方一排是要依次处理的 8 个括号,我们从最左边开始,一个一个扫。（动画第 4 步）

最优解：一步一步想明白

1. 3记牢「左括号压 0 开新层、右括号结算栈顶(空层得 1、否则翻倍)、把分数加回外层」,下面每一帧都在套它。
2. 4开始之前,先在栈底放一个 0。这个 0 代表「最外面一层」当前的累计分数,所有算出来的分最终都会汇总到它身上。上方一排是要依次处理的 8 个括号,我们从最左边开始,一个一个扫。
3. 5扫到第 1 个字符,是左括号 (。它代表「进入更里面的一层」。我们的做法是往栈里压入一个 0,给这新的一层先记 0 分,等里面的东西算完再结算。
4. 6压进一个 0。现在栈顶这个 0 就是「刚进入的这一层」的累计分数,它暂时是 0,因为里面还没算出任何东西。栈一旦变长,就说明我们钻进了更深的括号里。
5. 7扫到第 2 个字符,是左括号 (。它代表「进入更里面的一层」。我们的做法是往栈里压入一个 0,给这新的一层先记 0 分,等里面的东西算完再结算。
6. 8压进一个 0。现在栈顶这个 0 就是「刚进入的这一层」的累计分数,它暂时是 0,因为里面还没算出任何东西。栈一旦变长,就说明我们钻进了更深的括号里。
7. 9扫到第 3 个字符,是右括号 )。它代表「当前这一层到此封口、可以结算了」。接下来把栈顶那层的分数弹出来,看看这层到底值多少分。
8. 10把栈顶弹出来,这层封口前累计的分数是 v = 0。它是 0,意味着这一层从压进来到现在什么分都没加过,也就是一对紧挨着的空括号 ()。
9. 11v 是 0,说明这就是一对空括号 (),按规则 () 得 1 分。把这 1 分加到新的栈顶,也就是它外面那一层。外层分数从此多了 1。
10. 12扫到第 4 个字符,是左括号 (。它代表「进入更里面的一层」。我们的做法是往栈里压入一个 0,给这新的一层先记 0 分,等里面的东西算完再结算。
11. 13压进一个 0。现在栈顶这个 0 就是「刚进入的这一层」的累计分数,它暂时是 0,因为里面还没算出任何东西。栈一旦变长,就说明我们钻进了更深的括号里。
12. 14扫到第 5 个字符,是左括号 (。它代表「进入更里面的一层」。我们的做法是往栈里压入一个 0,给这新的一层先记 0 分,等里面的东西算完再结算。
13. 15压进一个 0。现在栈顶这个 0 就是「刚进入的这一层」的累计分数,它暂时是 0,因为里面还没算出任何东西。栈一旦变长,就说明我们钻进了更深的括号里。
14. 16扫到第 6 个字符,是右括号 )。它代表「当前这一层到此封口、可以结算了」。接下来把栈顶那层的分数弹出来,看看这层到底值多少分。
15. 17把栈顶弹出来,这层封口前累计的分数是 v = 0。它是 0,意味着这一层从压进来到现在什么分都没加过,也就是一对紧挨着的空括号 ()。
16. 18v 是 0,说明这就是一对空括号 (),按规则 () 得 1 分。把这 1 分加到新的栈顶,也就是它外面那一层。外层分数从此多了 1。
17. 19扫到第 7 个字符,是右括号 )。它代表「当前这一层到此封口、可以结算了」。接下来把栈顶那层的分数弹出来,看看这层到底值多少分。
18. 20把栈顶弹出来,这层封口前累计的分数是 v = 1。它大于 0,意味着这一层里面已经包着别的括号、攒了 1 分。
19. 21v 是 1 不为 0,说明里面包着东西,按规则 (A) 要翻倍:2 乘 1 等于 2。把 2 加到新的栈顶,也就是外面那一层。外层分数从此多了 2。
20. 22扫到第 8 个字符,是右括号 )。它代表「当前这一层到此封口、可以结算了」。接下来把栈顶那层的分数弹出来,看看这层到底值多少分。
21. 23把栈顶弹出来,这层封口前累计的分数是 v = 3。它大于 0,意味着这一层里面已经包着别的括号、攒了 3 分。
22. 24v 是 3 不为 0,说明里面包着东西,按规则 (A) 要翻倍:2 乘 3 等于 6。把 6 加到新的栈顶,也就是外面那一层。外层分数从此多了 6。
23. 258 个括号全部处理完,栈里只剩栈底这一个数 6。它就是最外层汇总到的全部分数,也就是整串的总分。把过程连起来看:最里面两对 () 各得 1,被层层括号包着不断翻倍累加,最终汇成 6。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def scoreOfParentheses(self, s: str) -> int:
        ans = d = 0
        for i, c in enumerate(s):
            if c == '(':
                d += 1
            else:
                d -= 1
                if s[i - 1] == '(':
                    ans += 1 << d
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int scoreOfParentheses(string s) {
        int ans = 0, d = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] == '(') {
                ++d;
            } else {
                --d;
                if (s[i - 1] == '(') {
                    ans += 1 << d;
                }
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int scoreOfParentheses(String s) {
        int ans = 0, d = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (s.charAt(i) == '(') {
                ++d;
            } else {
                --d;
                if (s.charAt(i - 1) == '(') {
                    ans += 1 << d;
                }
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问