如何解决括号相关的问题 :: labuladong的算法小抄

[labuladong]

文章链接点这里：如何解决括号相关的问题

评论礼仪 见这里，违者直接拉黑。

[z-ak-z]

都使用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();
    }

[alexyuisme]

if (s[i] == '(') {
need += 2;
if (need % 2 == 1) {
// 插入一个右括号
res++;
// 对右括号的需求减一
need--;
}
}

为何插入一个右括号需要res++? res不是左括号‘(’插入的次数吗? 例如"()("这种情况, �为什么需要res++?

[yangyangDeveloper]

res的定义是插入操作 need的定义是 需要的右括号数量
题目说明 插入操作可以是 ( 也可以是 ）

比如：
( ) (
此时s[2] = “ ( ” need为3

代码逻辑如下 res 插入一次 ）
( ) ) (

插入的是） 所以 need - 1 变成了2 ， 末尾补 2个 ）

( ) ) ( ) )

[rattlesnakey]

同问！

[rattlesnakey]

感觉不需要去判断need%2 == 1，不需要去考虑这个情况

[Leloz00]

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;
    }
}

[Mochengz]

纠结好久才发现res记录的是当前总的插入次数，大家不要默认为是对左括号的需求了……

[pathjh]

确实，res表示的是当前遍历过程中为了配平当前的状态，所需要插入左括号或是右括号的总次数，need表示的是遍历结束后仍需要的右括号数量，大家不要受前面例题的干扰

[zhongweiLeex]

注意 ， 不要被前面 Leloz200 这位用户的评论误导, 这里的 result 并不是 左括号 需求,而是除了 左右括号对应添加的 need 以外人为为了保持规则，而添加的次数。

[xlintime]

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;
};

[Leochens]

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;
};

[bert82503]

打卡，感谢！

[deepbreath373]

check in

[ywj1352]

打卡

[lhcezx]

根据东哥前一题的思路自己写了个方法, 对自己来说更容易想到。每个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;
    }
};

[Velliy]

1、补充一下“当遇到左括号时，若对右括号的需求量为奇数，需要插入 1 个右括号”，这个地方如果不做判断，那么 "()()))“ 和 ")()))"这两种情况(能造成 need为奇数的也就这两种情况，一个是need==-1造成的，一个是本来就缺一个右括号)结果都为0，也就是说不加奇偶判断的话，是不能保证按"())"顺序闭合的，一个左括号出现之前，必须要保证之前的左括号都已经匹配完或者一个右括号也没匹配，所以这句话应该"当遇到左括号时，若对右括号的需求量为奇数，需要插入 1 个右括号，来匹配之前缺一个右括号的左括号"
2、此算法最后一个案例超时

[fjf3997]

顶你上去

[Velliy]

不好意思，看错了没有超时。

[reborm]

分享一下使用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)

[Alwin4Zhang]

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)

[yonggui-yan]

打卡打卡

多种括号-用栈
一种括号-维持所需的右括号数量need

[5Reasons]

东哥，第三题的Java代码好像粘贴错误啦，“第一步，我们按照刚才的思路正确维护 need 变量：” 之后的那个代码块

[labuladong]

收到，感谢反馈~

[mangohow]

921 Golang

func minAddToMakeValid(s string) int {
	res := 0
	// 左括号的数量
	left := 0
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			left++
			continue
		}
		left-- // 碰到右括号，匹配一个左括号
		// 如果没有左括号，需要插入一个
		if left < 0 {
			res++
			left = 0
		}
	}

	// left为最后剩余的右括号数量，需要插入left个右括号
	return res + left
}

1541 Golang

func minInsertions(s string) int {
	res := 0
	// 左括号的数量
	left := 0
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			left++
			continue
		}

		left--
		// 碰到右括号，但是没有左括号，需要插入一个左括号
		if left < 0 {
			res++
			left = 0
		}

		// 只有一个右括号，需要再插入一个括号
		if i+1 >= len(s) || s[i+1] != ')' {
			res++
		} else {
			i++
		}
	}

	// left为最后剩余的未匹配的左括号，需要插入2*left个右括号匹配
	res += 2 * left

	return res
}