快捷導(dǎo)航

Java C++題解leetcode856括號(hào)的分?jǐn)?shù)

更新時(shí)間：2022年10月17日 11:37:23 作者：AnjaVon

這篇文章主要為大家介紹了Java C++題解leetcode856括號(hào)的分?jǐn)?shù)實(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é)束一個(gè)括號(hào)
                int cur = sta.pollLast(); // 取出當(dāng)前分?jǐn)?shù)
                sta.addLast(sta.pollLast() + Math.max(cur * 2, 1)); // 更新上級(jí)括號(hào)分?jǐn)?shù)
            }
        }
        return sta.peekLast();
    }
}

時(shí)間復(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é)束一個(gè)括號(hào)
                int cur = sta.top(); // 取出當(dāng)前分?jǐn)?shù)
                sta.pop();
                sta.top() += max(cur * 2, 1); // 更新上級(jí)括號(hào)分?jǐn)?shù)
            }
        }
        return sta.top();
    }
};

時(shí)間復(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]
    }
}

時(shí)間復(fù)雜度：O(n)
空間復(fù)雜度：O(n)

思路二：模擬計(jì)算

略去棧，直接記錄分?jǐn)?shù)；
根據(jù)題意發(fā)現(xiàn)其實(shí)分?jǐn)?shù)來(lái)源就只是()，所以記錄其所在深度depth考慮乘幾個(gè)222，然后累加到答案上即可。
因?yàn)榈谝粋€(gè)字符一定是(，所以默認(rèn)深度為1，遍歷字符串時(shí)直接掠過(guò)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ù)來(lái)源
                res += 1 << depth;
        }
        return res;
    }
}

時(shí)間復(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ù)來(lái)源
                res += 1 << depth;
        }
        return res;
    }
};

時(shí)間復(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ù)來(lái)源
                    res += 1 << depth;
                }
            }
        }
        res
    }
}