本文涉及知识点
动态规划汇总
字符串 表达式 栈
LeetCode2019 解出数学表达式的学生分数
给你一个字符串 s ,它 只 包含数字 0-9 ,加法运算符 ‘+’ 和乘法运算符 ‘’ ,这个字符串表示一个 合法 的只含有 个位数数字 的数学表达式(比方说 3+5
按照 从左到右 的顺序计算 乘法 ,然后
按照 从左到右 的顺序计算 加法 。
给你一个长度为 n 的整数数组 answers ,表示每位学生提交的答案。你的任务是给 answer 数组按照如下 规则 打分:
如果一位学生的答案 等于 表达式的正确结果,这位学生将得到 5 分。
否则,如果答案由 一处或多处错误的运算顺序 计算得到,那么这位学生能得到 2 分。
否则,这位学生将得到 0 分。
请你返回所有学生的分数和。
示例 1:
输入:s = “7+3
输出:7
解释:如上图所示,正确答案为 13 ,因此有一位学生得分为 5 分:[20,13,42] 。
一位学生可能通过错误的运算顺序得到结果 20 :7+3=10,10
所有学生得分分别为:[2,5,0] 。所有得分之和为 2+5+0=7 。
示例 2:
输入:s = “3+5
输出:19
解释:表达式的正确结果为 13 ,所以有 3 位学生得到 5 分:[13,0,10,13,13,16,16] 。
学生可能通过错误的运算顺序得到结果 16 :3+5=8,8
所有学生得分分别为:[5,0,0,5,5,2,2] 。所有得分之和为 5+0+0+5+5+2+2=19 。
示例 3:
输入:s = “6+0
输出: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
动态规划
num依次记录运算数,op依次记录运算符。利用栈实现一个简单的运算类,来计算正确结果。
利用动态规划来实现计算所有错误运算符的结果。
动态规划的状态表示
dp[len][i]表示num[i,i+len)所有运算顺序正确或错误可能的结果。
动态规划的转移方程
dp[len][i] = 追加
动态规划的初始值
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;
};
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话 |
---|
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。
版权声明:本文为博主作者:闻缺陷则喜何志丹原创文章,版权归属原作者,如果侵权,请联系我们删除!
原文链接:https://blog.csdn.net/he_zhidan/article/details/135954210