思路
迭代算法

leetcode - 726. 原子的数量

July 05, 2021

思路

每个括号内的计算都是一个子问题,对这种子问题可以通过迭代或者递归的方式处理

迭代算法

graph TD
  findAtom[找到下一个原子]
  findFactor[找到原子下标]
  init[初始化栈] --> iterate[遍历字符串]
  iterate -->  judge{对当前字符char做状态判断}
  judge --"char === '('"--> push[新建一个哈希表, 并入栈]
  judge--"char === ')'"--> pop[出栈,并对当前栈的哈希表结算]
  judge--其它--> findAtom --> findFactor --> 计算原子数并加入到当前栈帧的哈希表
  pop --> 将当前哈希表计算结果累加到栈顶
  iterate --遍历结束--> 对栈顶计算最终结果
type StackFrame = Map<string, number>;

function countOfAtoms(formula: string): string {
  let point = 0;
  const stack: StackFrame[] = [];

  stack.unshift(new Map());

  function getAtom() {
    let result = formula[point++];
    while (point < formula.length && /[a-z]/.test(formula[point])) {
      result = result + formula[point];
      point++;
    }
    return result;
  }

  function getFactor() {
    let result = 0;
    while (point < formula.length && !isNaN(+formula[point])) {
      result = result * 10 + parseInt(formula[point], 10);
      point++;
    }
    return result || 1;
  }

  while (point < formula.length) {
    if (formula[point] === '(') {
      // 入栈
      stack.unshift(new Map());
      point++;
    } else if (formula[point] === ')') {
      // 出栈
      point++;
      const factor = getFactor();
      const curFrame = stack.shift();
      const topFrame = stack[0];

      for (const [atom, count] of curFrame.entries()) {
        const orginalCount = topFrame.get(atom) || 0;
        topFrame.set(atom, orginalCount + count * factor);
      }
    } else {
      // 对单原子处理
      const atom = getAtom();
      const factor = getFactor();

      stack[0].set(atom, (stack[0].get(atom) || 0) + factor);
    }
  }

  // 字典序排列
  const final = [...stack.shift()].sort();
  const result = [];
  for (let [atom, count] of final) {
    result.push(atom, count > 1 ? count : '');
  }
  return result.join('');
}

countOfAtoms('Mg(OH)2');

feiker 少年起而行之