每日一题做题记录，参考官方和三叶的题解

题目要求

思路一：栈

• 看到括号立即推栈~
• 可以发现其实是一堆分数的累加，所以栈里面直接存分数：
  • 首先，每个(压入一个000作为初始分数；
  • 当遇到)即可结束一个括号，也就是最近的(；
    • 取出当前栈顶分数curcurcur；
      • 若为000，说明中间没有东西直接记111分；
      • 若为其他，说明中间有东西需要记2×cur2\times cur2×cur；
      • 新分数可以表示为max(2∗cur,1)max(2*cur, 1)max(2∗cur,1)；
    • 直接将新分数加在新栈顶上即可；
      • 越在底部的元素越是包在外面，里面都是累加计算；
  • 最终输出栈内的唯一元素即可。

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)O(n)
• 空间复杂度：O(n)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)O(n)
• 空间复杂度：O(n)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)O(n)
• 空间复杂度：O(n)O(n)O(n)

思路二：模拟计算

• 略去栈，直接记录分数；
• 根据题意发现其实分数来源就只是()，所以记录其所在深度depthdepthdepth考虑乘几个222，然后累加到答案上即可。
• 因为第一个字符一定是(，所以默认深度为111，遍历字符串时直接掠过s[0]s[0]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(n)O(n)
• 空间复杂度：O(1)O(1)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(n)O(n)
• 空间复杂度：O(1)O(1)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(n)O(n)
• 空间复杂度：O(1)O(1)O(1)

总结

自己想到的方法有点类似两种结合，用栈记录分数来源的括号并记录最后计算分数，没有意识到可以直接累加计算，顺序不影响结果。

【强行给自己放了一周假，还想搞十月打卡来着……还是认真摸鱼吧】

欢迎指正与讨论！