【LeetCode】726. 原子的数量

【题目描述】

【解题思路】

首先当我看到题目的时候感觉任务很复杂，有大小写字母、有数字、有括号，还得按照字母的顺序输出，一想到还有括号自己就完全没有思路不知道该怎么办？但是这道题目的限制条件是逐渐增加难度，如果大家的逻辑能力不强建议，大家不要上来就全面的考虑问题，这样只会让菜狗的我越想越混乱。根据自己仅有的做题经验，我告诉自己先让代码能满足简单的示例，比如实例中没有括号的情况，然后在这个代码的基础上怎么处理括号问题。

然后简单列举一下我的一些解题办法：
1. 既然有原子的定义，如何找到原子是要解决的问题
2. 每个原子都有对应的数量，如何确定原子对应的数量也是要解决的问题
3. 看到输出的格式是按照的原子的字典序输出，可以很容易想到用java中的treemap保存原子和原子对应的数量
4. 一看到俄罗斯套娃式的括号我的第一反应是用递归的方法
5. 先处理没有括号的情况，在此基础上加入递归的代码

【没有括号的简单情况】

老实说，我感觉这道题如果不让处理括号的话感觉还是挺简单的，就是找到原子，然后找到原子对应的数量，将这样的一个原子数量对<string, integer>保存在treemap中最后统一输出。
这里根据我处理字符串带括号问题的一个习惯，我先做了一个预处理，就是将string类型的输入保存在deque<character>类型的双向队列当中进行后续的操作。

先写出代码的大框架

class solution {
    public string countofatoms(string formula) {
        // string ======> duque
        deque<character> formuladeque = new linkedlist<>();
        for(int i = 0; i < formula.length(); ++i) {
            formuladeque.offer(formula.charat(i));
        }
        // 解题主要函数， 保存每个原子和其对应的数量
        treemap<string, integer> treemap = countatoms(formuladeque);
        // 按照要求进行输出
        string res = "";
        for(string key : treemap.keyset()) {
            if(treemap.get(key) > 1) {
                res += key + treemap.get(key);
            } else {
                res += key;
            }
        }
        return res;
    }

    public treemap<string, integer> countatoms(deque<character> formuladeque) {
        // coding ....
    }
}

编写求原子和对应数量的函数countatoms(deque formuladeque)，不考虑括号情况

下面我们将经历放在求解这样的一个函数上。我们可以遍历当前字符串的每一个字符，根据不同的字符类型处理不同情况。例如对于h2o2he3mg4ot而言：
我们将每次找到的原子和数量保存在string atom = “” 和string digit = “”中。
1. 遇到大写字母
    - 可能是原子的第一个大写字母，此时应改追加原子字符
    - 也可能是下一个原子的第一个字符，这是就要根据已经找到的atom和digit将其加入到treemap中，并且更新atom和digit为找下一个原子数量对做准备。
2. 遇到小写字母
    - 追加原子字符
3. 遇到数字
    - 追加数字字符

下面贴上代码（注意遍历完好药处理一次atom和digit）

public treemap<string, integer> countatoms(deque<character> formuladeque) {
        treemap<string, integer> treemap = new treemap<>();
        string atom = "";
        string digit = "";
        while(!formuladeque.isempty()) {
            char cur = formuladeque.poll();
            if(character.isuppercase(cur)) {
                if(atom.equals("")) { // 开始，遇到第一个大写字母，原子以大写字母开始，添加原子
                    atom += cur;
                } else { // 结束，遇到下一个大写字母，记录原子和数量
                    if(digit.equals("")) {  // 如果digit为空应该表示为1
                        treemap.put(atom, treemap.getordefault(atom, 0) + 1);
                    } else {
                        treemap.put(atom, treemap.getordefault(atom, 0) + integer.parseint(digit));
                    }
                    // 更新
                    atom = "" + cur;
                    digit = "";
                }
            }
            if(character.islowercase(cur)) {
                atom += cur;
            }
            if(character.isdigit(cur)) {
                digit += cur;
            }
        }
        // 处理最后一次
        if(!atom.equals("")) {
            if(digit.equals("")) {
                treemap.put(atom, treemap.getordefault(atom, 0) + 1);
            } else {
                treemap.put(atom, treemap.getordefault(atom, 0) + integer.parseint(digit));
            }
        }
        return treemap;
    }

【处理括号的情况】

一般 “(”, “)” 需要用到递归的思路，大致的思想是

• 遇到“（” 开始递归
• 遇到“）” 结束递归
  在开始递归处的代码，我们需要将递归的结果追加到treemap中
  在结束递归处的代码，因为遇到“）”也可能是一个原子数量对寻找的结束标志，结束递归前要先将此时的atom和digit加入到treemap中，除此之外“）”后面可能会跟数字，还要根据会面的数字对此时treemap的数据进行翻倍，下面是代码。

