1111.有效括号的嵌套深度
题目
有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。详情参见题末「有效括号字符串」部分。
嵌套深度 depth 定义：即有效括号字符串嵌套的层数，depth(A) 表示有效括号字符串 A 的嵌套深度。详情参见题末「嵌套深度」部分。
有效括号字符串类型与对应的嵌套深度计算方法如下图所示：
| 1.空字符串 | 2.AB型 | 3.(A)型 |
|---|---|---|
| “” | (())() |
((())()) |
| depth = 0 | depth = max(2,1) = 2 | depth = 1 + depth(A) = 3 |
给你一个「有效括号字符串」 seq，请你将其分成两个不相交的有效括号字符串，A 和 B，并使这两个字符串的深度最小。
- 不相交：每个
seq[i]只能分给A和B二者中的一个，不能既属于A也属于B。 A或B中的元素在原字符串中可以不连续。A.length + B.length = seq.length- 深度最小：
max(depth(A), depth(B))的可能取值最小。
划分方案用一个长度为 seq.length 的答案数组 answer 表示，编码规则如下：
answer[i] = 0，seq[i]分给 A 。answer[i] = 1，seq[i]分给 B 。
如果存在多个满足要求的答案，只需返回其中任意 一个 即可。
示例 1：
输入：seq = "(()())"
输出：[0,1,1,1,1,0]示例 2：
输入：seq = "()(())()"
输出：[0,0,0,1,1,0,1,1]
解释：本示例答案不唯一。
按此输出 A = "()()", B = "()()", max(depth(A), depth(B)) = 1，它们的深度最小。
像 [1,1,1,0,0,1,1,1]，也是正确结果，其中 A = "()()()", B = "()", max(depth(A), depth(B)) = 1 。提示：
1 < seq.size <= 10000
有效括号字符串：
仅由 “(“ 和 “)” 构成的字符串，对于每个左括号，都能找到与之对应的右括号，反之亦然。
下述几种情况同样属于有效括号字符串：
空字符串
连接，可以记作 AB（A 与 B 连接），其中 A 和 B 都是有效括号字符串
嵌套，可以记作 (A)，其中 A 是有效括号字符串
嵌套深度：
类似地，我们可以定义任意有效括号字符串 s 的 嵌套深度 depth(S)：
- s 为空时，depth(“”) = 0
- s 为 A 与 B 连接时，depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是有效括号字符串
- s 为嵌套情况，depth(“(“ + A + “)”) = 1 + depth(A)，其中 A 是有效括号字符串
例如：””，”()()”，和 “()(()())” 都是有效括号字符串，嵌套深度分别为 0，1，2，而 “)(“ 和 “(()” 都不是有效括号字符串。
思路
读懂题目意思很关键，可使用贪心的策略，保证每次分配括号之后，A和B的深度接近
class Solution {
public int[] maxDepthAfterSplit(String seq) {
int[] ans = new int[seq.length()];
int depth_a = 0;
int depth_b = 0;
int index = 0;
for(char c : seq.toCharArray()) {
if(c == '(') {
if(depth_a <= depth_b) {
ans[index] = 0;
depth_a++;
} else {
ans[index] = 1;
depth_b++;
}
} else if(c == ')') {
if(depth_a > depth_b) {
ans[index] = 0;
depth_a--;
} else {
ans[index] = 1;
depth_b--;
}
}
index++;
}
return ans;
}
}20.有效的括号
题目
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true示例 2:
输入: "()[]{}"
输出: true示例 3:
输入: "(]"
输出: false示例 4:
输入: "([)]"
输出: false示例 5:
输入: "{[]}"
输出: true思路
使用栈来模拟
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new LinkedList<>();
for(char c : s.toCharArray()) {
if(c == '(' || c == '{' || c == '[') {
stack.addFirst(c);
} else {
char temp = '\0';
if(stack.size() > 0) {
temp = stack.getFirst();
}
if((c == ')' && temp == '(') || (c == ']' && temp == '[') || (c == '}' && temp == '{')) {
stack.removeFirst();
} else {
stack.addFirst(c);
}
}
}
return stack.size() == 0;
}
}22.括号生成
题目
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]思路
1.暴力穷举
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
char[] parentheses = new char[2*n];
generaAll(parentheses, 0, ans);
return ans;
}
public void generaAll(char[] parentheses, int pos, List<String> ans) {
if(pos == parentheses.length) {
if(checkValid(parentheses)) {
ans.add(new String(parentheses));
}
} else {
parentheses[pos] = '(';
generaAll(parentheses, pos + 1, ans);
parentheses[pos] = ')';
generaAll(parentheses, pos + 1, ans);
}
}
public boolean checkValid(char[] parentheses) {
int ok = 0;
for(char c : parentheses) {
if(c == '(') {
ok++;
} else if(c == ')') {
ok--;
}
if(ok < 0) {
return false;
}
}
return ok == 0;
}
}2.DFS，回溯
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
dfs("", n, n, ans);
return ans;
}
public void dfs(String current, int open, int close, List<String> ans) {
if(open == 0 && close == 0) {
ans.add(current);
} else {
if(open > 0) {
dfs(current + "(", open - 1, close, ans);
}
if(close > 0 && close > open) {
dfs(current + ")", open, close - 1, ans);
}
}
}
}3.动态规划
class Solution {
public List<String> generateParenthesis(int n) {
if(n <= 0) {
return new ArrayList<>();
}
List<List<String>> dp = new ArrayList<>();
List<String> dp0 = new ArrayList<>();
dp0.add("");
dp.add(dp0);
for(int i = 1; i <= n; i++) {
List<String> cur = new ArrayList<>();
for(int j = 0; j < i; j++) {
List<String> str1 = dp.get(j);
List<String> str2 = dp.get(i - j - 1);
for(String s1 : str1) {
for(String s2 : str2) {
cur.add("(" + s1 + ")" + s2);
}
}
}
dp.add(cur);
}
return dp.get(n);
}
}32.最长有效括号
题目
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"思路
class Solution {
public int longestValidParentheses(String s) {
int[] dp = new int[s.length()];
int maxLen = 0;
char[] array = s.toCharArray();
for(int i = 1; i < s.length(); i++) {
if(array[i] == ')') {
if(array[i-1] == '(') {
dp[i] = (i >= 2 ? dp[i-2] : 0) + 2;
} else if(i - dp[i-1] > 0 && array[i - dp[i-1] - 1] == '(') {
dp[i] = dp[i-1] + 2 + (i - dp[i-1] - 2 >= 0 ? dp[i - dp[i-1] - 2] : 0);
}
maxLen = Math.max(maxLen, dp[i]);
}
}
return maxLen;
}
}
