Hard

题目描述

给你一个字符串 s，它只包含数字 0-9、加号 '+' 和乘号 '*' ，表示一个有效的单位数字数学表达式（例如 3+5*2）。这个表达式给了 n 个小学生。学生们被要求按照以下运算顺序来计算表达式的答案：

  1. 计算乘法，从左到右；然后
  2. 计算加法，从左到右。

给你一个长度为 n 的整数数组 answers，表示学生们提交的答案（顺序不定）。你需要按照以下规则为答案评分：

  • 如果答案等于表达式的正确答案，该学生得 5 分；
  • 否则，如果答案可以解释为学生以错误的运算顺序应用运算符但算术正确，该学生得 2 分；
  • 否则，该学生得 0 分。

返回学生们的总分数。

示例 1:

输入: s = "7+3*1*2", answers = [20,13,42]
输出: 7
解释: 表达式的正确答案是 13，因此一个学生得 5 分: [20,13,42]
一个学生可能以这种错误顺序应用运算符: ((7+3)*1)*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，因此三个学生各得 5 分: [13,0,10,13,13,16,16]
一个学生可能以这种错误顺序应用运算符: ((3+5)*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+0)*1，答案也是 6。
根据评分规则，学生们仍将得到 5 分（因为他们得到了正确答案），而不是 2 分。
学生们的分数是: [0,0,5,0,0,5]。总分数是 10。

约束条件:

  • 3 <= s.length <= 31
  • s 表示一个有效表达式，只包含数字 0-9、’+’ 和 ‘*’
  • 表达式中的所有整数操作数都在 [0, 9] 范围内
  • 1 <= 数学表达式中所有运算符（’+’ 和 ‘*’）的数量 <= 15
  • 测试数据保证表达式的正确答案在 [0, 1000] 范围内
  • 测试数据保证乘法中间步骤的值不会超过 10^9
  • n == answers.length
  • 1 <= n <= 10^4
  • 0 <= answers[i] <= 1000

解题思路

这道题需要解决两个核心问题：

  1. 计算正确答案：按照先乘后加的运算顺序计算表达式
  2. 生成所有可能的错误答案：考虑所有可能的运算顺序

对于第二个问题，我们可以使用区间动态规划的思想。对于表达式的任意一个区间 [i,j]，我们可以枚举所有可能的分割点 k，将区间分为两部分 [i,k] 和 [k+1,j]，然后根据分割点处的运算符进行计算。

具体算法步骤：

  1. 首先解析表达式，提取数字和运算符
  2. 计算正确答案（先乘后加）
  3. 使用记忆化递归生成所有可能的计算结果
  4. 对于每个学生答案，判断是否为正确答案（5分）、可能的错误答案（2分）或无效答案（0分）

为了优化性能，我们使用记忆化来避免重复计算，并且设置上界（1000）来剪枝无效的计算结果。

代码实现

class Solution {
public:
    int scoreOfStudents(string s, vector<int>& answers) {
        vector<int> nums;
        vector<char> ops;
        
        // 解析表达式
        for (int i = 0; i < s.length(); i++) {
            if (isdigit(s[i])) {
                nums.push_back(s[i] - '0');
            } else {
                ops.push_back(s[i]);
            }
        }
        
        int n = nums.size();
        
        // 计算正确答案
        int correct = nums[0];
        for (int i = 0; i < ops.size(); i++) {
            if (ops[i] == '*') {
                correct *= nums[i + 1];
            } else {
                correct += nums[i + 1];
            }
        }
        
        // 记忆化数组
        vector<vector<set<int>>> memo(n, vector<set<int>>(n));
        
        // 获取所有可能的结果
        set<int> possible = getAllPossible(nums, ops, 0, n - 1, memo);
        
        int score = 0;
        for (int answer : answers) {
            if (answer == correct) {
                score += 5;
            } else if (possible.count(answer)) {
                score += 2;
            }
        }
        
        return score;
    }
    
private:
    set<int> getAllPossible(vector<int>& nums, vector<char>& ops, int left, int right, 
                           vector<vector<set<int>>>& memo) {
        if (!memo[left][right].empty()) {
            return memo[left][right];
        }
        
        if (left == right) {
            memo[left][right].insert(nums[left]);
            return memo[left][right];
        }
        
        set<int> result;
        for (int k = left; k < right; k++) {
            set<int> leftSet = getAllPossible(nums, ops, left, k, memo);
            set<int> rightSet = getAllPossible(nums, ops, k + 1, right, memo);
            
            char op = ops[k];
            for (int leftVal : leftSet) {
                for (int rightVal : rightSet) {
                    int val = (op == '+') ? leftVal + rightVal : leftVal * rightVal;
                    if (val <= 1000) {  // 剪枝
                        result.insert(val);
                    }
                }
            }
        }
        
        memo[left][right] = result;
        return result;
    }
};

