資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學C++ 中括號的分值
假設我們有一個平衡的括號字串 S，我們需要根據以下規則計算字串的分值 -
- () 的分值為 1
- AB 的分值為 A + B，其中 A 和 B 是兩個平衡的括號字串。
- (A) 的分值為 2 * A，其中 A 是一個平衡的括號字串。
因此，如果輸入類似於“(()(()))”，那麼輸出將為 6。
為了解決此問題，我們將按照以下步驟操作 -
- ans := 0，定義一個棧 st
- 對於 i 的範圍從 0 到字串 S 的長度
- 如果 S[i] 是左括號，那麼將 -1 插入棧
- 否則
- 如果棧頂為 -1，那麼從棧中刪除並插入 1
- 否則
- x := 0
- 當棧頂不為 -1 時
- 將 x 增加 st 的值，從 st 中刪除
- x := x * 2
- 從 st 中刪除，並插入 x
- 當棧不為空時
- 將 ans 增加 st 中的值，並刪除棧頂元素
- 返回 ans。
讓我們看一下以下實現來加深理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int scoreOfParentheses(string S) {
int ans = 0;
stack <int> st;
for(int i = 0; i < S.size(); i+=1){
if(S[i] == '('){
st.push(-1);
}else{
if(st.top() == -1){
st.pop();
st.push(1);
}else{
int x = 0;
while(st.top() != -1){
x += st.top();
st.pop();
}
x *= 2;
st.pop();
st.push(x);
}
}
}
while(!st.empty()){
ans += st.top();
st.pop();
}
return ans;
}
};
main(){
Solution ob;
cout << (ob.scoreOfParentheses("(()(()))"));
}輸入
"(()(()))"
輸出
6
更新於： 05-05-2020
295 次瀏覽
廣告