Java实现括号分数问题，如何用长尾词表达？

本文共计847个文字，预计阅读时间需要4分钟。

目录- 题目要求- 思路一：栈 + Java + C++ + Rust- 思路二：模拟计算 + Java + C++ + Rust- 总结- 题目要求- 思路一：栈- 思路二：模拟计算

目录

• 题目要求
• 思路一：栈
• Java
• C++
• Rust
• 思路二：模拟计算
• Java
• C++
• Rust
• 总结

题目要求

思路一：栈

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]。

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)

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)

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++ 括号的分数的资料请关注自由互联其它相关文章！