【动态规划】【字符串】【表达式】2019. 解出数学表达式的学生分数

本文涉及知识点

动态规划汇总

字符串 表达式 栈

LeetCode2019 解出数学表达式的学生分数

给你一个字符串 s ，它 只 包含数字 0-9 ，加法运算符 ‘+’ 和乘法运算符 ‘’ ，这个字符串表示一个 合法 的只含有 个位数数字 的数学表达式（比方说 3+5 ⋆ \star⋆ 2）。有 n 位小学生将计算这个数学表达式，并遵循如下 运算顺序 ：
按照 从左到右 的顺序计算 乘法 ，然后
按照 从左到右 的顺序计算 加法 。
给你一个长度为 n 的整数数组 answers ，表示每位学生提交的答案。你的任务是给 answer 数组按照如下 规则 打分：
如果一位学生的答案 等于 表达式的正确结果，这位学生将得到 5 分。
否则，如果答案由 一处或多处错误的运算顺序 计算得到，那么这位学生能得到 2 分。
否则，这位学生将得到 0 分。
请你返回所有学生的分数和。
示例 1：
输入：s = “7+3⋆ \star⋆ 1⋆ \star⋆ 2”, answers = [20,13,42]
输出：7
解释：如上图所示，正确答案为 13 ，因此有一位学生得分为 5 分：[20,13,42] 。
一位学生可能通过错误的运算顺序得到结果 20 ：7+3=10，10⋆ \star⋆ 1=10，10 ⋆ \star⋆ 2=20 。所以这位学生得分为 2 分：[20,13,42] 。
所有学生得分分别为：[2,5,0] 。所有得分之和为 2+5+0=7 。
示例 2：
输入：s = “3+5 ⋆ \star⋆ 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 ⋆ \star⋆ 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 ⋆ \star⋆ 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

动态规划

num依次记录运算数，op依次记录运算符。利用栈实现一个简单的运算类，来计算正确结果。

利用动态规划来实现计算所有错误运算符的结果。

