726原子的数量

傷城~ 2023-02-27 08:25 37阅读 0赞

## 一、前言 ##

分类：Hash Table。

问题来源LeetCode 726 难度：困难。

问题链接：[https://leetcode-cn.com/problems/number-of-atoms/][https_leetcode-cn.com_problems_number-of-atoms]

## 二、题目 ##

给定一个化学式formula（作为字符串），返回每种原子的数量。原子总是以一个大写字母开始，接着跟随0个或任意个小写字母，表示原子的名字。如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。

给定一个化学式，输出所有原子的数量。格式为：第一个（按字典序）原子的名子，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。

**示例 1 :**

输入: 
    formula = "H2O"
    输出: "H2O"
    解释: 
    原子的数量是 {'H': 2, 'O': 1}。

**示例 2:**

输入: 
    formula = "Mg(OH)2"
    输出: "H2MgO2"
    解释: 
    原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。

**示例 3:**

输入: 
    formula = "K4(ON(SO3)2)2"
    输出: "K4N2O14S4"
    解释: 
    原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。

**注意:**

*  所有原子的第一个字母为大写，剩余字母都是小写。
 *  formula的长度在\[1, 1000\]之间。
 *  formula只包含字母、数字和圆括号，并且题目中给定的是合法的化学式。

## 三、思路 ##

看到这个问题最新想到的是用栈实现表达式，有相似之处，但不完全适合。可以借鉴栈实现表达式的思想，对于一个正确的输入参数，一个右括号会有一个对应的左括号，从右往左扫描，用栈记录数值，map记录已经访问的原子和原子数。

**复杂度分析：**

*  时间复杂度：O(n)
 *  空间复杂度：O(n)

**图解：**

*  输入: "K4(ON(SO3)2)2"
 *  输出: "K4N2O14S4"

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70][]

最终结果：K4N2O14S4

## 四、总结 ##

1.  有先后顺序要求，可以考虑用栈辅助处理；
2.  要按照字典顺序的要求，可以考虑用数组、map辅助处理，这里原子可能不止一个字符用map更方便些，map底层用的是红黑树不是哈希表。

## 五、编码实现 ##

//==========================================================================
    /*
    * @file    : 726_CountOfAtoms.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107392465
    * @author  : niebingyu
    * @date    : 2020/07/16
    * @title   : 726.原子的数量
    * @purpose : 给定一个化学式formula（作为字符串），返回每种原子的数量。
    * 原子总是以一个大写字母开始，接着跟随0个或任意个小写字母，表示原子的名字。
    * 如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。
    * 两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。
    * 一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。
    * 给定一个化学式，输出所有原子的数量。格式为：第一个（按字典序）原子的名子，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。
    *
    * 示例 1 :
    * 输入: formula = "H2O"
    * 输出: "H2O"
    * 解释: 原子的数量是 {'H': 2, 'O': 1}。
    *
    * 示例 2:
    * 输入: formula = "Mg(OH)2"
    * 输出: "H2MgO2"
    * 解释: 原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。
    *
    * 示例 3:
    * 输入: formula = "K4(ON(SO3)2)2"
    * 输出: "K4N2O14S4"
    * 解释: 原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。
    *
    *
    * 来源：力扣（LeetCode）
    * 难度：困难
    * 链接：https://leetcode-cn.com/problems/number-of-atoms
    */
    //==========================================================================
    #pragma once
    #include <iostream>
    #include <sstream>
    #include <vector>
    #include <stack>
    #include <map>
    #include <algorithm>
    using namespace std;
    
    #define NAMESPACE_COUNTOFATOMS namespace NAME_COUNTOFATOMS {
    #define NAMESPACE_COUNTOFATOMSEND }
    NAMESPACE_COUNTOFATOMS
    
    class Solution 
    {
    public:
        string countOfAtoms(string formula) 
        {
            // 这里没有判断：小写字母最前面会有一个大写字母
            map<string, int> mp;
            stack<int> stk;
            int atomNum = 1; // 最近扫描的原子数
            string atomStr;  // 最近扫描的原子
            for (int i = formula.size() - 1; i >= 0; --i)
            {
                if (formula[i] >= 'A' && formula[i] <= 'Z')
                {
                    int temp = atomNum;
                    if (!stk.empty()) temp *= stk.top();
                    atomStr = formula[i] + atomStr;
                    mp[atomStr] += temp;
                    atomStr = "";
                    atomNum = 1;
                }
                else if (formula[i] >= 'a' && formula[i] <= 'z')
                {
                    atomStr = formula[i];
                    while (i > 0 && formula[i-1] >= 'a' && formula[i-1] <= 'z')
                    {
                        atomStr = formula[i-1] + atomStr; 
                        --i;
                    }
                }
                else if (formula[i] == '(') // 左括号
                {
                    if (!stk.empty())
                        stk.pop();
    
                    atomNum = 1;
                }
                else if (formula[i] == ')') // 右括号
                {
                    if (!stk.empty())
                        atomNum *= stk.top();
    				
                    stk.push(atomNum);
                    atomNum = 1;
                }
                else if (formula[i] >= '0' && formula[i] <= '9') // 数字
                {
                    atomNum *= (formula[i] - '0');
                    int num = 1;	// 数字个数
                    while (i > 0 && formula[i - 1] >= '0' && formula[i - 1] <= '9')
                    {
                        atomNum += (formula[i - 1] - '0') * (int)pow(10, num);
                        --i; ++num;
                    }
                }
                else
                    return ""; // 参数错误
            }
    
            if (!stk.empty())
                return "";	//参数错误
    
            stringstream ss;
            for (auto it : mp)
            {
                ss << it.first;
                if (it.second > 1)
                    ss << it.second;
            }
    
            string ansStr;
            ss >> ansStr;
            return ansStr;
        }
    };
    
    以下为测试代码//
    // 测试 用例 START
    void test(const char* testName, string formula, string expect)
    {
        Solution s;
        string result = s.countOfAtoms(formula);
        if (expect == result)
            cout << testName << ", solution passed." << endl;
        else
            cout << testName << ", solution failed. expect: " << expect <<" ,result:" << result << endl;
    }
    
    // 测试用例
    void Test1()
    {
        string formula = "H2O";
        string expect = "H2O";
    
        test("Test1()", formula, expect);
    }
    
    void Test2()
    {
        string formula = "Mg(OH)2";
        string expect = "H2MgO2";
    
        test("Test2()", formula, expect);
    }
    
    void Test3()
    {
        string formula = "K4(ON(SO3)2)2";
        string expect = "K4N2O14S4";
    
        test("Test3()", formula, expect);
    }
    NAMESPACE_COUNTOFATOMSEND
    // 测试 用例 END
    //
    
    void CountOfAtoms_Test()
    {
        NAME_COUNTOFATOMS::Test1();
        NAME_COUNTOFATOMS::Test2();
        NAME_COUNTOFATOMS::Test3();
    }

**执行结果：**

![2020071620185854.png][]

[https_leetcode-cn.com_problems_number-of-atoms]: https://leetcode-cn.com/problems/number-of-atoms/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25pZTIzMTQ1NTA0NDE_size_16_color_FFFFFF_t_70]: /images/20230209/0af65acdd346468c8ad1c654ea59dfe6.png
[2020071620185854.png]: /images/20230209/760987b389c444ae9f44550388d08fd6.png