最近看到一个网友发帖，讲述了一件让人啼笑皆非的事情。
他说，公司新来了一个领导，38岁，一上任就给他加薪，从1w涨到1.5w。刚开始，他还以为领导搞错了，毕竟一般来说，换领导的第一反应不就是“新官上任三把火”嘛，怎么还可能给老员工加薪？结果，领导一开口说：“你是唯一的35岁老员工，咱们老人得互相帮忙。”
算法题：删除无效的括号
"(()())"输出："(()())""(())())"输出："(())"( 都有对应的右括号 )，并且括号配对必须是闭合的。第一步：用栈来处理
( 就是入栈操作，而右括号 ) 则是出栈操作。如果栈空了却遇到右括号，说明右括号多余了，这时就需要将这个无效的右括号去掉。代码实现
import java.util.Stack;
public class Solution {
public String removeInvalidParentheses(String s) {
Stack<Integer> stack = new Stack<>();
boolean[] toDelete = new boolean[s.length()];
// 第一遍遍历，检查不匹配的括号
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(i); // 将左括号的索引入栈
} else if (c == ')') {
if (stack.isEmpty()) {
toDelete[i] = true; // 右括号没有匹配的左括号，标记删除
} else {
stack.pop(); // 匹配的括号出栈
}
}
}
// 将栈中剩下的左括号标记为删除
while (!stack.isEmpty()) {
toDelete[stack.pop()] = true;
}
// 构造最终的有效字符串
StringBuilder result = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if (!toDelete[i]) {
result.append(s.charAt(i)); // 只保留不需要删除的字符
}
}
return result.toString();
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "(())())";
System.out.println(solution.removeInvalidParentheses(s)); // 输出 "(())"
}
}
首先，我们用一个栈来存储左括号的索引，右括号遇到时从栈中弹出一个左括号的索引。如果右括号没有匹配的左括号，则将其标记为要删除。 遍历完之后，栈里剩下的索引就是没有配对的左括号，需要标记为删除。 最后，我们通过一个布尔数组来构建最终的有效字符串，删掉那些标记为需要删除的字符。
关键点
栈的作用：栈帮助我们追踪左括号的配对情况。当遇到右括号时，我们检查栈顶是否有匹配的左括号。 删除标记：通过布尔数组 toDelete来标记哪些字符是无效的。这个方法比直接操作字符串更高效，因为字符串是不可变的，直接修改会造成性能浪费。处理无效括号：无效的右括号和左括号都需要标记删除，确保最终输出的字符串是有效的。
结束语
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
