每天一道算法题4

【括号有效配对】
括号有效配对是指：
1） 任何一个左括号都能找到和其正确配对的右括号
2）任何一个右括号都能找到和其正确配对的左括号
有效的：(()) ()() (()()) 等
无效的：(() )( 等
问题一：怎么判断一个括号字符串有效？
问题二：如果一个括号字符串无效，返回至少填几个字符能让其整体有效？

问题一：
用一个变量来记录，如果遇到左括号+1, 如果遇到右括号-1，在遍历过程中，只要出现一次为负数，则必为无效，如果遍历到结束，值为0，则说明字符串有效，否则为无效。

public static boolean valid(String s) {
    char[] str = s.toCharArray();
    int count = 0;
    for (int i = 0; i < str.length; i++) {
        count +=  str[i] == '(' ? 1 : -1;
        if (count < 0) {
            return false;
        }
    }
    return count == 0;
}

问题二：
再添加一个变量，need = 0, 如果遇到右括号时，当前count=0，说明这个右括号就是多的，则need++， 否则说明右括号不是多的，则count--；

public static int needParentheses(String s) {
    char[] str = s.toCharArray();
    int count = 0; 
    int need = 0;
    for (int i = 0; i < str.length; i++) {
        if (str[i] == '(') {
            count++;
        } else {
            if (count == 0) {
                need++;
            } else {
                count--;
            }
        }
    }
    return count + need;
}