Java&C++題解與拓展——leetcode856.括號的分數【麼的新知識】
theme: hydrogen highlight: atom-one-dark
| 每日一題做題記錄，參考官方和三葉的題解 |
題目要求
思路一：棧
- 看到括號立即推棧~
- 可以發現其實是一堆分數的累加，所以棧裡面直接存分數：
- 首先，每個
(壓入一個$0$作為初始分數； - 當遇到
)即可結束一個括號，也就是最近的(；- 取出當前棧頂分數$cur$；
- 若為$0$，說明中間沒有東西直接記$1$分；
- 若為其他，說明中間有東西需要記$2\times cur$；
- 新分數可以表示為$max(2*cur, 1)$；
- 直接將新分數加在新棧頂上即可；
- 越在底部的元素越是包在外面，裡面都是累加計算；
- 取出當前棧頂分數$cur$；
- 最終輸出棧內的唯一元素即可。
- 首先，每個
Java
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 { // 結束一個括號
int cur = sta.pollLast(); // 取出當前分數
sta.addLast(sta.pollLast() + Math.max(cur * 2, 1)); // 更新上級括號分數
}
}
return sta.peekLast();
}
}
- 時間複雜度：$O(n)$
- 空間複雜度：$O(n)$
C++
cpp
class Solution {
public:
int scoreOfParentheses(string s) {
stack<int> sta;
sta.push(0); // 初始0用於記錄結果分數
for (auto c : s) {
if (c == '(')
sta.push(0);
else { // 結束一個括號
int cur = sta.top(); // 取出當前分數
sta.pop();
sta.top() += max(cur * 2, 1); // 更新上級括號分數
}
}
return sta.top();
}
};
- 時間複雜度：$O(n)$
- 空間複雜度：$O(n)$
Rust
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用於記錄結果分數
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]
}
}
- 時間複雜度：$O(n)$
- 空間複雜度：$O(n)$
思路二：模擬計算
- 略去棧，直接記錄分數；
- 根據題意發現其實分數來源就只是
()，所以記錄其所在深度$depth$考慮乘幾個$2$，然後累加到答案上即可。 - 因為第一個字元一定是
(，所以預設深度為$1$，遍歷字串時直接掠過$s[0]$。
Java
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) == ')') // 分數來源
res += 1 << depth;
}
return res;
}
}
- 時間複雜度：$O(n)$
- 空間複雜度：$O(1)$
C++
cpp
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] == ')') // 分數來源
res += 1 << depth;
}
return res;
}
};
- 時間複雜度：$O(n)$
- 空間複雜度：$O(1)$
Rust
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'(' { // 分數來源
res += 1 << depth;
}
}
}
res
}
}
- 時間複雜度：$O(n)$
- 空間複雜度：$O(1)$
總結
自己想到的方法有點類似兩種結合，用棧記錄分數來源的括號並記錄最後計算分數，沒有意識到可以直接累加計算，順序不影響結果。
【強行給自己放了一週假，還想搞十月打卡來著……還是認真摸魚吧】
| 歡迎指正與討論！ |