Re: [閒聊] 每日leetcode

[Rushia (早瀬ユウカの体操服 )]

726. Number of Atoms
https://leetcode.com/problems/number-of-atoms/
給你一個化學元素字串，該字串由多個元素符號、數字和括號組成，元素符號是一個
大寫字串(O)或一個大寫字串加小寫字串(Oa)，後面的數字表示元素的數量，如果只有
一個元素則不寫數字(E = 1個E, A2 = 2個A)，如果碰到括號的話要把括號裡面的數量
都乘算（如果括號外面有數字，例如： (A)2 = A2），求出展開並合併後的元素字串，
每個字串根據元素的字典順序排序，元素後面加上元素數量。


思路:
1.用一個stack來模擬元素的合併和乘算，最後把元素按照名稱排序後append起來。


Java code
---------------------------------------------------------
class Solution {
    public String countOfAtoms(String formula) {
        Deque<Pair> stack = new ArrayDeque();
        char[] ch = formula.toCharArray();
        int n = ch.length;
        for (int i = 0; i < n; i++) {
            if (ch[i] == '(') {
                stack.add(new Pair("(", 0));
            } else if (ch[i] == ')') {
                // 找出括號後面的數字(如果有)
                int j = i + 1;
                int cnt = 0;
                while (j < n && Character.isDigit(ch[j])) {
                    cnt = cnt * 10 + (ch[j++] - '0');
                }
                if (cnt == 0) {
                    cnt = 1;
                } else {
                    i = j - 1;
                }
                // pop直到遇到左括號(，保存pop的元素並乘以數量
                List<Pair> tmp = new ArrayList<>();
                Pair curr = stack.pollLast();
                while (curr.key != "(") {
                    curr.val *= cnt;
                    tmp.add(curr);
                    curr = stack.pollLast();
                }
                // 放回去stack
                for (Pair p : tmp) {
                    stack.add(p);
                }
            } else {
                // 找出元素符號
                String key = "" + ch[i];
                if (i + 1 < n && ch[i + 1] >= 'a' && ch[i + 1] <= 'z') {
                    key += ch[i + 1];
                    i++;
                }
                // 找出數字
                int j = i + 1;
                int cnt = 0;
                while (j < n && Character.isDigit(ch[j])) {
                    cnt = cnt * 10 + (ch[j++] - '0');
                }
                if (cnt == 0) {
                    cnt = 1;
                } else {
                    i = j - 1;
                }
                stack.add(new Pair(key, cnt));
            }
        }
        Map<String, Integer> map = new TreeMap<>();
        while (!stack.isEmpty()) {
            Pair curr = stack.pollLast();
            map.put(curr.key, map.getOrDefault(curr.key, 0) + curr.val);
        }
        // append
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            sb.append(entry.getKey());
            if (entry.getValue() != 1) {
                sb.append(entry.getValue());
            }
        }
        return sb.toString();
    }
}

class Pair {
    String key;
    int val;
    public Pair(String key, int val) {
        this.key = key;
        this.val = val;
    }
}
---------------------------------------------------------

非常醜代碼==

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720948994.A.665.html
推 oin1104: 大師
推 CanIndulgeMe: 技术大牛，好想成为你哦。