LeetCode 856. 括号的分数

2025-09-18 HGNULB 约 6 分钟

文章信息 7 个分类 3 个标签

分类

题目描述

✅ 856. 括号的分数

题意分析

输入是一个保证平衡的括号串，长度不超过 50，要按三条规则算出它的分数：() 得 1 分，AB 得 A 与 B 之和，(A) 得 A 的两倍。

三条规则里没有任何字符值参与运算，分数完全由嵌套结构决定，因此答案与某对括号出现在串的哪个位置无关，只与「谁被谁包住」有关。

把规则一路展开到底会发现，真正凭空产生分数的只有紧挨在一起的一对 ()，其余括号的作用是给内部已有的分数翻倍。

边界上有两点要留意：题目保证串是平衡的，不会出现 )( 这种非法输入；长度 50 意味着最深嵌套 25 层，$2^{25}$ 远在 32 位整数范围内，不必担心溢出。

解法：按深度累加基础 () 贡献

核心思路

最直接的做法是照定义递归：先找出把当前区间切成若干个平衡段的位置，分别求分再相加；若整段外面正好被一对括号裹住，就递归求内部分数再乘 2。

瓶颈在于每层递归都要重新扫一遍当前区间去找切点，同一个字符被反复访问，最坏退化到 $O(n^2)$。

换个角度观察：把 (A) 的翻倍规则一直往里推，一对最内层的 () 如果外面套了 $d$ 层括号，它最终会被乘 $2^d$；而 AB 的相加规则说明各对 () 的贡献互不干扰。于是答案就是 $\sum 2^{d_i}$，其中 $d_i$ 是第 $i$ 对贴合的 () 外面套的层数。

由此得到扫描过程要维持的不变量：处理下标 i 之前，depth 恒等于 i 左边尚未闭合的左括号个数。当 s[i] 是 ) 时先执行 depth--，此刻 depth 正好等于这对括号外面套了几层；若 s[i - 1] 是 (，说明刚闭合的是一对贴合的 ()，把 1 << depth 计入答案即可。

解题步骤

depth 置 0、score 置 0。depth 承载上面的不变量，score 只做单向累加，两个变量含义全程不变，避免中途改写语义。

从左往右逐字符扫描。嵌套深度只依赖左边已经出现过的括号，一次正向扫描就够，不需要回头再看。

遇到 ( 时 depth++。新开一层意味着它右边的内容都被多包了一层。

遇到 ) 时先 depth--。先减是为了让 depth 从「括号内的层数」回退成「括号外的层数」，只有这样 1 << depth 才对应正确的翻倍次数。

减完之后再判断 s[i - 1] 是不是 (。是就说明刚闭合的是一对贴合的 ()，把 1 << depth 加进 score；不是则说明它闭合的是一段更大的结构，那段内部的分数早已在更内层结算完，这里不能重复计。

扫描结束返回 score。

以 (()(())) 走一遍：

i = 0 是 (，depth 变 1；i = 1 是 (，depth 变 2。

i = 2 是 )，先减成 depth = 1，前一位 s[1] 是 (，累加 1 << 1 = 2，此时 score = 2。

i = 3 是 (，depth 变 2；i = 4 是 (，depth 变 3。

i = 5 是 )，先减成 depth = 2，前一位 s[4] 是 (，累加 1 << 2 = 4，此时 score = 6。

i = 6 是 )，先减成 depth = 1，前一位 s[5] 是 )，不累加。

i = 7 是 )，先减成 depth = 0，前一位 s[6] 是 )，不累加。

返回 6。按规则手算是：(()(())) 外层裹住 ()(())，即 $2 \times (1 + 2 \times 1) = 6$，两者一致。

代码实现

class Solution {
    // 扫描时只要知道当前字符属于第几层，遇到 () 时就能立即结算一个贡献。
    public int scoreOfParentheses(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int depth = 0;
        int score = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                depth++;
            } else {
                depth--;
                if (i > 0 && s.charAt(i - 1) == '(') {
                    score += 1 << depth;
                }
            }
        }

        return score;
    }
}