{ 正确结果为 [ 0 , 1000 ] 加上任意数只会不边或变大 乘以 0 以外的数，只会变大或不变 \begin{cases} 正确结果为[0,1000] \\ 加上任意数只会不边或变大\\ 乘以0以外的数，只会变大或不变\\ \end{cases}⎩⎨⎧正确结果为[0,1000]加上任意数只会不边或变大乘以0以外的数，只会变大或不变 → \rightarrow→ 中间结果>1001和1000完全一样 { 结果相同 乘了 0 大于 a n s w e r s 的最大值 1000 没有乘 0 \begin{cases} 结果相同 & 乘了0 \\ 大于answers的最大值1000 &没有乘0 \\ \end{cases}{结果相同大于answers的最大值1000乘了0没有乘0

动态规划的状态表示

dp[len][i]表示num[i,i+len)所有运算顺序正确或错误可能的结果。

动态规划的转移方程

dp[len][i] = 追加l e n 1 : 1 l e n − 1 _{len1:1}^{len-1}len1:1len−1dp[len1][i] 加（或乘) dp[len-len1][i+len1]

动态规划的初始值

dp[1][i] = num[i]

动态规划的填表顺序

len 从2到大，以确保填表顺序。

i从小到大。

动态规划的返回值

正确结果得5分，dp.back()[0]中的值得2分。

代码

核心代码

class Solution {
public:
  int scoreOfStudents(string s, vector<int>& answers) {
    CExpression exp;
    for (const char& ch : s)
    {
      if (('+' == ch) || ('*' == ch))
      {
        exp.AddOpe(ch);
      }
      else
      {
        exp.AddNum(ch - '0');
      }
    }
    const int iAns = exp.DoAddSub();
    int num[16];
    char ope[15];
    for (int i = 0; i < s.length(); i++)
    {
      if (i & 1)
      {
        ope[i / 2] = s[i];
      }
      else
      {
        num[i / 2] = s[i] - '0';
      }
    }
    int n = (s.length() + 1) / 2;
    vector<vector<unordered_set<int> >> dp(n+1, vector<unordered_set<int>>(n));
    for (int i = 0; i < n; i++)
    {
      dp[1][i].emplace(num[i]);
    }
    for (int len = 2; len <= n; len++)
    {
      for (int i = 0; i + len <= n; i++)
      {
        for (int len1 = 1; len1 < len; len1++)
        {
          for (const auto& n1 : dp[len1][i])
          {
            for (const auto& n2 : dp[len - len1][i + len1])
            {
              const int ret = ('+' == ope[i + len1 - 1]) ? (n1 + n2) : (n1 * n2);
              dp[len][i].emplace((ret>1001)?1001:ret);
            }
          }
        }
      }
    }
    int iRet = 0;
    for (const auto& ans : answers)
    {
      if (iAns == ans)
      {
        iRet += 5;
      }
      else if (dp.back()[0].count(ans))
      {
        iRet += 2;
      }
    }
    return iRet;
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  string s;
  vector<int> answers;
  {
    Solution sln;
    s = "7+3*1*2", answers = { 20, 13, 42 };
    auto res = sln.scoreOfStudents(s,answers);
    Assert(res,7);
  }
  {
    Solution sln;
    s = "3+5*2", answers = { 13, 0, 10, 13, 13, 16, 16 };
    auto res = sln.scoreOfStudents(s, answers);
    Assert(res, 19);
  }
  {
    Solution sln;
    s = "6+0*1", answers = { 12, 9, 6, 4, 8, 6 };
    auto res = sln.scoreOfStudents(s, answers);
    Assert(res, 10);
  }
}

2023年2月版

class Solution {

public:

int scoreOfStudents(string s, vector& answers) {

m_c = s.length();

const int iVilid = GetVilidAns(s);

vector < vector<std::unordered_set>> vLenPosErrAns(m_c + 1, vector<std::unordered_set>(m_c));

for (int len = 1; len <= m_c; len += 2)

{

for (int iPos = 0; iPos+len-1 < m_c; iPos += 2)

{

if (1 == len)

{

vLenPosErrAns[len][iPos].insert(s[iPos] - ‘0’);

continue;

}

for (int leftLen = 1;; leftLen += 2)

{

const int iRightLen = len - 1 - leftLen;

if (iRightLen <= 0)

{

break;

}

CalSet(vLenPosErrAns[len][iPos], vLenPosErrAns[leftLen][iPos], s[iPos + leftLen], vLenPosErrAns[iRightLen][iPos + leftLen + 1]);

}

}

}

int iRet = 0 ;

for (int i = 0; i < answers.size(); i++)

{

if (iVilid == answers[i])

{

iRet += 5;

continue;

}

if (vLenPosErrAns[m_c][0].count(answers[i]))

{

iRet += 2;

}

}

return iRet;

}

void CalSet(std::unordered_set& setResult, const std::unordered_set& set1, char chOpe, const std::unordered_set& set2)

{

for (auto it : set1)

{

for (auto ij : set2)

{

int iResult = it + ij;

if (‘’ == chOpe )
{
iResult = itij;

}

if (iResult <= 1000)

{

setResult.insert(iResult);

}

}

}

}

int GetVilidAns(string s)

{

stack staNum;

stack staOpe;

for (const auto& ch : s)

{

if ((’’ == ch) || (‘+’ == ch))
{
staOpe.push(ch);
}
else
{
staNum.push(ch-‘0’);
if ((staNum.size() >= 2) && staOpe.size()&&(''== staOpe.top()))

{

int t1 = staNum.top();

staNum.pop();

int t2 = staNum.top();

staNum.pop();

staNum.push(t1*t2);

staOpe.pop();

}

}

}

while (staNum.size() >= 2)
   {
     int t1 = staNum.top();
     staNum.pop();
     int t2 = staNum.top();
     staNum.pop();
     staNum.push(t1+t2);
     staOpe.pop();
   }
   return staNum.top();
 }
 int m_c;

};

2023年7月

class Solution {

public:

int scoreOfStudents(string s, vector& answers) {

for (const auto& ch : s)

{

if ((‘+’ == ch) || (‘’ == ch))
{
m_staOpes.emplace(ch);
}
else
{
const int iNum = ch - ‘0’;
if (m_staOpes.size() && ('’ == m_staOpes.top()))

{

const int iPre = m_staNums.top();

m_staNums.pop();

m_staNums.emplace(iPre * iNum);

m_staOpes.pop();

}

else

{

m_staNums.emplace(iNum);

}

}

}

while (m_staOpes.size())

{

int iNext = m_staNums.top();

m_staNums.pop();

const int iPre = m_staNums.top();

m_staNums.pop();

m_staOpes.pop();

m_staNums.emplace(iPre + iNext);

}

m_c = s.length() / 2 + 1;

m_dp.assign(m_c, vector<set>(m_c));

for (int i = 0; i < m_c; i++)

{

m_dp[i][i] .emplace( s[i * 2] - ‘0’);

}

for (int len = 2; len <= m_c; len++)

{

#define END (begin + len - 1)

for (int begin = 0; END < m_c; begin++)

{

for (int mid = begin ; mid < END; mid++)

{

Ope(m_dp[begin][END], m_dp[begin][mid], m_dp[mid + 1][END],s[mid*2+1]);

}

}

}

int iScore = 0;

for (const auto& ans : answers)

{

if (ans == m_staNums.top())

{

iScore += 5;

}

else if (m_dp[0].back().count(ans))

{

iScore += 2;

}

}

return iScore;

}

void Ope(set& res, const set& pre, const set& next,const char& ch )

{

for (const auto& it : pre)

{

for (const auto& ij : next)

{

int iRes = (‘+’ == ch) ? (it + ij) : (it * ij);

if (iRes > 1000)

{

break;

}

res.emplace(iRes);

}

}

if (res.empty())

{

res.emplace(1001);

}

}

stack m_staNums;

stack m_staOpes;

int m_c;

vector<vector<set>> m_dp;

};