LeetCode Solve the Equation

LeetCode Solve the Equation

Solve a given equation and return the value of x in the form of string "x=#value". The equation contains only '+', '-' operation, the variable xand its coefficient.

If there is no solution for the equation, return "No solution".

If there are infinite solutions for the equation, return "Infinite solutions".

If there is exactly one solution for the equation, we ensure that the value of x is an integer.

Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"

解一个一元一次方程。简单题,首先把方程分解成等号两边两个子表达式,然后解析这两个子表达式,使成为la+lb*x=ra+rb*x,再转换为(lb-rb)x=ra-la,令lb-rb=b, ra-la=a,则最终的表达式等价于bx=a。

如果b等于0,且a也等于0,则有无穷多解。如果b等于0,但a不等于0,则无解。否则x=a/b。

所以问题的难点是怎样把一个表达式转换为a+bx的形式。也就是代码中的convert函数。遍历字符串,取出每个带符号的操作数,如果该操作数包含'x',则取出系数,加到b上;否则是常数项,加到a上。

有一个需要注意的点是包含'x'的操作数可能是'-x'或者'+x',提取系数时需要特殊判断。

代码如下:

class Solution {
private:
	void convert(string& s, int& a, int& b) {
		int aa = 0, bb = 0;
		s += "+";
		int start = 0, end = 0;
		for (end = 0; end < s.size(); ++end) {
			if (end != 0 && (s[end] == '+' || s[end] == '-')) { // -x=-1
				string tmp = s.substr(start, end - start);
				if (tmp.find('x') != string::npos) {
					if (tmp == "x" || tmp == "+x")bb += 1;
					else if (tmp == "-x")bb -= 1;
					else bb += stoi(tmp.substr(0, tmp.size() - 1));
				}
				else {
					aa += stoi(tmp);
				}
				start = end;
			}
		}
		a = aa;
		b = bb;
	}
public:
	string solveEquation(string equation) {
		size_t pos = equation.find('=');
		string left = equation.substr(0, pos), right = equation.substr(pos + 1);
		int la = 0, lb = 0, ra = 0, rb = 0;
		convert(left, la, lb);
		convert(right, ra, rb);
		int b = lb - rb, a = ra - la;
		if (b == 0) {
			if (a == 0)return "Infinite solutions";
			else return "No solution";
		}
		else {
			return "x=" + to_string(a / b);
		}
	}
};

本代码提交AC,用时3MS。

Leave a Reply

Your email address will not be published. Required fields are marked *