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

相关文章

来自专栏数据结构与算法

洛谷P3375 【模板】KMP字符串匹配

题目描述 如题,给出两个字符串s1和s2,其中s2为s1的子串,求出s2在s1中所有出现的位置。 为了减少骗分的情况,接下来还要输出子串的前缀数组next。 (...

3247
来自专栏算法channel

归并排序算法的过程图解

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

37811
来自专栏大闲人柴毛毛

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

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

3009
来自专栏猿人谷

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

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

2186
来自专栏chenjx85的技术专栏

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

2886
来自专栏青青天空树

说反话(c++实现)

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

692
来自专栏xiaoxi666的专栏

今日头条笔试题:“最小数字*区间和”的最大值【单调栈】

  利用单调栈,从前向后和从后向前分别遍历一遍数组,得到每个元素的左边界和右边界(边界的定义即为碰到比该元素更小的即停止),最后用每个元素乘以每个元素对应的区间...

1701
来自专栏从流域到海域

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

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

2017
来自专栏Spark学习技巧

海量数据处理之BloomFilter

一提到元素查找,我们会很自然的想到HashMap。通过将哈希函数作用于key上,我们得到了哈希值,基于哈希值我们可以去表里的相应位置获取对应的数据。除了存在哈希...

1163
来自专栏Java开发者杂谈

算法之数组和问题

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

3768

扫码关注云+社区