fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
如何解决括号相关的问题 :: labuladong的算法小抄
都使用stack的解法，如下
// 921. 使括号有效的最少添加
public int minAddToMakeValid(String s) {
if (s.length() == 0) {
return 0;
}
int res = 0;
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(c);
} else {
if (!stack.isEmpty()) {
stack.pop();
} else {
res ++;
}
}
}
// 插入的右括号数量 + 多余的左括号数量
return res + stack.size();
}
1541. 平衡括号字符串的最少插入次数
public int minInsertions(String s) {
int n = s.length();
// 需要插入的右括号数量
int res = 0;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (c == '(') {
stack.push(c);
} else {
// 读下一位
if (i + 1 < n) {
if (s.charAt(i + 1) != ')') {
res++;
} else {
i++;
}
} else {
res++;
}
// 检查有没有可以匹配的左括号
if (!stack.isEmpty()) {
stack.pop();
} else {
res++;
}
}
}
// 插入的右括号数量 + 2倍的'多余的左括号数量'
return res + 2 * stack.size();
}
if (s[i] == '(') { need += 2; if (need % 2 == 1) { // 插入一个右括号 res++; // 对右括号的需求减一 need--; } }
为何插入一个右括号需要res++? res不是左括号‘(’插入的次数吗? 例如"()("这种情况, 为什么需要res++?
Java注释版
class Solution {
public int minInsertions(String s) {
int leftNeed=0,rightNeed=0;
for (char c : s.toCharArray()) {
if (c == '(') {
rightNeed += 2; // 右括号需求+2
if (rightNeed%2 == 1) { // 如果右括号为奇数，则插入一个右括号（例：")"）
rightNeed --; // 插入一个右括号，右括号需求减一
leftNeed ++; // 插入一个左括号，左括号需求加一
}
} else { // c==')'
rightNeed--;
if (rightNeed == -1) {
leftNeed++;
rightNeed = 1;
}
}
}
return leftNeed + rightNeed;
}
}
确实，res表示的是当前遍历过程中为了配平当前的状态，所需要插入左括号或是右括号的总次数，need表示的是遍历结束后仍需要的右括号数量，大家不要受前面例题的干扰
注意 ， 不要被前面 Leloz200 这位用户的评论误导, 这里的 result 并不是 左括号 需求,而是除了 左右括号对应添加的 need 以外人为为了保持规则，而添加的次数。
1541的javascript版本 对需要插入的左右括号进行了区分，方便理解
var minInsertions = function (s) {
let rightNeeds = 0;
let leftNeeds = 0;
let rightInsertTimes = 0;
let leftInsertTimes = 0;
for (let c of s) {
if (c === '(') {
rightNeeds += 2;
if (rightNeeds % 2 === 1) { // 奇数个
rightInsertTimes++;
rightNeeds--;
}
}
if (c === ')') {
rightNeeds--;
if (rightNeeds === -1) { // 多了一个右括号
leftInsertTimes++;
rightNeeds = 1;
}
}
}
return rightNeeds +leftNeeds+ rightInsertTimes + leftInsertTimes;
};
js版1541
/**
* @param {string} s
* @return {number}
*/
var minInsertions = function (s) {
let need = 0, res = 0;
let i = 0;
// res表示的是当前遍历过程中为了配平当前的状态，所需要插入左括号或是右括号的总次数，need表示的是遍历结束后仍需要的右括号数量
while (i < s.length) {
if (s[i] === '(') {
need += 2;
// 如果右括号是奇数个
// 根据左括号和右括号的比例1:2 所以右括号的个数必须是偶数才行
if (need % 2 === 1) {
res++; // 补上一个右括号
need--;// 对右括号的需求-1 因为正好利用一个右括号去和上面的左括号匹配
}
} else if (s[i] === ')') {
need--;
// 说明右括号太多了 情况:()))
// 需要给多的那个右括号补上 --> ( ())) )
if (need === -1) {
res++; // 补上一个左括号
need = 1; // 此时右括号需求变为1
}
}
i++;
}
return res + need;
};
根据东哥前一题的思路自己写了个方法, 对自己来说更容易想到。每个need对应两个右括号，每次出现右括号需要判断是否连续，若不连续则添加右括号;
class Solution {
public:
int minInsertions(string s) {
int res = 0;
int need = 0; // 需要右括号对的数量
for (int i = 0; i < s.length();) {
if (s[i] == '(') {
need += 1;
i++;
} else {
need--;
if (need == -1) { // 右括号出现的数量过多，需要添加一个左括号平衡右括号
res++;
need = 0;
}
if (i + 1 >= s.length() || s[i + 1] != ')') { // 如果出现的右括号不连续，则需要添加右括号
res++;
i++;
} else { // 若连续，则跳过第i和第i+1个右括号
i += 2;
}
}
}
return res + need * 2;
}
};
1、补充一下“当遇到左括号时，若对右括号的需求量为奇数，需要插入 1 个右括号”，这个地方如果不做判断，那么 "()()))“ 和 ")()))"这两种情况(能造成 need为奇数的也就这两种情况，一个是need==-1造成的，一个是本来就缺一个右括号)结果都为0，也就是说不加奇偶判断的话，是不能保证按"())"顺序闭合的，一个左括号出现之前，必须要保证之前的左括号都已经匹配完或者一个右括号也没匹配，所以这句话应该"当遇到左括号时，若对右括号的需求量为奇数，需要插入 1 个右括号，来匹配之前缺一个右括号的左括号" 2、此算法最后一个案例超时
分享一下使用stack的python写法
def minAddToMakeValid2(self, s):
stack = []
for i in s:
#如果是左括号，就入栈。当右括号时，同时栈顶为左括号时，则将左括号排出，最后留在栈内的括号数量就是需要加入的括号数量
if i == '(':
stack.append(i)
else:
if stack and stack[-1] == '(':
stack.pop()
else:
stack.append(i)
return len(stack)
921 题「 使括号有效的最少添加」：Python version
只需要在20题【有效的括号】的基础上稍作改动，有其他括号的暂时忽略
class Solution:
def minAddToMakeValid(self, s: str) -> int:
def leftof(c):
if c == '}':
return '{'
elif c == ')':
return '('
return '['
stack = []
count = 0
for c in s:
if c in ['{','[','(']:
stack.append(c)
else:
if stack and leftof(c) == stack[-1]:
stack.pop()
else:
count += 1
return count + len(stack)