public treemap<string, integer> countatoms(deque<character> formuladeque) {
        treemap<string, integer> treemap = new treemap<>();
        string atom = "";
        string digit = "";
        while(!formuladeque.isempty()) {
            char cur = formuladeque.poll();
            if(cur == '(') { // 开始递归操作
                // 将递归的结果追加到treemap
                treemap<string, integer> nexttreemap = countatoms(formuladeque);
                for(string key : nexttreemap.keyset()) {
                    treemap.put(key, treemap.getordefault(key, 0) + nexttreemap.get(key));
                }
            }
            if(character.isuppercase(cur)) {
                if(atom.equals("")) { // 开始，遇到第一个大写字母，原子以大写字母开始，添加原子
                    atom += cur;
                } else { // 结束，遇到下一个大写字母，记录原子和数量
                    if(digit.equals("")) {
                        treemap.put(atom, treemap.getordefault(atom, 0) + 1);
                    } else {
                        treemap.put(atom, treemap.getordefault(atom, 0) + integer.parseint(digit));
                    }
                    // 更新
                    atom = "" + cur;
                    digit = "";
                }
            }
            if(character.islowercase(cur)) {
                atom += cur;
            }
            if(character.isdigit(cur)) {
                digit += cur;
            }
            if(cur == ')') { // 结束递归
                // 如果此时atom非空，“）”在成了一次寻找atom和digit对结束，应该返回结果前加入treemap
                if(!atom.equals("")) {
                    if(digit.equals("")) {
                        treemap.put(atom, treemap.getordefault(atom, 0) + 1);
                    } else {
                        treemap.put(atom, treemap.getordefault(atom, 0) + integer.parseint(digit));
                    }
                }
                // 如果“）”后还有数字，要根据数字值对treemap里面的数据进行翻倍操作
                string nextdigit = "";
                while(!formuladeque.isempty() && character.isdigit(formuladeque.peekfirst())) {
                    nextdigit += formuladeque.poll();
                }
                if(!nextdigit.equals("")) {
                    for(string key : treemap.keyset()) {
                        treemap.put(key, treemap.get(key) * integer.parseint(nextdigit));
                    }
                }
                // 返回递归结果
                return treemap;
            }
        }
        if(!atom.equals("")) {
            if(digit.equals("")) {
                treemap.put(atom, treemap.getordefault(atom, 0) + 1);
            } else {
                treemap.put(atom, treemap.getordefault(atom, 0) + integer.parseint(digit));
            }
        }
        return treemap;
    }

【最后完整代码】（java）

class solution {
    public string countofatoms(string formula) {
        deque<character> formuladeque = new linkedlist<>();
        for(int i = 0; i < formula.length(); ++i) {
            formuladeque.offer(formula.charat(i));
        }
        treemap<string, integer> treemap = countatoms(formuladeque);
        string res = "";
        for(string key : treemap.keyset()) {
            if(treemap.get(key) > 1) {
                res += key + treemap.get(key);
            } else {
                res += key;
            }
        }
        return res;
    }

    public treemap<string, integer> countatoms(deque<character> formuladeque) {
        treemap<string, integer> treemap = new treemap<>();
        string atom = "";
        string digit = "";
        while(!formuladeque.isempty()) {
            char cur = formuladeque.poll();
            if(cur == '(') {
                treemap<string, integer> nexttreemap = countatoms(formuladeque);
                for(string key : nexttreemap.keyset()) {
                    treemap.put(key, treemap.getordefault(key, 0) + nexttreemap.get(key));
                }
            }
            if(character.isuppercase(cur)) {
                if(atom.equals("")) { // 开始，遇到第一个大写字母，原子以大写字母开始，添加原子
                    atom += cur;
                } else { // 结束，遇到下一个大写字母，记录原子和数量
                    if(digit.equals("")) {
                        treemap.put(atom, treemap.getordefault(atom, 0) + 1);
                    } else {
                        treemap.put(atom, treemap.getordefault(atom, 0) + integer.parseint(digit));
                    }
                    // 更新
                    atom = "" + cur;
                    digit = "";
                }
            }
            if(character.islowercase(cur)) {
                atom += cur;
            }
            if(character.isdigit(cur)) {
                digit += cur;
            }
            if(cur == ')') {
                if(!atom.equals("")) {
                    if(digit.equals("")) {
                        treemap.put(atom, treemap.getordefault(atom, 0) + 1);
                    } else {
                        treemap.put(atom, treemap.getordefault(atom, 0) + integer.parseint(digit));
                    }
                }
                string nextdigit = "";
                while(!formuladeque.isempty() && character.isdigit(formuladeque.peekfirst())) {
                    nextdigit += formuladeque.poll();
                }
                if(!nextdigit.equals("")) {
                    for(string key : treemap.keyset()) {
                        treemap.put(key, treemap.get(key) * integer.parseint(nextdigit));
                    }
                }
                return treemap;
            }
        }
        if(!atom.equals("")) {
            if(digit.equals("")) {
                treemap.put(atom, treemap.getordefault(atom, 0) + 1);
            } else {
                treemap.put(atom, treemap.getordefault(atom, 0) + integer.parseint(digit));
            }
        }
        return treemap;
    }
}

虽然代码效率不高，但是这种化繁为简，由简入深的解题思路还是很值得记录一下的，希望能帮助到大家。