-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathL856.java
More file actions
74 lines (62 loc) · 1.92 KB
/
L856.java
File metadata and controls
74 lines (62 loc) · 1.92 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
package com.liang.leetcode.stack;
import java.util.Stack;
/**
* @ClassName L856
* @description 括号的分数
* @Author LiaNg
* @Date 2019-11-22
*/
public class L856 {
public static void main(String[] args) {
String s = "(()(()))";
L856 l856 = new L856();
System.out.println("l856.scoreOfParentheses(s) = " + l856.scoreOfParentheses(s));
}
/**
* 给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
* () 得 1 分。
* AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
* (A) 得 2 * A 分，其中 A 是平衡括号字符串。
* 来源：力扣（LeetCode）
* 链接：https://leetcode-cn.com/problems/score-of-parentheses
* 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public int scoreOfParentheses(String S) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
char[] sArray = S.toCharArray();
for (char c : sArray) {
if ('(' == c) {
stack.push(0);
} else {
int v = stack.pop();
int w = stack.pop();
stack.push(w + Math.max(v * 2, 1));
}
}
return stack.pop();
}
/**
* LeetCode 耗时最短解答
*/
public int scoreOfParentheses1(String S) {
return F(S, 0, S.length());
}
public int F(String S, int i, int j) {
//Score of balanced string S[i:j]
int ans = 0, bal = 0;
// Split string into primitives
for (int k = i; k < j; ++k) {
bal += S.charAt(k) == '(' ? 1 : -1;
if (bal == 0) {
if (k - i == 1) {
ans++;
} else {
ans += 2 * F(S, i + 1, k);
}
i = k + 1;
}
}
return ans;
}
}