算法题 括号的分数

856. 括号的分数

问题描述

给定一个平衡括号字符串s，按下述规则计算该字符串的分数：

• ()得 1 分
• AB得A + B分，其中A和B是平衡括号字符串
• (A)得2 * A分，其中A是平衡括号字符串

返回字符串s的分数。

示例：

输入:"()"输出:1

输入:"(())"输出:2解释:(())=2*()=2*1=2

输入:"()()"输出:2解释:()()=()+()=1+1=2

输入:"(()(()))"输出:6解释:(()(()))=2*(()+(()))=2*(1+2)=6

算法思路

深度优先搜索 + 栈模拟：

1. 核心：

   • 平衡括号字符串可以递归分解
   • 每个()贡献的分数 = 2^(深度)

2. 方法一：递归

   • 遍历字符串，找到每个独立的平衡子串
   • 对每个子串递归计算分数
   • 合并结果：独立子串相加，嵌套子串乘以2

3. 方法二：深度计算

   • 遍历字符串，维护当前深度
   • 遇到()时，贡献分数为 2^depth
   • 每个()的实际贡献等于它所在深度的2的幂次

4. 方法三：栈模拟

   • 使用栈存储当前各层的分数
   • 遇到(时压入0
   • 遇到)时，计算当前层分数并更新上一层

代码实现

方法一：递归

