Java&C++題解與拓展——leetcode856.括號的分數【麼的新知識】

語言: CN / TW / HK

theme: hydrogen highlight: atom-one-dark


每日一題做題記錄,參考官方和三葉的題解

題目要求

image.png

思路一:棧

  • 看到括號立即推棧~
  • 可以發現其實是一堆分數的累加,所以棧裡面直接存分數:
    • 首先,每個(壓入一個$0$作為初始分數;
    • 當遇到)即可結束一個括號,也就是最近的(
      • 取出當前棧頂分數$cur$;
        • 若為$0$,說明中間沒有東西直接記$1$分;
        • 若為其他,說明中間有東西需要記$2\times cur$;
        • 新分數可以表示為$max(2*cur, 1)$;
      • 直接將新分數加在新棧頂上即可;
        • 越在底部的元素越是包在外面,裡面都是累加計算;
    • 最終輸出棧內的唯一元素即可。

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)$

總結

自己想到的方法有點類似兩種結合,用棧記錄分數來源的括號並記錄最後計算分數,沒有意識到可以直接累加計算,順序不影響結果。

【強行給自己放了一週假,還想搞十月打卡來著……還是認真摸魚吧】


歡迎指正與討論!