[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 删除。

发表于

我来说两句

4 条评论
登录 后参与评论

相关文章

来自专栏开发技术

排序之希尔排序(shell sort)

本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中都...

843
来自专栏mathor

动态规划(二)

984
来自专栏苦逼的码农

从零打卡leetcode之day 4--无重复最长字符串

说明:有点抱歉,昨晚发的记得有写题目描述,但不知为啥,题目描述丢失了,可能是自己突然不小心删除了。

833
来自专栏aCloudDeveloper

算法导论第九章中位数和顺序统计量(选择问题)

  本章如果要归结成一个问题的话,可以归结为选择问题,比如要从一堆数中选择最大的数,或最小的数,或第几小/大的数等, 这样的问题看似很简单,似乎没有什么可研究的...

2507
来自专栏灯塔大数据

每周学点大数据 | No.7大数据规模的算法分析

No.7期 大数据规模的算法分析 Mr. 王:这样的时间界限记为O(1),我们称之为常数时间算法,这样的算法一般来说是最快的,因为它与输入规模完全无关,不论输...

1874
来自专栏java一日一条

我是如何击败Java自带排序算法的

Java 8 对自带的排序算法进行了很好的优化。对于整形和其他的基本类型, Arrays.sort() 综合利用了双枢轴快速排序、归并排序和启发式插入排序。这个...

491
来自专栏深度学习与计算机视觉

Python Numpy简介

原文地址:What is Numpy? Numpy是应用Python进行科学计算时的基础模块。它是一个提供多维数组对象的Python库,除此之外,还包含了多种衍...

19010
来自专栏我和未来有约会

[Silverlight动画]转向行为 - 2D向量

转向行为已经被各种语言实现过多次了,其最底层是用向量来描述的(也是最常见的实现方式)。 概括的看,一个向量由两部分组成:一个方向和一个大小。比如,一个运动中对象...

1786
来自专栏java一日一条

最快最简单的排序算法:桶排序

在我们生活的这个世界中到处都是被排序过的。站队的时候会按照身高排序,考试的名次需要按照分数排序,网上购物的时候会按照价格排序,电子邮箱中的邮件按照时间排序……总...

451
来自专栏用户2442861的专栏

白话经典算法系列之六 快速排序 快速搞定

原文   http://blog.csdn.net/morewindows/article/details/6684558

912

扫码关注云+社区