Java C++題解leetcode856括號的分?jǐn)?shù)
更新時間：2022年10月17日 11:37:23 作者：AnjaVon
這篇文章主要為大家介紹了Java C++題解leetcode856括號的分?jǐn)?shù)實現(xiàn)示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
題目要求
思路一：棧
Java
class Solution {
public int scoreOfParentheses(String s) {
Deque<Integer> sta = new ArrayDeque<>();
sta.addLast(0);
for (char c : s.toCharArray()) {
if (c == '(')
sta.addLast(0);
else { // 結(jié)束一個括號
int cur = sta.pollLast(); // 取出當(dāng)前分?jǐn)?shù)
sta.addLast(sta.pollLast() + Math.max(cur * 2, 1)); // 更新上級括號分?jǐn)?shù)
}
}
return sta.peekLast();
}
}
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n)
C++
class Solution {
public:
int scoreOfParentheses(string s) {
stack<int> sta;
sta.push(0); // 初始0用于記錄結(jié)果分?jǐn)?shù)
for (auto c : s) {
if (c == '(')
sta.push(0);
else { // 結(jié)束一個括號
int cur = sta.top(); // 取出當(dāng)前分?jǐn)?shù)
sta.pop();
sta.top() += max(cur * 2, 1); // 更新上級括號分?jǐn)?shù)
}
}
return sta.top();
}
};
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n)
Rust
impl Solution {
pub fn score_of_parentheses(s: String) -> i32 {
let mut sta = Vec::with_capacity((s.len() >> 1) + 1);
sta.push(0); // 初始0用于記錄結(jié)果分?jǐn)?shù)
for c in s.bytes() {
if c == b'(' {
sta.push(0);
}
else {
let cur = sta.pop().unwrap();
*sta.last_mut().unwrap() += 1.max(cur << 1);
}
}
sta[0]
}
}
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n)
思路二：模擬計算
- 略去棧，直接記錄分?jǐn)?shù)；
- 根據(jù)題意發(fā)現(xiàn)其實分?jǐn)?shù)來源就只是
()，所以記錄其所在深度depth考慮乘幾個222，然后累加到答案上即可。 - 因為第一個字符一定是
(，所以默認(rèn)深度為1，遍歷字符串時直接掠過s[0]。
Java
class Solution {
public int scoreOfParentheses(String s) {
int depth = 1, res = 0;
for (int i = 1; i < s.length(); i++) {
depth += (s.charAt(i) == '(' ? 1 : -1);
if (s.charAt(i - 1) == '(' && s.charAt(i) == ')') // 分?jǐn)?shù)來源
res += 1 << depth;
}
return res;
}
}
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
C++
class Solution {
public:
int scoreOfParentheses(string s) {
int depth = 1, res = 0;
for (int i = 1; i < s.size(); i++) {
depth += (s[i] == '(' ? 1 : -1);
if (s[i - 1] == '(' && s[i] == ')') // 分?jǐn)?shù)來源
res += 1 << depth;
}
return res;
}
};
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
Rust
impl Solution {
pub fn score_of_parentheses(s: String) -> i32 {
let (mut depth, mut res) = (1, 0);
let ss = s.as_bytes();
for i in 1..s.len() {
if (ss[i] == b'(') {
depth += 1
}
else {
depth -= 1;
if ss[i - 1] == b'(' { // 分?jǐn)?shù)來源
res += 1 << depth;
}
}
}
res
}
}
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
總結(jié)
自己想到的方法有點類似兩種結(jié)合，用棧記錄分?jǐn)?shù)來源的括號并記錄最后計算分?jǐn)?shù)，沒有意識到可以直接累加計算，順序不影響結(jié)果。
以上就是Java C++題解leetcode856括號的分?jǐn)?shù)的詳細(xì)內(nèi)容，更多關(guān)于Java C++ 括號的分?jǐn)?shù)的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C語言計算大數(shù)階乘的方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-05-05
大家好，本篇文章主要講的是c++下迭代器總結(jié)，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12
C++是面向?qū)ο蟮恼Z言（與C語言主要區(qū)別），所以C++也擁有多態(tài)的特性。下面通過代碼看下C++虛函數(shù)表的問題，感興趣的朋友一起看看吧2021-10-10
大家好，本篇文章主要講的是c語言實現(xiàn)簡易版三子棋（附完整代碼），感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
C++??STL?_?Vector使用及模擬實現(xiàn)
這篇文章主要介紹了C++ STL_Vector使用及模擬實現(xiàn)，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-08-08
在編程的過程中,使用已經(jīng)封裝好的庫函數(shù)是十分方便的,也是十分高效的,這篇文章主要給大家介紹了關(guān)于C語言庫的封裝和使用的相關(guān)資料,需要的朋友可以參考下2021-07-07
C語言基礎(chǔ)知識點解析(extern,static,typedef,const)
本篇文章是對C語言基礎(chǔ)知識點(extern,static,typedef,const)的用法進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過來參考下2013-10-10
C++實現(xiàn)LeetCode(95.獨一無二的二叉搜索樹之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(95.獨一無二的二叉搜索樹之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)通訊錄小功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
這篇文章主要介紹了C++中的自增與自減,自增與自減是C++當(dāng)中兩個使用頻率非常高的運算符，不僅在循環(huán)當(dāng)中用到，在日常的代碼當(dāng)中也經(jīng)常使用,下面來看看文章得具體介紹2021-11-11