2019：解出数学表达式的学生分数（2583 分）

2021-09-26 约 1056 字预计阅读 3 分钟次阅读

力扣第 260 场周赛第 4 题

题目

给你一个字符串 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 <= 31
s 表示一个只包含 0-9 ，'+' 和 '*' 的合法表达式。
表达式中所有整数运算数字都在闭区间 [0, 9] 以内。
1 <= 数学表达式中所有运算符数目（'+' 和 '*'） <= 15
测试数据保证正确表达式结果在范围 [0, 1000] 以内。
n == answers.length
1 <= n <= 10⁴
0 <= answers[i] <= 1000

相似问题：

分析

枚举最后运算的运算符位置 k，转为 [0,k-1] 和 [k+1,n-1] 的递归子问题
令 f(i,j) 代表 s[i:j+1] 能得到的所有结果，递归即可
注意题目保证正确结果和学生答案都<=1000，因此 f(i,j) 只保留<=1000 的值，保证不超时

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        ans = eval(s)
        n = len(s)
        f = [[set() for _ in range(n)] for _ in range(n)]
        for i in range(n-1,-1,-2):
            f[i][i] = {int(s[i])}
            for j in range(i+2,n,2):
                for k in range(i+1,j,2):
                    for a,b in product(f[i][k-1],f[k+1][j]):
                        c = a+b if s[k]=='+' else a*b
                        if c<=1000:
                            f[i][j].add(c)
        return sum(5 if x==ans else 2 for x in answers if x in f[0][-1])

914 ms

目录

2019：解出数学表达式的学生分数（2583 分）

题目

分析

解答