有效的括号字符串[贪心练习]

前言

贪心最考察分析能力，且训练变通能力，往往不和经典的死知识点挂钩，而是寻找贪心点，再用代码把自己的想法实现。所以不能发呆，需稳步快想！

一、有效的括号字符串

二、寻找贪心点

package everyday.greed;

// 有效的括号字符串。
public class CheckValidString {
    
    /* target：不要发呆！稳步快想。 采用一般的栈思想来括号匹配，碰到*号怎么办？ 用数组+len实现栈，当碰到 ')' 时，取把 ‘*’ 号前面 ‘(' 变为 ’*‘ ，为什么这样做？ 试想一下，此时的 ’*‘ 可变 ’)‘ ，也可变 '(' ，也可当作 空串，是局部信息不能做出正确判定的时候！ 如果缺'(',留住*号后面让它变；如果缺右，留着*号后面让它变。空串同理。 贪心核心：把*留到最后，防止前期用错了，毕竟它是万能的，可左右不万能，先让固定括号匹配去对消左右括号。 */
    public boolean checkValidString(String s) {
    
        int[] sk = new int[100];
        int len = 0;

        for (char c : s.toCharArray()) {
    
            if (c == '(') sk[len++] = 1;
            if (c == '*') sk[len++] = 0;
            if (c == ')') {
    
                if (len == 0) return false;
                // 寻找前面的 ’(‘ 号
                int i = len - 1;
                while (i >= 0 && sk[i] != 1) --i;
                if (i >= 0) sk[i] = 0;// 将左括号变星号。

                len--;
            }
        }
        // 拿到全局信息，可以来做正确的判定了。
        // 看看后面的 星号 是否能足够填充前面的 左括号。
        int m = 0;// 代表后面星号的个数。注：这里其实有以前练习的抽象思想，我们不关心这一个个号，我们关心这一组符号有多少，将数量m抽象出来。
        for (int i = len - 1; i >= 0; i--) {
    
            if (sk[i] == 1 && m == 0) return false;

            if (sk[i] == 0) ++m;
            else --m;
        }
        return true;
    }
}

总结

1）练习贪心问题，可锻炼分析能力，数据结构巧妙运用能力。
2）不要发呆，稳步快想！
3）训练抽象能力，否则不能巧妙的将现实问题转化为代码，或者说很难转换。转换问题（配合数据结构&算法&循环分支&抽象能力）是解决问题的大方向之一，还有一类就是复杂性比较高，需要有拆解问题的能力，再联系相关知识点进行组合。
4）总的来说，就是抽象派 & 复杂组件派，对应抽象能力 & 知识点组合协调能力。

参考文献

[1] LeetCode 有效的括号字符串