专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

现在是3月份，正是找工作的时候，大家不要被一些所谓的高薪工作给迷惑了，尤其是国外的工作，如果是国企外派过去的倒还好一些，如果是自己在网上找的，一定要谨慎。

最近网上有三人收到一条短信，大致内容是给他们提供一份工作，工作内容是剪辑和拍摄，一个月赚七八万，五六十万的都有。虽然他们并无相关工作经验，仍按照对方指示来到广西，企图偷渡出境。幸好，出租车司机发现并报了警，民警及时把他们拦截。

我记得在2019年和2020年找工作的时候，也收到一些需要出国的工作，工资要比国内高一些，一个是菲律宾一个是泰国，他们说这些国家软件开发不行，需要国内的人过去，我当时没考虑到是诈骗，但觉得太远，直接拒绝了。还好没去，印象中那几年招人到东南亚的挺多的。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第1249题：移除无效的括号，难度中等 。

给你一个由 '('、')' 和小写字母组成的字符串 s。你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。请返回任意一个合法字符串。

示例1：

输入：s = "lee(t(c)o)de)" 输出："lee(t(c)o)de" 解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。

示例2：

输入：s = "a)b(c)d" 输出："ab(c)d"

  • 1 <= s.length <= 10^5

  • s[i] 可能是 '('、')' 或英文小写字母

问题分析

这题说的是删除最少的括号，使剩下的括号有效，其中字母不要删除。实际上这是一道括号匹配问题，匹配的时候我们只需要考虑左括号和右括号，其它的字符不需要考虑。

我们使用一个栈只记录左括号 '(' 的下标，如果遇到左括号就把它压栈，然后标记为删除状态，这里为什么要把它标记为可删除状态？因为后面如果能遇到匹配的右括号 ')' ，再把它恢复为不可删除状态，如果后面遇不到匹配的右括号 ')' ，说明这个左括号是无效。

如果遇到右括号 ')' ，并且栈是空的，说明没有和这个右括号匹配的左括号，把这个右括号标记为可删除状态。如果栈不为空，那么当前右括号就和栈顶的左括号是匹配的，栈顶的左括号出栈，把它们都标记为不可删除状态。

最后在遍历整个字符串，去掉删除状态的括号即可。

JAVA：

public String minRemoveToMakeValid(String s) {     boolean[] deleted = newboolean[s.length()];// 标记哪些括号是被删除的     Stack stk =  new Stack<>();     for (int i = 0; i < s.length(); i++) {         if (s.charAt(i) == '(') {             // 左括号，先标记为删除状态，如果能遇到右括号，再标记为不可删除状态。             stk.push(i);             deleted[i] = true;         } elseif (s.charAt(i) == ')') {             if (stk.empty()) {                 // 栈是空的，说明当前右括号没有可匹配的，标记为删除状态。                 deleted[i] = true;             } else {                 // 这里的右括号和栈顶的左括号匹配，标记为不可删除状态。                 deleted[stk.pop()] = false;                 deleted[i] = false;             }         }     }     // 去掉删除状态的字符。     StringBuilder ans = new StringBuilder();     for (int i = 0; i < s.length(); i++) {         if (!deleted[i])             ans.append(s.charAt(i));     }     return ans.toString(); }

C++：

public:     string minRemoveToMakeValid(string s) {         vector

  deleted(s.length(), false);// 标记哪些括号是被删除的         stack

 stk;         for (int i = 0; i < s.length(); i++) {             if (s[i] == '(') {                 // 左括号，先标记为删除状态，如果能遇到右括号，再标记为不可删除状态。                 stk.push(i);                 deleted[i] = true;             } elseif (s[i] == ')') {                 if (stk.empty()) {                     // 栈是空的，说明当前右括号没有可匹配的，标记为删除状态。                     deleted[i] = true;                 } else {                     // 这里的右括号和栈顶的左括号匹配，标记为不可删除状态。                     deleted[stk.top()] = false;                     stk.pop();                     deleted[i] = false;                 }             }         }         // 去掉删除状态的字符。         string ans;         for (int i = 0; i < s.length(); i++) {             if (!deleted[i])                 ans += s[i];         }         return ans;     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。