Java C++題解leetcode856括號的分數
題目要求
思路一:棧
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++
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
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考慮乘幾個222,然後累加到答案上即可。 - 因為第一個字符一定是
(
,所以默認深度為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) == ')') // 分數來源 res += 1 << depth; } return res; } }
- 時間復雜度:O(n)
- 空間復雜度: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] == ')') // 分數來源 res += 1 << depth; } return res; } };
- 時間復雜度:O(n)
- 空間復雜度: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'(' { // 分數來源 res += 1 << depth; } } } res } }
- 時間復雜度:O(n)
- 空間復雜度:O(1)
總結
自己想到的方法有點類似兩種結合,用棧記錄分數來源的括號並記錄最後計算分數,沒有意識到可以直接累加計算,順序不影響結果。
以上就是Java C++題解leetcode856括號的分數的詳細內容,更多關於Java C++ 括號的分數的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- None Found