(栈)leetcode856 Score of Parentheses
2024-10-15 15:39:24
Given a balanced parentheses string S
, compute the score of the string based on the following rule:
()
has score 1AB
has scoreA + B
, where A and B are balanced parentheses strings.(A)
has score2 * A
, where A is a balanced parentheses string.
Example 1:
Input: "()"
Output: 1
Example 2:
Input: "(())"
Output: 2
Example 3:
Input: "()()"
Output: 2
Example 4:
Input: "(()(()))"
Output: 6
Note:
S
is a balanced parentheses string, containing only(
and)
.2 <= S.length <= 50
这个可以利用栈,在官方题解上:
Intuition and Algorithm
Every position in the string has a depth - some number of matching parentheses surrounding it. For example, the dot in (()(.()))
has depth 2, because of these parentheses: (__(.__))
Our goal is to maintain the score at the current depth we are on. When we see an opening bracket, we increase our depth, and our score at the new depth is 0. When we see a closing bracket, we add twice the score of the previous deeper part - except when counting ()
, which has a score of 1.
For example, when counting (()(()))
, our stack will look like this:
[0, 0]
after parsing(
[0, 0, 0]
after(
[0, 1]
after)
[0, 1, 0]
after(
[0, 1, 0, 0]
after(
[0, 1, 1]
after)
[0, 3]
after)
[6]
after)
C++代码:
class Solution {
public:
int scoreOfParentheses(string S) {
stack<int> s;
s.push();
for(char c:S){
if(c == '(')
s.push();
else{
int v = s.top();
s.pop();
int w = s.top();
s.pop();
s.push(w + max(*v,));
}
}
return s.top();
}
};
最新文章
- Clr Via C#读书笔记---CLR寄宿和应用程序域
- gulp完全开发指南 =>; 快来换掉你的Grunt吧
- sublime text 3 的在文件夹中查找的快捷键没有反应 的bug冲突
- php数组序列化serialize与unserialize
- PHP中ob系列函数整理
- KVM虚拟机网络基础及优化说明
- Android 常见的广播 action常量
- HDFS的体系结构和操作
- 学习笔记 - 深究Bitmap压缩避免OOM的核心inSampleSize的最佳取值
- 转:Backbone与Angular的比较
- TCP Linger的坑
- java获取当前上一周、上一月、上一年的时间
- PG数据库中用户权限
- python网络编程初级
- 设置linux新用户默认当前目录及使用的shell
- json-lib.jar开发包及依赖包的下载地址(转)
- Project configuration is not up-to-date with pom.xml
- zabbix3.2的server和zabbix-agent2.2怎么监控MySQL的办法
- BZOJ4870 [Shoi2017]组合数问题 【组合数 + 矩乘】
- 【Matlab】运动目标检测之“帧差法”