func scoreOfParentheses(s string) int {
    // 扫描时只要知道当前字符属于第几层，遇到 () 时就能立即结算一个贡献。
    if len(s) == 0 {
        return 0
    }

    score := 0
    depth := 0
    for i := 0; i < len(s); i++ {
        if s[i] == '(' {
            depth++
        } else {
            depth--
            if i > 0 && s[i-1] == '(' {
                score += 1 << depth
            }
        }
    }
    return score
}

复杂度分析

时间复杂度：$O(n)$，每个字符只被访问一次，每次做的都是常数级的加减、比较和位移。

空间复杂度：$O(1)$，全程只有 depth 和 score 两个整数，没有开栈也没有开数组。

关键点总结

递归定义不等于必须递归实现。把 (A) 的翻倍规则展开到底得到「每对贴合的 () 贡献 $2^{层数}$」的闭式，$O(n^2)$ 的分治就塌成了一次线性扫描。

计数类问题先找「最小结算单元」。认准贴合的 () 是唯一产分单位之后，其余右括号一律不参与计分，分支逻辑立刻收敛。

「先改状态还是先用状态」是这类扫描题的成败点。既然约定 depth 表示外层层数，就必须在 ) 分支里先减后用，顺序颠倒会让每个贡献整体翻倍。

面试视角：本题有栈解和 $O(1)$ 计数解两条路。答出栈解能过关，但主动指出「栈里存的是各层累计分数，而这些分数其实只由深度决定」并给出常数空间写法，是明确的加分项。

面试视角：写 1 << depth 而不是 Math.pow(2, depth)，既避开了浮点精度和强制转换，也顺带表明你看清了「翻倍」与「左移」的等价关系，面试官通常会顺势追问 1614 这类只求深度的变形。

易错点总结

错误写法：在 ) 分支里先 score += 1 << depth 再 depth--。用 (()) 试：内层 ) 在 i = 2，此时 depth 还是 2，会加 4 而不是 2，答案从 2 变成 4。

错误写法：不判断 s[i - 1] == '('，每个 ) 都累加。用 (()) 试：i = 2 加 2、i = 3 再加 1，返回 3，外层括号被当成了产分单元。

错误写法：把偏移写成 1 << (depth + 1)。用最简单的 () 试：depth 减到 0 后本该加 1，却加了 2，与规则「() 得 1 分」直接冲突。

错误写法：不加 i > 0 保护就访问 s[i - 1]。合法输入首字符必是 (，但面试官一旦放宽约束传入 )( 之类，第一步就下标越界。

错误写法：改用栈解时，弹出内层分数后写 top += 2 * inner 而漏掉 max(2 * inner, 1)。用 () 试：栈里内层分数是 0，乘 2 仍是 0，答案变成 0。

错误写法：把 AB = A + B 误读成并列两段相乘。用 ()() 试：算成 $1 \times 1 = 1$，正确答案是 2。

错误写法：以为「最深那对括号贡献最大，只统计它」。用 ()()() 试：最深处只有 1 分，另外两对被漏掉，答案从 3 变成 1。

错误写法：切分平衡段时只数左括号、不数右括号来判断何时切开。这样切点会落在不平衡的位置上，递归收到非法子串后要么越界要么静默返回错误分数。

相似题目

题目	难度	考察点
20. 有效的括号	简单	只判合法性，栈里存待匹配字符
32. 最长有效括号	困难	栈里存下标，答案是区间长度
678. 有效的括号字符串	中等	通配符让单一深度退化成上下界区间
1190. 反转每对括号间的子串	中等	同样按层驱动，每层要做的是字符反转
1614. 括号的最大嵌套深度	简单	对深度取最大值而非按层累加权重