Question

640. 求解方程

English Version

题目描述

求解一个给定的方程，将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 只有一个 '='. 
• 方程由绝对值在 [0, 100]  范围内且无任何前导零的整数和变量 'x' 组成。​​​

解法

方法一：数学

将方程 $equation$ 按照等号 “=” 切分为左右两个式子，分别算出左右两个式子中 "x" 的系数 $x_i$，以及常数的值 $y_i$。

那么方程转换为等式 $x_1 \times x + y_1 = x_2 \times x + y_2$。

• 当 $x_1 = x_2$：若 $y_1 \neq y_2$，方程无解；若 $y_1=y_2$，方程有无限解。
• 当 $x_1 \neq x_2$：方程有唯一解 $x=\frac{y_2-y_1}{x_1-x_2}$。

相似题目：

• 592. 分数加减运算

class Solution:
  def solveEquation(self, equation: str) -> str:
    def f(s):
      x = y = 0
      if s[0] != '-':
        s = '+' + s
      i, n = 0, len(s)
      while i < n:
        sign = 1 if s[i] == '+' else -1
        i += 1
        j = i
        while j < n and s[j] not in '+-':
          j += 1
        v = s[i:j]
        if v[-1] == 'x':
          x += sign * (int(v[:-1]) if len(v) > 1 else 1)
        else:
          y += sign * int(v)
        i = j
      return x, y

    a, b = equation.split('=')
    x1, y1 = f(a)
    x2, y2 = f(b)
    if x1 == x2:
      return 'Infinite solutions' if y1 == y2 else 'No solution'
    return f'x={(y2 - y1) // (x1 - x2)}'

class Solution {
  public String solveEquation(String equation) {
    String[] es = equation.split("=");
    int[] a = f(es[0]), b = f(es[1]);
    int x1 = a[0], y1 = a[1];
    int x2 = b[0], y2 = b[1];
    if (x1 == x2) {
      return y1 == y2 ? "Infinite solutions" : "No solution";
    }
    return "x=" + (y2 - y1) / (x1 - x2);
  }

  private int[] f(String s) {
    int x = 0, y = 0;
    if (s.charAt(0) != '-') {
      s = "+" + s;
    }
    int i = 0, n = s.length();
    while (i < n) {
      int sign = s.charAt(i) == '+' ? 1 : -1;
      ++i;
      int j = i;
      while (j < n && s.charAt(j) != '+' && s.charAt(j) != '-') {
        ++j;
      }
      String v = s.substring(i, j);
      if (s.charAt(j - 1) == 'x') {
        x += sign * (v.length() > 1 ? Integer.parseInt(v.substring(0, v.length() - 1)) : 1);
      } else {
        y += sign * Integer.parseInt(v);
      }
      i = j;
    }
    return new int[] {x, y};
  }
}

func solveEquation(equation string) string {
  f := func(s string) []int {
    x, y := 0, 0
    if s[0] != '-' {
      s = "+" + s
    }
    i, n := 0, len(s)
    for i < n {
      sign := 1
      if s[i] == '-' {
        sign = -1
      }
      i++
      j := i
      for j < n && s[j] != '+' && s[j] != '-' {
        j++
      }
      v := s[i:j]
      if s[j-1] == 'x' {
        a := 1
        if len(v) > 1 {
          a, _ = strconv.Atoi(v[:len(v)-1])
        }
        x += sign * a
      } else {
        a, _ := strconv.Atoi(v)
        y += sign * a
      }
      i = j
    }
    return []int{x, y}
  }

  es := strings.Split(equation, "=")
  a, b := f(es[0]), f(es[1])
  x1, y1 := a[0], a[1]
  x2, y2 := b[0], b[1]
  if x1 == x2 {
    if y1 == y2 {
      return "Infinite solutions"
    } else {
      return "No solution"
    }
  }
  return fmt.Sprintf("x=%d", (y2-y1)/(x1-x2))
}

function solveEquation(equation: string): string {
  const [left, right] = equation.split('=');
  const createExpr = (s: string) => {
    let x = 0;
    let n = 0;
    let i = 0;
    let sym = 1;
    let cur = 0;
    let isX = false;
    for (const c of s) {
      if (c === '+' || c === '-') {
        if (isX) {
          if (i === 0 && cur === 0) {
            cur = 1;
          }
          x += cur * sym;
        } else {
          n += cur * sym;
        }
        isX = false;
        cur = 0;
        i = 0;
        if (c === '+') {
          sym = 1;
        } else {
          sym = -1;
        }
      } else if (c === 'x') {
        isX = true;
      } else {
        i++;
        cur *= 10;
        cur += Number(c);
      }
    }
    if (isX) {
      if (i === 0 && cur === 0) {
        cur = 1;
      }
      x += cur * sym;
    } else {
      n += cur * sym;
    }
    return [x, n];
  };
  const lExpr = createExpr(left);
  const rExpr = createExpr(right);
  if (lExpr[0] === rExpr[0]) {
    if (lExpr[1] !== rExpr[1]) {
      return 'No solution';
    }
    return 'Infinite solutions';
  }
  return `x=${(lExpr[1] - rExpr[1]) / (rExpr[0] - lExpr[0])}`;
}