20. 有效的括号

图片.png

思路：建议一个栈，遇到左括号就压入栈，遇到右括号就和当前的栈顶符号作比较，如果不一样就返回false,一样则继续比较，直到栈为空，如果最后栈不为空则返回false

  1. class Solution {
  2. public:
  3.     bool isValid(string s) {
  4.         stack<char> st;
  5.         for(char c:s)
  6.         {
  7.             if(c=='('||c=='{'||c=='[')
  8.                 st.push(c);
  9.             else
  10.             {
  11.                 if(!st.empty()&&leftOf(c)==st.top())
  12.                     st.pop();
  13.                 else
  14.                     return false;
  15.             }
  16.         }
  17.         return st.empty();
  19.     }
  20.     char leftOf(char c)
  21.     {
  22.         if(c=='}')
  23.             return '{';
  24.         if(c==')')
  25.             return '(';
  26.         return '[';
  27.     }
  28. };
  29. //O(n)
  30. //O(n)

921. 使括号有效的最少添加

图片.png

思路：设置两个变量left,right,分别表示左括号的插入次数和对右括号的需求。 以左括号为基础，每遇到一个左括号则需要一个右括号，即right++; 当遇到一个右括号时，前面的右括号需求-1，即right—; 如果right==-1,说明右括号多出现了一次，因此需要补上1个left使得right=0

  1. class Solution {
  2. public:
  3.     int minAddToMakeValid(string s) {
  4.         int left=0,right=0;
  5.         for(char c:s)
  6.         {
  7.             if(c=='(')
  8.                 right++;//对右括号的需求+1
  9.             else//c==')'
  10.             {
  11.                 right--;//匹配到1个右括号 需求-1
  12.                 if(right==-1)//右括号出现多了1个 需要左括号
  13.                 {
  14.                     left++;//左括号插入次数+1
  15.                     right=0;//由于前面补充了1个左括号 此时对右括号的需求置0
  17.                 }
  18.             }
  19.         }
  20.         return left+right;
  21.     }
  22. };
  23. //O(n)
  24. //O(1)

1541. 平衡括号字符串的最少插入次数

图片.png

class Solution {
public:
    int minInsertions(string s) {
        //left: 左括号的插入次数  right: 对右括号的需求
        int left=0,right=0;
        for(char c:s)
        {
            if(c=='(')
            {
                right+=2;//当前遇到( 则对)的需求+2
                if(right%2==1)//对右括号的需求为奇数 说明少了1个右括号  应该插入1个右括号
                {
                    left++;//插入1个右括号后此时多了2个) 此时应该插入一个(与两个)匹配
                    right--;//由于插入了1个右括号 对右括号的需求-1
                }
            }
            else//遇到右括号
            {
                right--;//右括号需求-1
                if(right==-1)//右括号出现多了1次
                {

                    left++;//插入1个左括号
                    right=1;//由多一个变成少一个（需要1个）
                }
            }
        }
        return left+right;

    }
};
//O(n)
//O(1)