Valid bracketed strings [greedy exercise]

前言

Greed is the most important test of analytical ability,and training flexibility,Often not linked to the classic dead knowledge point,Instead, look for greedy points,Then use code to realize your ideas.So don't be in a daze,Need to think steadily！

一、有效的括号字符串

二、Look for greedy points

package everyday.greed;

// 有效的括号字符串.
public class CheckValidString {
    
    /* target：不要发呆！Think steadily. Use general stack thinking for bracket matching,碰到*号怎么办？ 用数组+len实现栈,当碰到 ')' 时,take the handle ‘*’ 号前面 ‘(' 变为 ’*‘ ,为什么这样做？ 试想一下,此时的 ’*‘ 可变 ’)‘ ,也可变 '(' ,也可当作 空串,This is when local information cannot make a correct decision！ 如果缺'(',留住*Make it change after the number;If missing right,留着*Make it change after the number.Empty strings are the same. 贪心核心：把*留到最后,To prevent the wrong use in the early stage,After all it is omnipotent,But it is not omnipotent,Let the fixed brackets match first to cancel the left and right brackets. */
    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;
                // Look for the front ’(‘ 号
                int i = len - 1;
                while (i >= 0 && sk[i] != 1) --i;
                if (i >= 0) sk[i] = 0;// Change the left parenthesis to an asterisk.

                len--;
            }
        }
        // Get global information,It is time to make a correct judgment.
        // 看看后面的 星号 Is it enough to fill the front 左括号.
        int m = 0;// Represents the number of asterisks that follow.注：There are actually abstract ideas from previous exercises here,We don't care about this one number,We care how many symbols this group has,将数量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）Practice greed problems,Can exercise analytical skills,Skillful use of data structures.
2）不要发呆,Think steadily！
3）Train abstract skills,Otherwise, it is impossible to cleverly convert real-world problems into code,Or rather difficult to convert.转换问题（Match the data structure&算法&循环分支&抽象能力）It is one of the major directions to solve the problem,Another category is the high complexity,The ability to dismantle problems is required,Then contact the relevant knowledge points to combine.
4）总的来说,It's abstraction & Complex component pie,Corresponds to abstract ability & Knowledge point combination coordination ability.

参考文献

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