726. Number of Atoms

Leetcode link

解题思路

本题是一道 hard 的题目

这道题第一眼看感觉还蛮简单的，但是仔细研究之后发现其中还是有蛮多坑的，我们先来研究一下题目本身：

首先本题只有一个参数，就是 formula，他代表一个化学表达式，它包含三个部分：

• element：元素名称，可能是一个大写的字母（比如 O），也可能是一个大写字母跟着小写字母的组合（比如 He）
• count：原子的个数，如果没写就是一个（比如 O2 代表两个氧原子，O 代表一个）
• ()：括号，代表一组元素，如果括号后面有数字，则代表有多少组括号内的元素（比如 (HO)3 代表有 3 个氢、1 个氧）

题目要求我们把括号去除掉，按照字母顺序返回所有元素及其对应的个数（比如：Mg(OH)2 变成 H2MgO2，元素按照字母顺序排列，元素的个数紧跟其后）

一般解决这种字符串嵌套有两种思路：递归、堆栈

因为递归比较好理解，我们这里使用递归的思路来去做讲解

首先我们还是要正常的去遍历题目给到的字符串，在遍历的时候会出现三种可能：

• 遇到字母 & 数字：持续遍历字符串，并且把对应的元素与数量保存到一个对象中
• 遇到 (：需要遍历到下一个字符，然后递归调用分析函数
• 遇到 )：需要找到后面的数字，并且将其乘到当前括号的元素内，最后需要返回当前保存的对象

等到最后递归函数处理完成后，我们需要把对象返回给原函数，原函数会对对象数据进行排序、字符串化后返回结果

Javascript

/**
 * @param {string} formula
 * @return {string}
 */
var countOfAtoms = function (formula) {
  let result = [];
  const { res: resultMap } = parse(formula, 0);
  // 将对象数据整理成期望的格式
  for (const [element, count] of Object.entries(resultMap)) {
    result.push(element + (count === 1 ? "" : count));
  }
  // 记得排序后字符串化解答
  return result.sort().join('');
};

const parse = (formula, i) => {
  let res = {};
  while (i < formula.length) {
    if (formula[i] === '(') {
      // 遇到 ( 开启递归，记得要返回最新的遍历进度
      i++;
      let { res: subRes, i: subI } = parse(formula, i);
      i = subI;
      for (const [element, count] of Object.entries(subRes)) {
        res[element] = (res[element] || 0) + count;
      }
    } else if (formula[i] === ')') {
      // 遇到 ) 往后拿到数字，然后乘以前面的元素之后直接中断循环返回
      let begin = ++i;
      while (i < formula.length && /\d/.test(formula[i])) i++;
      let subStr = formula.slice(begin, i);
      let multiple = subStr === "" ? 1 : Number(subStr);
      for (const element in res) {
        res[element] *= multiple;
      }

      return { res, i };
    } else {
      // 遇到字母 & 数字：持续遍历，并将结果保存起来
      let begin = i++;
      while (i < formula.length && /[a-z]/.test(formula[i])) i++;
      const element = formula.slice(begin, i);
      begin = i;
      while (i < formula.length && /\d/.test(formula[i])) i++;
      const cnt = formula.slice(begin, i);
      res[element] = (res[element] || 0) + (cnt === "" ? 1 : Number(cnt));
    }
  }
  return { res, i };
}