[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 条评论
登录 后参与评论

相关文章

来自专栏个人分享

替换空格

请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

971
来自专栏青青天空树

说反话(c++实现)

输入:测试输入包含一个测试用例,在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成,其中单词是由英文字母(大小写有区分)组成的字符串,单词之间...

832
来自专栏猿人谷

C++ STL算法系列1---count函数

一.count函数 algorithm头文件定义了一个count的函数,其功能类似于find。这个函数使用一对迭代器和一个值做参数,返回这个值出现次数的统计结果...

2476
来自专栏向治洪

常用的排序算法和时间复杂度

1. 数据结构部分 数据结构中常用的操作的效率表 通用数据结构查找  插入   删除 遍历  数组 O(N)O(1)O(N)—有序数组O(logN)O(N)O...

35110
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题31连续子数组的最大和

题目:输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组和的最大值。要求时间复杂度为O(n) 分析:统计连续子数...

3069
来自专栏Java 源码分析

排序算法

选择排序: ​ 选择排序一般来说就是,我们 始终从中右边的序列中找出那些最小的元素,放在左侧,这样我们就能保证左边始终有序。 ​ 但是这个算法的复杂...

4046
来自专栏从流域到海域

《笨办法学Python》 第21课手记

《笨办法学Python》 第21课手记 本节课介绍函数和返回值,出现了函数嵌套,即函数的返回值可以不经赋值而直接做函数参数使用。 原代码如下: def add(...

2397
来自专栏十月梦想

多维数组遍历

多维数组遍历。实际为一维数组的嵌套,吧第一次遍历输出的值当做内部的数组继续遍历,三维数组遍历持续第二次的值当做第三次遍历的数组

901
来自专栏Java开发者杂谈

算法之数组和问题

算法题之数组和求解 数组和问题 ​ 加上给定一个数组和值x。设计一个算法使得如果数组中存在两个元素的和为x,则输出两个元素的值组成的数组(不区分先后),否则输出...

3958
来自专栏chenjx85的技术专栏

leetcode-788-Rotated Digits(使用vector替代if else的逐个判断)

2976

扫码关注云+社区

领取腾讯云代金券