解出数学表达式的学生分数
难度:
标签:
题目描述
给你一个字符串 s ，它 只 包含数字 0-9 ，加法运算符 '+' 和乘法运算符 '*' ，这个字符串表示一个 合法 的只含有 个位数数字 的数学表达式（比方说 3+5*2）。有 n 位小学生将计算这个数学表达式，并遵循如下 运算顺序 ：
- 按照 从左到右 的顺序计算 乘法 ，然后
- 按照 从左到右 的顺序计算 加法 。
给你一个长度为 n 的整数数组 answers ，表示每位学生提交的答案。你的任务是给 answer 数组按照如下 规则 打分：
- 如果一位学生的答案 等于 表达式的正确结果，这位学生将得到
5分。 - 否则，如果答案由 一处或多处错误的运算顺序 计算得到，那么这位学生能得到
2分。 - 否则，这位学生将得到
0分。
请你返回所有学生的分数和。
示例 1：
输入：s = "7+3*1*2", answers = [20,13,42] 输出：7 解释：如上图所示，正确答案为 13 ，因此有一位学生得分为 5 分：[20,13,42] 。 一位学生可能通过错误的运算顺序得到结果 20 ：7+3=10，10*1=10，10*2=20 。所以这位学生得分为 2 分：[20,13,42] 。 所有学生得分分别为：[2,5,0] 。所有得分之和为 2+5+0=7 。
示例 2：
输入：s = "3+5*2", answers = [13,0,10,13,13,16,16] 输出：19 解释：表达式的正确结果为 13 ，所以有 3 位学生得到 5 分：[13,0,10,13,13,16,16] 。 学生可能通过错误的运算顺序得到结果 16 ：3+5=8，8*2=16 。所以两位学生得到 2 分：[13,0,10,13,13,16,16] 。 所有学生得分分别为：[5,0,0,5,5,2,2] 。所有得分之和为 5+0+0+5+5+2+2=19 。
示例 3：
输入：s = "6+0*1", answers = [12,9,6,4,8,6] 输出：10 解释：表达式的正确结果为 6 。 如果一位学生通过错误的运算顺序计算该表达式，结果仍为 6 。 根据打分规则，运算顺序错误的学生也将得到 5 分（因为他们仍然得到了正确的结果），而不是 2 分。 所有学生得分分别为：[0,0,5,0,0,5] 。所有得分之和为 10 分。
提示：
3 <= s.length <= 31s表示一个只包含0-9，'+'和'*'的合法表达式。- 表达式中所有整数运算数字都在闭区间
[0, 9]以内。 1 <=数学表达式中所有运算符数目（'+'和'*'）<= 15- 测试数据保证正确表达式结果在范围
[0, 1000]以内。 n == answers.length1 <= n <= 1040 <= answers[i] <= 1000
代码结果
运行时间: 700 ms, 内存: 26.0 MB
/*
* 思路：
* 使用Java Stream来处理学生的答案集合，计算正确答案并对每个学生的答案打分。
*/
import java.util.Arrays;
public class SolutionStream {
public int scoreOfStudents(String s, int[] answers) {
int correctResult = evaluate(s);
return Arrays.stream(answers).map(answer -> {
if (answer == correctResult) return 5;
else if (canGetByWrongOrder(s, answer)) return 2;
else return 0;
}).sum();
}
private int evaluate(String s) {
int sum = 0, mul = 1;
char lastOperator = '+';
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int num = c - '0';
if (lastOperator == '+') {
sum += mul;
mul = num;
} else {
mul *= num;
}
} else {
lastOperator = c;
}
}
sum += mul;
return sum;
}
private boolean canGetByWrongOrder(String s, int target) {
return Arrays.asList(evaluateAllPossible(s)).contains(target);
}
private Integer[] evaluateAllPossible(String s) {
// Simplified approach to get all possible results (similar to the dfs method)
// This needs to be implemented properly to match all possible orderings
return new Integer[]{/* possible results */};
}
}解释
方法:
题解首先通过使用栈来计算表达式的正确结果，遵循给定的运算顺序：先从左到右完成所有的乘法，然后再完成所有的加法。接着，使用深度优先搜索（DFS）和记忆化技术，计算可能通过错误的运算顺序得到的所有结果，并将这些结果存储在集合中。最后，根据答案数组和这两个结果来为学生打分。
时间复杂度:
O(3^15 + m)
空间复杂度:
O(1001)
代码细节讲解
🦆
在解题的`DFS函数`中，你是如何确定在哪个位置进行递归分割的？
▷🦆
为什么在进行乘法运算时，你选择将结果限制在1000以内？是否存在表达式超出这个范围的可能性？
▷🦆
在计算过程中，你是如何处理字符串中的数字和运算符的？具体是如何区分并操作这些字符的？
▷🦆
题解中提到使用`记忆化技术`，具体是如何实现的？这种方法在本题中的作用是什么？
▷