🔗 🔴 726. Number of Atoms

tags: 字串(String) 堆疊(Stack) 雜湊表(Hash Table) 排序(Sorting)

題意

給定一個字串 formula\text{formula}，表示一個化學式，請返回每種原子的數量。

原子的名稱總是以大寫字母開頭，後面跟著零個或多個小寫字母。

如果該原子的數量大於 11，可能會跟著一個或多個數字表示數量。如果數量是 11，則後面不會有數字。

  • 例如，"H2O"\text{"H2O"} 和 "H2O2"\text{"H2O2"} 是有效的化學式，但 "H1O2"\text{"H1O2"} 是無效的。

兩個化學式可以連接在一起產生另一個化學式。

  • 例如，"H2O2He3Mg4"\text{"H2O2He3Mg4"} 也是一個化學式。

放在括號中的化學式，後面加上數字、或是不加數字，也是一個化學式。

  • 例如，"(H2O2)"\text{"(H2O2)"} 和 "(H2O2)3"\text{"(H2O2)3"} 都是化學式。

將原子依照其名稱的字母順序排列後，返回每個原子的數量，格式如下：第一個名稱（按字母順序排序），後面跟著它的數量（如果該數量大於 11），然後是第二個名稱（按字母順序排序），後面跟著它的數量（如果該數量大於 11），依此類推。

思路：堆疊(Stack) + 雜湊表(Hash Table)

對於這種括號結構的問題，我們可以使用 堆疊(stack) 來處理括號內的子化學式，並使用 雜湊表(Hash Table) 來記錄每種原子的數量。

具體步驟如下：

  1. 初始化：首先，我們需要一些變數來幫助我們解析化學式。 ii 用來遍歷字串，nn 是字串的長度。 stst 是一個堆疊，用來存放每層子化學式的原子數量。
  2. 遍歷字串：我們使用一個 while 迴圈來遍歷整個字串 formula\text{formula}。
    • 遇到左括號 ‘(’：我們遇到一個新的子化學式，將一個新的 Counter（或 map）推入堆疊。
    • 遇到右括號 ‘)’：這表示我們完成了一個子化學式的解析。接著，我們需要解析這個子化學式後面的數字（如果有的話），並將這個子化學式的原子數量乘以這個數字，然後將結果加回上一層的 Counter 中。
    • 遇到原子名稱：解析原子的名稱和數量，並將其加入當前層的 Counter 中。
  3. 合併結果：最終，堆疊中只會剩下一個 Counter，即整個化學式的原子數量。我們將這些原子按名稱的字母順序排序，並生成最終的結果字串。

複雜度分析

  • 時間複雜度：O(nlog⁡n)\mathcal{O}(n \log n)，其中 nn 是字串的長度。
    • 每個字元最多只會被處理一次。
    • 在最壞情況下原子的數量可能和字串的長度相當，故排序所有原子的時間複雜度為 O(nlog⁡n)\mathcal{O}(n \log n)。
  • 空間複雜度：O(n)\mathcal{O}(n)，最壞情況下堆疊的深度可能等於字串的長度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def countOfAtoms(self, formula: str) -> str:
        n = len(formula)
        i = 0
        st = [Counter()]
        while i < n:
            if formula[i] == '(':
                st.append(Counter())
                i += 1
            elif formula[i] == ')':
                i += 1
                j = i
                while j < n and formula[j].isdigit():
                    j += 1
                mul = int(formula[i:j] or 1)
                i = j
                cnt = st.pop()
                for k in cnt:
                    st[-1][k] += cnt[k] * mul
            else:
                j = i + 1
                while j < n and formula[j].islower():
                    j += 1
                elem = formula[i:j]
                i = j
                while j < n and formula[j].isdigit():
                    j += 1
                mul = int(formula[i:j] or 1)
                i = j
                st[-1][elem] += mul
        cnt = st[0]
        return ''.join(k + (str(v) if v > 1 else '') for k, v in sorted(cnt.items()))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    string countOfAtoms(string formula) {
        int n = formula.size(), i = 0;
        stack<map<string, int>> st;
        st.push({});
        while (i < n) {
            if (formula[i] == '(') {
                st.push({});
                i++;
            } else if (formula[i] == ')') {
                i++;
                int mul = 0;
                while (i < n && isdigit(formula[i])) mul = mul * 10 + formula[i++] - '0';
                mul = mul == 0 ? 1 : mul;
                auto cnt = st.top();
                st.pop();
                for (auto [k, v] : cnt) st.top()[k] += v * mul;
            } else {
                string elem = formula.substr(i++, 1);
                while (i < n && islower(formula[i])) elem += formula[i++];
                int mul = 0;
                while (i < n && isdigit(formula[i])) mul = mul * 10 + formula[i++] - '0';
                mul = mul == 0 ? 1 : mul;
                st.top()[elem] += mul;
            }
        }
        auto cnt = st.top();
        string ans;
        for (auto [k, v] : cnt) ans += k + (v > 1 ? to_string(v) : "");
        return ans;
    }
};

寫在最後

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail,
1 girl, solo, long hair, black hair, blue eyes, skirt, shirt, school uniform, standing, white shirt, short sleeves, pleated skirt, outdoors, sky, serafuku, (pink serafuku, pink school uniform), day, sailor collar, blurry, arm up, neckerchief, long skirt, girl