LeetCode-Go 题解实战856. Score of Parentheses 括号分数的栈解法与深入剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇围绕 LeetCode 第 856 题「括号的分数Score of Parentheses」展开以 LeetCode-Go 仓库中 856. Score of Parentheses 解题源码 与测试用例为核心依据系统讲解题目规则、三种等价解法栈模拟、按层计分、递归解析的推导过程并逐行剖析仓库源码中以 -1 标记左括号的栈实现细节与复杂度分析。读完本篇你将掌握一类括号字符串评分问题的通用分析框架能够独立完成代码复现与正确性验证。题目理解三条递归定义规则原题见 leetcode/0856.Score-of-Parentheses/README.md给定一个平衡括号字符串Sbalanced parentheses string要求按下述规则计算其分数()的分数为1AB的分数为A B其中 A、B 均为平衡括号字符串即并列相加(A)的分数为2 * A其中 A 为平衡括号字符串即包裹翻倍。三条规则是递归定义的因此任意平衡括号串都可以唯一地拆解为原子()的组合分数本质上取决于每个原子()被多少层括号包裹。官方示例回顾输入输出拆解过程()1原子括号直接 1 分(())2(())( () )2 * 1()()2()()1 1(()(()))6( () (()) )2 * (1 2) 6题目约束S 是仅含(与)的平衡括号字符串且2 S.length 50。长度上限只有 50意味着递归、栈、DFS 等任何 O(n) 或 O(n²) 级别的解法都可以轻松通过解题重点在于逻辑清晰与写法优雅。解法一栈模拟仓库采用的核心思路解题源码 采用的正是栈方案遇到(压入标记遇到)弹出并结算。与常规做法不同仓库实现用整型栈配合哨兵值-1来充当(的占位标记避免了额外定义结构体。package leetcode func scoreOfParentheses(S string) int { res, stack, top, temp : 0, []int{}, -1, 0 for _, s : range S { if s ( { stack append(stack, -1) top } else { temp 0 for stack[top] ! -1 { temp stack[top] stack stack[:len(stack)-1] top-- } stack stack[:len(stack)-1] top-- if temp 0 { stack append(stack, 1) top } else { stack append(stack, temp*2) top } } } for len(stack) ! 0 { res stack[top] stack stack[:len(stack)-1] top-- } return res }逐行推演初始化res记录最终总分stack是整数栈top初始为-1表示空栈temp在每次右括号结算时临时累加。遇到(压入哨兵-1top表示这里有一层新的包裹其内部的分数尚未产生。遇到)进入结算流程——temp清零从栈顶连续弹出所有非-1的数字并累加到temp这些数字是当前这一层括号内部并列子串的分数对应规则AB → A B弹出顶部的-1哨兵代表与当前)配对的(关键分支若temp 0说明括号内为空即原子()按规则记1分入栈否则说明内部是若干已完成计分的子串按规则(A) → 2 * A将temp * 2入栈。收尾整个字符串扫描完毕后栈中剩余的数字是顶层并列的若干组分数全部累加进res返回。复杂度分析时间复杂度 O(n)每个字符入栈/出栈恰好一次均摊 O(1)总体 O(n)n 为字符串长度空间复杂度 O(n)最坏情况下如(((((((((栈深度与 n 成正比因此为 O(n)。为什么可以用 -1 充当括号标记栈中只存在两类元素数字已结算的分数与-1 哨兵未闭合的左括号。由于题目保证输入是平衡括号串任意时刻-1的数量恰好等于尚未配对的(数量。以-1作为分隔层的妙处在于遇到)时只需一路弹出数字求和直到碰到-1即代表这一层的边界天然实现了把内层分数汇总后再整体翻倍的递归语义。以示例(()(()))走一遍期望输出 6已扫描栈内容左→右为栈底→栈顶说明([-1]压入左括号标记([-1, -1]压入第二层标记)[-1, 1]temp0原子记 1 分([-1, 1, -1]压入新层标记([-1, 1, -1, -1]压入内层标记)[-1, 1, -1, 1]原子记 1 分)[-1, 1, 2]弹出 1temp1≠0翻倍为 2)[6]弹出 1、2 求和得 3翻倍为 6收尾累加res 6 ✔解法二按层计分O(n) 且无需显式栈从原子()的分数由包裹层数决定这一视角出发可以推导出更精简的按层计数法这也是 Stack Overflow 上被广泛讨论的标准做法可当作理解题意的辅助参考维护变量bal记录当前深度未闭合的(数量从左到右扫描每当遇到子串()即当前字符是)且前一个字符是(时说明这里产生了一个原子括号其贡献的分数为1 bal即2^bal等价于2 * 2 * ... * 2共 bal 层包裹最终把每个原子括号的贡献累加即得总分。以(()(()))验证两个原子()分别出现在深度 2 与深度 3 处贡献2² 2³ 4 8注意这并不等于 6——原因在于按层计分法要求原子括号只被其左侧尚未闭合的括号包裹而第二个原子()前面已有((两层包裹应为2² 4。重新数字符串(()(()))中第一个()位于第 2 层第二个()位于第 3 层但它是( () ( () ) )中最内层实际被 3 层包裹贡献2³ 8与第一个的4相加得 12这依然不等于 6。这里需要纠正常见误区包裹层数指的是该原子左侧所有未闭合(的数量而不是距离字符串开头的总深度。正确推演(()(()))的两个原子分别位于第 2 层和第 3 层若直接按2^depth累加会得到4 8 12这显然是错的。正确答案 6 的正确拆解是内层(())得 2 分外层整体为( 1 2 ) 3再翻倍得 6。由此可见按层计分法的正确实现应为遇到()时用1 (bal-1)之类按当前包裹深度计数且只在原子处计分——更稳妥的写法是扫描时维护bal当遇到)且前一字符为(时累加1 (bal - 1)随后bal--遇到(时bal。按此修正(()(()))第一个原子在第 2 层计2^(2-1)2第二个原子在第 3 层计2^(3-1)4合计 6与题目示例一致。该方法与栈解法本质等价但省去了显式栈空间可降至 O(1)。解法三递归解析与题意最贴近的直译由于题目规则本身就是递归的直接按定义翻译成递归同样可行适合作为讲解辅助思路func scoreOfParentheses(S string) int { // 伪代码思路findScore(l, r) 返回 S[l:r] 的分数 // 1. 若 S[l:r] 形如 ()返回 1 // 2. 否则按括号匹配拆出最外层包裹内部整体翻倍2 * findScore(l1, r-1) // 若内部可拆为多个并列子串则分别求分后相加。 }递归实现需要先对字符串做括号配对预处理记录每个(对应的)位置最坏情况下时间复杂度为 O(n²)每次切片后需线性寻找配对但由于题目 n ≤ 50仍然完全可接受。三种解法中栈模拟兼具 O(n) 时间与直观的即时结算语义是实战与面试中最推荐的主方案。测试验证以仓库测试用例复现正确性仓库为本题配备了完整的表驱动测试位于 856. Score of Parentheses_test.go覆盖了官方四个示例之外还额外加入了两个边界用例输入期望输出覆盖点()1最小原子括号(())2单层包裹翻倍()()2并列相加(()(()))6嵌套 并列混合官方最复杂用例()(())3并列中混入包裹1 2((()()))8深层嵌套( ( ( ) ( ) ) ) 2 * (2 2) 8测试通过fmt.Printf逐条打印输入与输出见Test_Problem856方便肉眼核对。若需在本地运行可在仓库根目录执行# 仅运行本题测试需先进入对应目录或使用包路径 go test -v ./leetcode/0856.Score-of-Parentheses/ # 全仓库测试并生成覆盖率参考仓库 gotest.sh 的写法 go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...仓库根目录的 gotest.sh 展示了统一生成合法覆盖率文件的方式使用 Go 1.10 对多个包一次性-coverprofile避免旧式 cat 追加导致 Codecov 解析失败的问题这也是本项目100% test coverage质量要求的具体落点详见仓库根目录 README.md 中关于解题质量的说明。举一反三仓库中的同族括号题目理解了哨兵栈模式后可以顺带对比仓库中其余括号类题目它们在数据结构与扫描策略上高度相通0020.Valid-Parentheses经典括号配对校验用栈存左括号字符0032.Longest-Valid-Parentheses最长有效括号子串需要记录下标而非分数0224.Basic-Calculator带括号的四则运算求值同样以栈处理括号优先级0394.Decode-Stringk[encoded_string]解码是括号包裹 内部展开思想的字符串版本。它们的共同抽象是用栈保存尚未闭合的上下文遇到闭符号时弹出上下文并结算。掌握 856 题的哨兵值技巧后再遇到这类题目可以快速套用同一分析路径。小结LeetCode 856 题的核心是三条递归规则与包裹翻倍、并列相加的语义。仓库提供的 Go 实现 用-1哨兵栈在 O(n) 时间内完成全部结算配合 测试用例 中的六个用例可以完整覆盖嵌套、并列、深层包裹三类场景。无论面试中要求给出栈解法、按层计数还是递归实现只要抓住原子()的分数等于2^包裹层数并列组相加这一本质即可举一反三、稳扎稳打。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
