[数据结构与算法][leetcode]2019. 解出数学表达式的学生分数

周赛260补题

2019. 解出数学表达式的学生分数

给你一个字符串 s ，它 只 包含数字 0-9 ，加法运算符 '+' 和乘法运算符 '*' ，这个字符串表示一个 合法 的只含有 个位数****数字 的数学表达式（比方说 3+5*2）。有 n 位小学生将计算这个数学表达式，并遵循如下 运算顺序 ：

1. 按照 从左到右 的顺序计算 乘法 ，然后
2. 按照 从左到右 的顺序计算 加法 。

给你一个长度为 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 <= 104
• 0 <= answers[i] <= 1000

class Solution {
public:
    int scoreOfStudents(string s, vector<int>& answers) {
        int realAns = 0, n = s.size();
        unordered_map<int, int> score;
        stack<int> stk;
        for(int i = 0; i < n; ++ i){
            if(stk.empty() == true || s[i] == '+' || s[i] == '*'){
                stk.push(s[i]);
            }else{
                if(stk.top() == '*'){
                    stk.pop();
                    int a = stk.top() - '0';
                    stk.pop();
                    stk.push(a * (s[i] - '0') + '0');
                }else{
                    stk.push(s[i]);
                }
            }
        }
        while(stk.empty() == false){
            if(stk.top() != '+'){
                realAns += (stk.top() - '0');
            }
            stk.pop();
        }
        vector<vector<set<int>>> vvs(n, vector<set<int>>(n, set<int>()));
        for(int i = 0; i < n; i += 2){
            for(int j = 0; j + i < n; j += 2){
                if(i == 0){
                    vvs[j][j].insert(s[j] - '0');
                }else{
                    for(int l = j + 1; l <= j + i - 1; l += 2){
                        if(s[l] == '+'){
                            for(auto a : vvs[j][l - 1]){
                                for(auto b : vvs[l + 1][j + i]){
                                    if(a + b <= 1000)vvs[j][j + i].insert(a + b);
                                }
                            }
                        }else{
                            for(auto a : vvs[j][l - 1]){
                                for(auto b : vvs[l + 1][j + i]){
                                    if(a * b <= 1000)vvs[j][j + i].insert(a * b);
                                }
                            }
                        }
                    }
                }
            }
        }
        for(auto a : vvs[0][n - 1]){
            score[a] = 2;
        }
        score[realAns] = 5;
        int ans = 0;
        for(auto a : answers){
            if(score.find(a) != score.end())ans += score[a];
        }
        return ans;
    }
};

算法思路

题目要求所有学生的得分总和，可以用一个unordered_map存储每个结果可以得到的分数。正确的结果得5分，其它运算顺序错的结果得2分。正确的结果可以用一个栈算，如果遇到乘法可以直接乘，然后把结果丢进栈里，最后计算栈里所有元素的和即为正确结果。运算顺序错得到的结果的集合就比较难了，这里用到的是区间dp，有点类似于dp的经典问题矩阵连乘。dp[i][j]表示表达式中第i到j这段子串可以得到的所有结果，该子串的结果又是由该子串的两部分组成，举个例子，C是s的子串且可计算的，即首尾都是数字，A和B是C的两个子串，则C的结果由dp(A) op dp(B)得到，op为+或为*，从长度为1的子串开始往上计算，最后就能计算到整个字符串能得到的所有结果。值得注意的是提示条件里的0 <= answers[i] <= 1000，这就意味这集合中大于1000的可以忽略，因此集合在插入时要进行剪枝。

B)得到，op为+或为*，从长度为1的子串开始往上计算，最后就能计算到整个字符串能得到的所有结果。值得注意的是提示条件里的0 <= answers[i] <= 1000`，这就意味这集合中大于1000的可以忽略，因此集合在插入时要进行剪枝。