禹城有做网站,网站向哪里备案,温州设计集团网站建设,无极网站无极城市在线LeetCode-726 原子的数量 递归
题目链接#xff1a;LeetCode-726 原子的数量 给你一个字符串化学式 formula #xff0c;返回 每种原子的数量 。 原子总是以一个大写字母开始#xff0c;接着跟随 0 个或任意个小写字母#xff0c;表示原子的名字。 如果数量大于 1#xf…LeetCode-726 原子的数量 递归
题目链接LeetCode-726 原子的数量 给你一个字符串化学式 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}。 示例 4 输入formula “Be32” 输出“Be32” 提示 1 formula.length 1000formula 由英文字母、数字、’(’ 和 ‘)’ 组成formula 总是有效的化学式输出的所有值总是在 32-bit 整数范围内 本题并没有特别复杂、特别难理解的思路但是对于各种情况需要妥善地加以处理再配合递归的思想和 map 即可解出。
首先我们来分析以下我们在遍历给定的字符串的时候会遇到以下几种情况 常规情况 这里的情况指的是常规的字符和数字即没有括号的情况。在这种情况下我们知道大写字母及其后跟着的小写字母表示的是化学元素的名称而元素名称后面又有两种情况一是后面直接跟其他大写字母这种情况下即元素个数缺省默认为1另一种情况是后面跟着数字则数字表示该元素的原子个数。 括号 括号及嵌套括号的出现是这个题要仔细处理的一个情况。对于这种多层括号嵌套最里面的括号中就是我们上面的常规情况而不同级的括号嵌套这种情况非常适合我们用递归的方式进行处理。
在具体实现中我们将遍历字符串中遇到的字符分为以下三种情况 遇到 ( 当遇到左括号时我们要开始准备递归在这种情况下对当前括号里的子串进行递归调用并用一个子 map 来接收当前括号内子串的原子名称及个数。当我们遇到有括号会退出递归函数注意当退出递归函数时我们需要记录其后面的一个数字并将它乘到我们的子串得到的子 map 所统计的原子个数上。 遇到 ) 遇到右括号时我们肯定在之前遇到过一个左括号并进入递归函数这时我们只需返回并让遍历索引往后走一步即可。 其他情况 其他情况即上述常规情况我们遇到的是代表原子名称的字母和代表原子个数的数字。我们会分别实现两个函数来获取原子名称和个数。
其他需要注意的点
题目中要求的字典序map 会自动帮我们排序。整个过程中维护的遍历索引 i 需要再函数间传递时使用引用传递。
完整代码
class Solution {
private:int get_num(string s, int i) {string num ;while (isdigit(s[i])) {num s[i];}return num.empty() ? 1 : stoi(num);}string get_name(string s, int i) {string name ;while (isalpha(s[i]) (name.empty() || islower(s[i]))) {name s[i];}return name;}mapstring, int get_map(string s, int i) {mapstring, int ans;while (i ! s.length()) {if (s[i] () {mapstring, int temp get_map(s, i);int cnt get_num(s, i);for (auto kv : temp) {ans[kv.first] kv.second * cnt;}}else if (s[i] )) {i;return ans;}else {string name get_name(s, i);int cnt get_num(s, i);ans[name] cnt;}}return ans;}public:string countOfAtoms(string formula) {int i 0;string ans;for (auto kv : get_map(formula, i)) {ans kv.first;if (kv.second 1) {ans to_string(kv.second);}}return ans;}
};Ref
https://leetcode-cn.com/problems/number-of-atoms/
https://riba2534.blog.csdn.net/article/details/88591566