class Solution:
    def scoreOfStudents(self, s: str, answers: List[int]) -> int:
        # 解析表达式
        nums = []
        ops = []
        for c in s:
            if c.isdigit():
                nums.append(int(c))
            else:
                ops.append(c)
        
        n = len(nums)
        
        # 计算正确答案
        correct = nums[0]
        for i in range(len(ops)):
            if ops[i] == '*':
                correct *= nums[i + 1]
            else:
                correct += nums[i + 1]
        
        # 记忆化
        memo = {}
        
        def getAllPossible(left, right):
            if (left, right) in memo:
                return memo[(left, right)]
            
            if left == right:
                memo[(left, right)] = {nums[left]}
                return memo[(left, right)]
            
            result = set()
            for k in range(left, right):
                left_set = getAllPossible(left, k)
                right_set = getAllPossible(k + 1, right)
                
                op = ops[k]
                for left_val in left_set:
                    for right_val in right_set:
                        if op == '+':
                            val = left_val + right_val
                        else:
                            val = left_val * right_val
                        if val <= 1000:  # 剪枝
                            result.add(val)
            
            memo[(left, right)] = result
            return result
        
        # 获取所有可能的结果
        possible = getAllPossible(0, n - 1)
        
        score = 0
        for answer in answers:
            if answer == correct:
                score += 5
            elif answer in possible:
                score += 2
        
        return score

public class Solution {
    public int ScoreOfStudents(string s, int[] answers) {
        List<int> nums = new List<int>();
        List<char> ops = new List<char>();
        
        // 解析表达式
        for (int i = 0; i < s.Length; i++) {
            if (char.IsDigit(s[i])) {
                nums.Add(s[i] - '0');
            } else {
                ops.Add(s[i]);
            }
        }
        
        int n = nums.Count;
        
        // 计算正确答案
        int correct = nums[0];
        for (int i = 0; i < ops.Count; i++) {
            if (ops[i] == '*') {
                correct *= nums[i + 1];
            } else {
                correct += nums[i + 1];
            }
        }
        
        // 记忆化
        HashSet<int>[,] memo = new HashSet<int>[n, n];
        
        // 获取所有可能的结果
        HashSet<int> possible = GetAllPossible(nums, ops, 0, n - 1, memo);
        
        int score = 0;
        foreach (int answer in answers) {
            if (answer == correct) {
                score += 5;
            } else if (possible.Contains(answer)) {
                score += 2;
            }
        }
        
        return score;
    }
    
    private HashSet<int> GetAllPossible(List<int> nums, List<char> ops, int left, int right,
                                       HashSet<int>[,] memo) {
        if (memo[left, right] != null) {
            return memo[left, right];
        }
        
        if (left == right) {
            memo[left, right] = new HashSet<int> { nums[left] };
            return memo[left, right];
        }
        
        HashSet<int> result = new HashSet<int>();
        for (int k = left; k < right; k++) {
            HashSet<int> leftSet = GetAllPossible(nums, ops, left, k, memo);
            HashSet<int> rightSet = GetAllPossible(nums, ops, k + 1, right, memo);
            
            char op = ops[k];
            foreach (int leftVal in leftSet) {
                foreach (int rightVal in rightSet) {
                    int val = (op == '+') ? leftVal + rightVal : leftVal * rightVal;
                    if (val <= 1000) {  // 剪枝
                        result.Add(val);
                    }
                }
            }
        }
        
        memo[left, right] = result;
        return result;
    }
}

var scoreOfStudents = function(s, answers) {
    // 解析表达式
    const nums = [];
    const ops = [];
    for (const c of s) {
        if (c >= '0' && c <= '9') {
            nums.push(parseInt(c));
        } else {
            ops.push(c);
        }
    }
    
    const n = nums.length;
    
    // 计算正确答案
    let correct = nums[0];
    for (let i = 0; i < ops.length; i++) {
        if (ops[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n³ × 2^n) 其中 n 是表达式中数字的个数。区间DP需要 O(n³) 的时间，每个子问题可能产生指数级别的结果
空间复杂度O(n² × 2^n) 记忆化存储所有子问题的结果，每个结果集合的大小在最坏情况下是指数级别的

相关题目