中等

问题描述

求解一个给定的方程，将 x 以字符串 "x=#value" 的形式返回。该方程仅包含 '+' ， '-' 操作，变量 x 和其对应系数。

如果方程没有解，请返回 "No solution" 。如果方程有无限解，则返回 "Infinite solutions" 。

题目保证，如果方程中只有一个解，则 'x' 的值是一个整数。

示例 1：

输入: equation = "x+5-3+x=6+x-2"
输出: "x=2"

示例 2:

输入: equation = "x=x"
输出: "Infinite solutions"

示例 3:

输入: equation = "2x=x"
输出: "x=0"

提示:

• 3 <= equation.length <= 1000
• equation 只有一个 '='
• equation 方程由整数组成，其绝对值在 [0, 100] 范围内，不含前导零和变量 'x' 。

模拟

将表达式拆分为左右两部分，遍历左右两部分字符串，使用双指针分别拆分每个带符号数值或 $x$，分别计算左右部分 $x$ 的个数和数值的和，有以下几种情况：

• 左右两部分$x$个数相同，数值部分不同，表达式无解
• 左右两部分$x$个数相同，数值部分相同，表达式无限解
• 左右两部分$x$个数不相同，表达是解为 $x=\dfrac{rSum - lSum}{lXCnt - rXCnt}$

/**
 * @param {string} equation
 * @return {string}
 */
var solveEquation = function (equation) {
  const [left, right] = equation.split('=')
  const calc = (exp) => {
    let l = 0
    let r = 0
    let xcnt = 0
    let sum = 0
    while (r < exp.length) {
      while (r < exp.length && !['+', '-'].includes(exp[r])) r++
      const str = exp.substring(l, r)
      if (str.includes('x')) {
        const num = str.match(/-?\d+/g)
        if (num) {
          xcnt += +num[0]
        } else {
          if (str.startsWith('-')) xcnt--
          else xcnt++
        }
      } else {
        sum += +str
      }
      l = r++
    }
    return [xcnt, sum]
  }
  const [lXCnt, lSum] = calc(left)
  const [rXCnt, rSum] = calc(right)
  if (lXCnt === rXCnt) return lSum === rSum ? 'Infinite solutions' : 'No solution'
  return `x=${(rSum - lSum) / (lXCnt - rXCnt)}`
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$