递归

题目一

思路: 1.迭代
利用栈，令每个被括号包裹的子串返回一个 {元素名：出现次数} 的字典，汇总到上一层的字典中，统计结果。

class Solution {
public:
    string countOfAtoms(string formula) {
        stack<map<string,int>>s = solve(formula);
        map<string,int>mp = s.top();
        cout<<mp.size();
        string ans = "";
        for(auto t:mp){
            ans += (t.second > 1 ? t.first + to_string(t.second):t.first);
        }
        return ans;
    }
    stack<map<string,int>> solve(string formula){
        // 每一个括号包裹的子串都让返回一个 元素名：出现次数 的字典
        stack<map<string,int>>s;
        s.push(map<string,int>());
        int n = formula.size();
        for(int i=0;i<n;){
            if(formula[i]=='('){
                // 遇到左括号新增一个字典
                map<string,int>tmp;
                s.push(tmp);
                ++i;
            }
            else if(formula[i]>='A'&&formula[i]<='Z'){
                string t = "";
                // 记录元素名
                t += formula[i++];
                while(i<n&&(formula[i]>='a'&&formula[i]<='z'))
                    t+=formula[i++];
                // 记录后面跟着的出现次数
                int cnt = 0;
                while(i<n&&(formula[i]>='0'&&formula[i]<='9'))
                    cnt = cnt*10 + (formula[i++]-'0');
                    // 填到当前字典中
                    s.top()[t] += (cnt ? cnt : 1);
            }
            // 若是右括号，就把顶层字典弹出，将其中的信息汇总到次顶层字典中
            else if(formula[i]==')'){
                int cnt = 0;
                i++;
                while(i<n&&(formula[i]>='0'&&formula[i]<='9'))
                    cnt = cnt*10 + (formula[i++]-'0');
                map<string,int>mp = s.top(); s.pop();
                for(auto t:mp){
                    s.top()[t.first] += (t.second*cnt);
                }
            }
        }
        // 整个串处理完毕后 最终栈中只有一个字典
        return s;
    }
};

题目二：

思路1：迭代

class Solution {
public:
    string decodeString(string s) {
        if(s.empty()) return "";
        vector<int>cnt;
        vector<char>v;
        int num = 0;
        for(int i=0;i<s.size();++i)
        {
            // 字符的类型
            // 数字
            if(s[i]>='0'&&s[i]<='9')
            {
                num = num*10 + (s[i]-'0');
            }
            // 左括号
            else if(s[i]=='[')
            {
                v.push_back('[');
                cnt.push_back(num);
                num = 0;
            }
            // 右括号
            else if(s[i]==']'){
                string t = "";
                // 出栈直到遇见左括号
                while(v.back()!='[')
                {
                    char x = v.back();
                    t = x+t;
                    v.pop_back();
                }
                v.pop_back();
                // 这段字符要重复的次数
                int n = cnt.back();
                cnt.pop_back();
                while(n--)
                {
                    for(auto a:t)
                        v.push_back(a);
                }
            }
            // 字母
            else{
                v.push_back(s[i]);
            }
        }
        string ans = "";
        for(auto a:v)
            ans+=a;
        return ans;
    }
};

思路2：递归。难点在于递归结束的返回值设计。

class Solution {
public:
    string decodeString(string s) {
        string res = "";
        dfs(s,res,0);
       return res;
    }
    int dfs(string s,string& ans,int i){
        int num = 0;
        while(i<s.size()){
            if(isdigit(s[i]))
                num = num*10 + (s[i] - '0');
            else if(s[i]=='['){
                // 遇到'[',递归
                // 返回解码好的子串和']'位置的索引  递归设计的难点
                 string tmp = "";
                 int p = dfs(s,tmp,i+1);
                 while(num>0){
                     ans+=tmp;
                     num--;
                 }
                 i = p;
            }
            else if(s[i]==']')
                break;
            else ans+=s[i];
            ++i;
        }
        return i;
    }
};

题目三

思路1：递归

class Solution {
public:
    int scoreOfParentheses(string s) {
        int pos = 0;
        int score = dfs(s,pos);
        return score;
    }
    int dfs(string s,int& i){
        int ans = 0;
        while(i<s.size()){
            // 遇到左括号递归计算子串的分数
            // 返回分数和处理完的')'的下标
            if(s[i]=='('){
                int tmp = 0;
                i++;
                tmp = dfs(s,i);
                ans+=tmp;
            }
            else{
                ans = ans==0 ? 1 : ans*2;
                break;
            }
            ++i;
        }
        return ans;
    }
};

思路2：利用栈，迭代。

class Solution {
public:
    int scoreOfParentheses(string str) {
        int val = 0;
        // vector保存平衡括号子串的分数
        stack<vector<int>>s;
        // 加一层最外边的括号 方便处理
        s.push(vector<int>());
        for(int i=0;i<str.size();++i){
            // 遇到左括号 新增一个vector来记录子串分数
            if(str[i]=='('){
                s.push(vector<int>());
            }
            // 遇到右括号 弹出栈顶vector
            //  将计算好的子串分数汇总到次栈顶的vector中
            else{
                vector<int>tmp = s.top(); s.pop();
                if(tmp.empty())
                    s.top().push_back(1);
                else{
                    int sum = 0;
                    for(auto t:tmp)
                        sum+=t;
                    s.top().push_back(sum*2);
                }

            }
        }
        // 处理完毕后 只剩下最初新增在最外层的vector
        // 统计分数和即可
        vector<int>ans = s.top();
        for(auto a:ans)
            val+=a;
        return val;


    }
};