有趣的算法03-三道括号问题

有趣的算法03

​ 为提升算法、编程能力,开始刷LeetCode,一些于我有益的题记录在此系列中(或许对大佬们而言尽是些简单的题,还请见谅)。同时感谢评论区的大佬们。
A mathematician, who is not also some thing of a poet, will never be a complete mathematician --Weierstraß

[有效的括号] -- 辅助栈

【问题描述】

​ 给定一个只包含'('、`)'、'{'、'}'、'['、']'的字符串,判断字符串是否有效,参LeetCode 20. 有效的括号。

【解法思路】

​ 使用一个栈来存储,每次读入进行入栈或出栈匹配,最为基础的题了。

public:
    bool isValid(string s) {
        stack<char> stack;
        char c;

        for(int i=0; i<s.size(); i++){
            c = s[i];

            if(c=='(') stack.push(')');
            else if(c=='[') stack.push(']');
            else if(c=='{') stack.push('}');
            else if(stack.empty()||c!=stack.top())
                return false;
            else stack.pop();
        }

        return stack.empty();
    }

[括号生成]

【题目描述】

​ 给出$n$表示要生成括号的对数,需要给出全部有效的括号组合。

【解法思路】

​ 每次只有两种可能,加入'('或加入')',增加两个计数器,分别记录可增加的'('数量和')'数量,参LeetCode 22. 括号生成。

public:
    vector<string> generateParenthesis(int n) {
        vector<string> s;
        s.push_back("");
        generate(s, 0, n, 0);
        return s;
    }

    void generate(vector<string> &s, int i, int n, int m){
          // '('分配完后,填入')'
        if(n==0){
            while(m>0){
                s[i]+=')';
                m--;
            }
            return;
        }

          // 加入'('
        string str = s[i];
        s[i] += '(';
        generate(s, i, n-1, m+1);

          // 加入')'
        if(m!=0){
            s.push_back(str+')');
            generate(s, s.size()-1, n, m-1);
        }

        return;
    }

[有效括号的嵌套深度]

【题目描述】

​ 将一个只含有'('和')'的有效括号字符串,分成两个有效括号字符串,使得分成的两个字符串的深度$\max({\rm depth}(A),{\rm depth}(B))$最小,参LeetCode 1111. 有效括号的嵌套深度。

【解法思路】

​ 根据第一题的思考,用辅助栈的思考可知,每个'('和')'都属于不同的深度层,如果要使两者深度最小,即分布要平均(即可以按照深度的奇偶进行分开)。

public:
    vector<int> maxDepthAfterSplit(string seq) {
        vector<int> ans(seq.length(),0);

        int dep = 0;
        for(int i=0; i<seq.length(); i++){
            if(seq[i]=='('){
                dep++;
                if(dep%2==0) ans[i]=1;
            }
            else{
                if(dep%2==0) ans[i]=1;
                dep--;
            }
        }

        return ans;
    }
​ 三道有关括号的简单题,一开始拿到第三题没有什么思路,但做完两题后,就会清楚许多了。

评论

暂无评论