[LeetCode Weekly Contest 90]856.括号的分数

题目描述

856.括号的分数

给定一个平衡括号字符串 S,按下述规则计算该字符串的分数:

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

示例 1:

输入: "()"
输出: 1

示例 2:

输入: "(())"
输出: 2

示例 3:

输入: "()()"
输出: 2

示例 4:

输入: "(()(()))"
输出: 6

提示:

  1. S 是平衡括号字符串,且只含有 ( 和 ) 。
  2. 2 <= S.length <= 50

分析

这个题目看起来有点像括号匹配的题目,但事实上是一个表达式求值。

不包含任何内容的括号()得一分,事实上我们可以将()替换为1,这样题目就变成了1得一分,并列的部分得分相加,括号内的部分得分乘以2,四个示例就转换为了:

示例 1:

输入: "1"
输出: 1

示例 2:

输入: "(1)"
输出: 2

示例 3:

输入: "11"
输出: 2

示例 4:

输入: "(1(1))"
输出: 6

我们可以像处理表达式求值一样,利用栈来存储:

  1. 遇到1压栈,
  2. 遇到左括号压栈,
  3. 遇到右括号,弹出栈顶元素并累加,直到弹出左括号,将累加的和乘以2压栈

最后的结果就是所有栈内元素的和,例如处理‘1(1(11))’,也就是'()(()(()()))':

  1. 遇到1,压栈,[1]
  2. 遇到(,压栈,[1, (]
  3. 遇到1,压栈,[1, (, 1]
  4. 遇到(,压栈,[1, (, 1, (]
  5. 遇到两个1, 先后压栈, [1, (, 1, (, 1, 1]
  6. 遇到),弹出栈顶元素,在弹出(之前遇到两个1,求和得2,再乘以2压栈,[1, (, 1, 4,]
  7. 遇到),弹出栈顶元素,在弹出(之前遇到1和4,求和得5,再乘以2压栈,[1, 10]
  8. 扫描结束,结果就是栈内所有元素的和,为11

代码实现

class Solution:
    def scoreOfParentheses(self, S):
        """
        :type S: str
        :rtype: int
        """
        S = S.replace('()', '1')
        stack = []
        for ch in S:
            if ch == '(':
                stack.append(ch)
            elif ch == '1':
                stack.append(1)
            else:
                num = 0
                while stack[-1] != '(':
                    num += stack.pop()
                stack.pop()
                stack.append(num * 2)
        return sum(stack)        

其实不讲()替换为1也可以,这样的话遇到)的时候如果栈顶就是(,弹出(并压入1就可以了。这在使用不能方便的进行字符串替换的语言中(C语言)是优先选择。

class Solution:
    def scoreOfParentheses(self, S):
        """
        :type S: str
        :rtype: int
        """
        stack = []
        for ch in S:
            if ch == '(':
                stack.append(ch)
            else:
                num = 0
                if stack[-1] == '(':
                    stack.pop()
                    stack.append(1)
                else:
                    while stack[-1] != '(':
                        num += stack.pop()
                    stack.pop()
                    stack.append(num * 2)
        return sum(stack)

结语

今天的建议是善于把握问题的实质,不要被表象迷惑。

最后祝大家享受生活,享受代码。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏linux驱动个人学习

高通Audio中ASOC的machine驱动

ASoC被分为Machine、Platform和Codec三大部分,其中的Machine驱动负责Platform和Codec之间的耦合以及部分和设备或板子特定的...

9774
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1796
来自专栏码匠的流水账

java9系列(五)Stack-Walking API

java9新增这个类的目的是提供一个标准API用于访问当前线程栈,之前只有Throwable::getStackTrace、Thread::getStackTr...

421
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

702
来自专栏码匠的流水账

聊聊HystrixThreadPool

hystrix-core-1.5.12-sources.jar!/com/netflix/hystrix/HystrixThreadPool.java

781
来自专栏Jerry的SAP技术分享

How to update BOL entity property value via ABAP code

Suppose I have one product with ID I042416 which could be found in CRM WebClient...

510
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2312
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112
来自专栏Golang语言社区

Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1142
来自专栏WOLFRAM

向日葵中的数学之美

1833

扫码关注云+社区