0640-求解方程

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:29 2023-09-13 16:06:29 Updated    

求解一个给定的方程，将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' 组成。​​​

方法一：解析

我们将等式右边的项都移到等式左边，那么等式右边的项的默认系数为 -1。我们依次解析方程的项，并将同类项进行合并，使用 factor 表示变量的系数，val 表示常量值。

初始时默认系数 sign}_1 = 1，当我们解析到等号时，说明解析到等式右边的项，令 sign}_1 = -1。使用变量 sign}_2 表示项的符号，初始时 sign}_2 = \textit{sign}_1，如果我们解析到 +' 或 -‘，那么相应的更改 sign}_2。使用 number 记录数字，valid 表示 number 是否有效（变量 x 前面可能没有数字），如果我们解析到的项是变量项，那么相应的更改 factor；如果我们解析到的项是常量项，那么相应的更改 val。

如果 factor} = 0 成立，说明变量 x 对方程无影响，然后判断 val} = 0 是否成立，成立则说明方程有无数解，返回 Infinite solutions"，否则返回 No solution”。其他情况直接返回对应的整数解 x = \dfrac{-\textit{val}}{\textit{factor}。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def solveEquation(self, equation: str) -> str:
        factor = val = 0
        i, n, sign = 0, len(equation), 1  # 等式左边默认系数为正
        while i < n:
            if equation[i] == '=':
                sign = -1
                i += 1
                continue

            s = sign
            if equation[i] == '+':  # 去掉前面的符号
                i += 1
            elif equation[i] == '-':
                s = -s
                i += 1

            num, valid = 0, False
            while i < n and equation[i].isdigit():
                valid = True
                num = num * 10 + int(equation[i])
                i += 1

            if i < n and equation[i] == 'x':  # 变量
                factor += s * num if valid else s
                i += 1
            else:  # 数值
                val += s * num

        if factor == 0:
            return "No solution" if val else "Infinite solutions"
        return f"x={-val // factor}"
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    string solveEquation(string equation) {
        int factor = 0, val = 0;
        int index = 0, n = equation.size(), sign1 = 1; // 等式左边默认系数为正
        while (index < n) {
            if (equation[index] == '=') {
                sign1 = -1; // 等式右边默认系数为负
                index++;
                continue;
            }

            int sign2 = sign1, number = 0;
            bool valid = false; // 记录 number 是否有效
            if (equation[index] == '-' || equation[index] == '+') { // 去掉前面的符号
                sign2 = (equation[index] == '-') ? -sign1 : sign1;
                index++;
            }
            while (index < n && isdigit(equation[index])) {
                number = number * 10 + (equation[index] - '0');
                index++;
                valid = true;
            }

            if (index < n && equation[index] == 'x') { // 变量
                factor += valid ? sign2 * number : sign2;
                index++;
            } else { // 数值
                val += sign2 * number;
            }
        }

        if (factor == 0) {
            return val == 0 ? "Infinite solutions" : "No solution";
        }
        return string("x=") + to_string(-val / factor);
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public String solveEquation(String equation) {
        int factor = 0, val = 0;
        int index = 0, n = equation.length(), sign1 = 1; // 等式左边默认系数为正
        while (index < n) {
            if (equation.charAt(index) == '=') {
                sign1 = -1; // 等式右边默认系数为负
                index++;
                continue;
            }

            int sign2 = sign1, number = 0;
            boolean valid = false; // 记录 number 是否有效
            if (equation.charAt(index) == '-' || equation.charAt(index) == '+') { // 去掉前面的符号
                sign2 = (equation.charAt(index) == '-') ? -sign1 : sign1;
                index++;
            }
            while (index < n && Character.isDigit(equation.charAt(index))) {
                number = number * 10 + (equation.charAt(index) - '0');
                index++;
                valid = true;
            }

            if (index < n && equation.charAt(index) == 'x') { // 变量
                factor += valid ? sign2 * number : sign2;
                index++;
            } else { // 数值
                val += sign2 * number;
            }
        }

        if (factor == 0) {
            return val == 0 ? "Infinite solutions" : "No solution";
        }
        return "x=" + (-val / factor);
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public class Solution {
    public string SolveEquation(string equation) {
        int factor = 0, val = 0;
        int index = 0, n = equation.Length, sign1 = 1; // 等式左边默认系数为正
        while (index < n) {
            if (equation[index] == '=') {
                sign1 = -1; // 等式右边默认系数为负
                index++;
                continue;
            }

            int sign2 = sign1, number = 0;
            bool valid = false; // 记录 number 是否有效
            if (equation[index] == '-' || equation[index] == '+') { // 去掉前面的符号
                sign2 = (equation[index] == '-') ? -sign1 : sign1;
                index++;
            }
            while (index < n && char.IsDigit(equation[index])) {
                number = number * 10 + (equation[index] - '0');
                index++;
                valid = true;
            }

            if (index < n && equation[index] == 'x') { // 变量
                factor += valid ? sign2 * number : sign2;
                index++;
            } else { // 数值
                val += sign2 * number;
            }
        }

        if (factor == 0) {
            return val == 0 ? "Infinite solutions" : "No solution";
        }
        return "x=" + (-val / factor);
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#define MAX_EXPRESSION_LEN 32

char * solveEquation(char * equation) {
    int factor = 0, val = 0;
    int index = 0, n = strlen(equation), sign1 = 1; // 等式左边默认系数为正
    while (index < n) {
        if (equation[index] == '=') {
            sign1 = -1; // 等式右边默认系数为负
            index++;
            continue;
        }

        int sign2 = sign1, number = 0;
        bool valid = false; // 记录 number 是否有效
        if (equation[index] == '-' || equation[index] == '+') { // 去掉前面的符号
            sign2 = (equation[index] == '-') ? -sign1 : sign1;
            index++;
        }
        while (index < n && isdigit(equation[index])) {
            number = number * 10 + (equation[index] - '0');
            index++;
            valid = true;
        }

        if (index < n && equation[index] == 'x') { // 变量
            factor += valid ? sign2 * number : sign2;
            index++;
        } else { // 数值
            val += sign2 * number;
        }
    }

    if (factor == 0) {
        return val == 0 ? "Infinite solutions" : "No solution";
    }
    char *ans = (char *)malloc(sizeof(char) * MAX_EXPRESSION_LEN);
    sprintf(ans, "x=%d", -val / factor);
    return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
var solveEquation = function(equation) {
    let factor = 0, val = 0;
    let index = 0, n = equation.length, sign1 = 1; // 等式左边默认系数为正
    while (index < n) {
        if (equation[index] === '=') {
            sign1 = -1; // 等式右边默认系数为负
            index++;
            continue;
        }

        let sign2 = sign1, number = 0;
        let valid = false; // 记录 number 是否有效
        if (equation[index] === '-' || equation[index] === '+') { // 去掉前面的符号
            sign2 = (equation[index] === '-') ? -sign1 : sign1;
            index++;
        }
        while (index < n && isDigit(equation[index])) {
            number = number * 10 + (equation[index].charCodeAt() - '0'.charCodeAt());
            index++;
            valid = true;
        }

        if (index < n && equation[index] === 'x') { // 变量
            factor += valid ? sign2 * number : sign2;
            index++;
        } else { // 数值
            val += sign2 * number;
        }
    }

    if (factor === 0) {
        return val === 0 ? "Infinite solutions" : "No solution";
    }
    return "x=" + (-val / factor);
};

const isDigit = (ch) => {
    return parseFloat(ch).toString() === "NaN" ? false : true;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
func solveEquation(equation string) string {
    factor, val := 0, 0
    i, n, sign := 0, len(equation), 1 // 等式左边默认系数为正
    for i < n {
        if equation[i] == '=' {
            sign = -1 // 等式右边默认系数为负
            i++
            continue
        }

        s := sign
        if equation[i] == '+' { // 去掉前面的符号
            i++
        } else if equation[i] == '-' {
            s = -s
            i++
        }

        num, valid := 0, false
        for i < n && unicode.IsDigit(rune(equation[i])) {
            valid = true
            num = num*10 + int(equation[i]-'0')
            i++
        }

        if i < n && equation[i] == 'x' { // 变量
            if valid {
                s *= num
            }
            factor += s
            i++
        } else { // 数值
            val += s * num
        }
    }

    if factor == 0 {
        if val == 0 {
            return "Infinite solutions"
        }
        return "No solution"
    }
    return "x=" + strconv.Itoa(-val/factor)
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 equation 的长度。

  • 空间复杂度：O(1)。

 Comments
On this page
0640-求解方程