classSolution{/** * 递归计算括号字符串的分数 * 将字符串分解为独立的平衡子串，分别计算后相加 * * @param s 平衡括号字符串 * @return 字符串的分数 */publicintscoreOfParentheses(Strings){returnscore(s,0,s.length()-1);}/** * 计算子串s[start...end]的分数 */privateintscore(Strings,intstart,intend){// 基础情况：最简单的"()"得1分if(end-start==1){return1;}intbalance=0;// 平衡计数器inttotalScore=0;// 找到独立的平衡子串并分别计算for(inti=start;i<=end;i++){if(s.charAt(i)=='('){balance++;}else{balance--;}// 当balance为0时，找到了一个独立的平衡子串if(balance==0){if(i==end){// 整个字符串是一个嵌套结构：(A)// 分数 = 2 * score(A)totalScore=2*score(s,start+1,end-1);}else{// 当前子串是独立的：AB 形式// 分数 = score(A) + score(B)totalScore+=score(s,start,i);// 递归处理剩余部分totalScore+=score(s,i+1,end);break;// 已经分解完成}}}returntotalScore;}}

方法二：深度计算

classSolution{/** * 深度计算 * 每个"()"的贡献是2^depth，其中depth是其嵌套深度 * * @param s 平衡括号字符串 * @return 字符串的分数 */publicintscoreOfParentheses(Strings){intdepth=0;// 当前嵌套深度inttotalScore=0;// 总分数for(inti=0;i<s.length();i++){if(s.charAt(i)=='('){depth++;}else{depth--;// 如果前一个字符是'('，说明遇到了"()"if(s.charAt(i-1)=='('){// 贡献分数为2^depthtotalScore+=(1<<depth);// 位运算：1 << depth = 2^depth}}}returntotalScore;}}

方法三：栈模拟

importjava.util.*;classSolution{/** * 使用栈模拟计算括号分数 * 栈中存储当前各层的累计分数 * * @param s 平衡括号字符串 * @return 字符串的分数 */publicintscoreOfParentheses(Strings){Stack<Integer>stack=newStack<>();stack.push(0);// 初始化栈底为0for(charc:s.toCharArray()){if(c=='('){// 遇到左括号，压入0表示新层开始stack.push(0);}else{// 遇到右括号，计算当前层的分数intcurrentScore=stack.pop();// 当前层的分数intparentScore=stack.pop();// 父层的分数// 如果currentScore为0，说明是"()"，得1分// 否则是嵌套结构，得2 * currentScore分intlayerScore=currentScore==0?1:2*currentScore;// 将当前层分数加到父层stack.push(parentScore+layerScore);}}// 栈中只剩最终结果returnstack.pop();}}

算法分析

• 方法一时间复杂度：O(n²)
  • 最坏情况下每次递归都要遍历整个子串
  • 例如：(((((...)))))这样的完全嵌套结构
• 方法二时间复杂度：O(n)
  • 只需要一次遍历
  • 位运算操作是O(1)
• 方法三时间复杂度：O(n)
  • 每个字符最多入栈出栈一次
• 空间复杂度：
  • 方法一：O(n)（递归栈）
  • 方法二：O(1)
  • 方法三：O(n)（显式栈）

算法过程

1：s = "(()(()))"

方法二：

s: ( ( ) ( ( ) ) ) i: 0 1 2 3 4 5 6 7

1. i=0：(，depth=1
2. i=1：(，depth=2
3. i=2：)，depth=1，前一个字符是(，所以totalScore += 2^1 = 2
4. i=3：(，depth=2
5. i=4：(，depth=3
6. i=5：)，depth=2，前一个字符是(，所以totalScore += 2^2 = 4
7. i=6：)，depth=1，前一个字符是)，不加分
8. i=7：)，depth=0，前一个字符是)，不加分

结果：totalScore = 2 + 4 = 6

方法三：

初始: stack = [0] ( : stack = [0, 0] ( : stack = [0, 0, 0] ) : pop 0, pop 0 → 0==0 → push 0+1 = [0, 1] ( : stack = [0, 1, 0] ( : stack = [0, 1, 0, 0] ) : pop 0, pop 0 → 0==0 → push 0+1 = [0, 1, 1] ) : pop 1, pop 1 → 1!=0 → push 1+2*1 = [0, 3] ) : pop 3, pop 0 → 3!=0 → push 0+2*3 = [6] 结果: 6

测试用例

publicclassMain{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：基础情况System.out.println("Test 1: "+solution.scoreOfParentheses("()"));// 1// 测试用例2：嵌套System.out.println("Test 2: "+solution.scoreOfParentheses("(())"));// 2// 测试用例3：并列System.out.println("Test 3: "+solution.scoreOfParentheses("()()"));// 2// 测试用例4：复杂嵌套System.out.println("Test 4: "+solution.scoreOfParentheses("(()(()))"));// 6// 测试用例5：深度嵌套System.out.println("Test 5: "+solution.scoreOfParentheses("((()))"));// 4// ((())) = 2 * (2 * ()) = 2 * 2 * 1 = 4// 测试用例6：混合结构System.out.println("Test 6: "+solution.scoreOfParentheses("()(())"));// 3// ()(()) = 1 + 2 = 3// 测试用例7：更复杂System.out.println("Test 7: "+solution.scoreOfParentheses("(()()())"));// 6// (()()()) = 2 * (1 + 1 + 1) = 6// 测试用例8：最大深度System.out.println("Test 8: "+solution.scoreOfParentheses("((((()))))"));// 16// 2^4 = 16// 测试用例9：单层多并列System.out.println("Test 9: "+solution.scoreOfParentheses("()()()()"));// 4// 测试用例10：嵌套和并列混合System.out.println("Test 10: "+solution.scoreOfParentheses("((())(()))"));// 8// ((())(())) = 2 * (2 + 2) = 8}}

关键点

1. 深度贡献：

   • 每个()的实际贡献是2^depth
   • 每嵌套一层，外层的括号会将内层分数乘以2

2. 识别()：

   • 在遍历时，如果当前字符是)且前一个字符是(，说明遇到了基础的()

3. 位运算：

   • 1 << depth比Math.pow(2, depth)更高效
   • 位运算在底层执行更快

常见问题

1. 为什么每个()的贡献是 2^depth？
   每层外层括号都会将内层分数乘以2。例如，深度为2的()会被外层两层括号分别乘以2，总共乘以4=2²。

2. 方法二如何处理()()这种并列情况？
   每个()都会被独立识别和计算。第一个()在深度0时贡献1，第二个()也在深度0时贡献1，总共2。

3. 栈中的初始0？
   初始0作为根节点的分数，确保所有计算都有父层可以累加。最终栈中只剩这个累加后的总分数。