题目链接
思路
使用区间 的方法，使用一个二维数组
表示字符串
总共可以通过调换计算顺序，得到哪些计算结果
Step 1：统计回答
思路
因为错误的计算结果可能有很多种，所以我们先对所有学生提交的结果做一个简单统计，后续就不需要每次都 遍历了。
代码及注释
// 所有学生答案都在[0, 1000]，因此开一个差不多大小的空间即可
vector<int> count(1024);
for(auto p : answer){
count[p]++;
}
Step 2：计算正确结果
思路
使用加法入栈，乘法直接将栈顶元素做乘法的方法，计算正确结果。
解释
顺序遍历时
- 对于
a + b ...，由于不知道b之后是否涉及到乘法运算，因此不可以直接将a与b相加，而是应该暂时把两个数都放在栈中； - 对于
a * b ...，乘法运算优先级最高，因此此处直接计算a * b的值，并更新栈顶的a的值为a * b
代码及注释
stack<int> st;
st.push(s[0] - '0'); // 第一个元素入栈
for(int i = 1; i < s.length(); i += 2){
if(s[i] == '+'){ // 加法运算，暂不做，存到栈顶
st.push(s[i + 1] - '0');
}
else{ // 乘法运算，直接做
st.top() *= (s[i + 1] - '0');
}
}
// 弹栈，计算所有加法运算
int right = 0;
while(st.size() > 0){
right += st.top();
st.pop();
}
// 正确的得分 = 5 * 正确人数
int ans = 5 * count[right];
Step 3：枚举所有可能结果
思路
这一步中，使用区间 的方法，使用一个二维数组
表示字符串
总共可以通过调换计算顺序，得到哪些计算结果，
是一个集合。
初始化
初始条件时，是 ，此时
递推关系
对于一个区间 ，我们有
其中
，符号
○ 表示加号或乘号关系。
代码及注释
// 开空间，dp为n*n的数组，每一项为一个集合
int len = s.length();
vector<vector<unordered_set<int>>> dp(len + 2, vector<unordered_set<int>>(len + 2));
// 初始化，对于i=j情况，能组成的值为其本身
for(int j = 0; j < len; j += 2){
dp[j][j].insert(s[j] - '0');
}
// 枚举步伐，不断增大，即 step = j-i
for(int step = 2; step < len; step += 2){
// 枚举开始位置 i
for(int i = 0; i + step < len; i += 2){
// 枚举左半部分长度 t
for(int t = 0; t < step; t += 2){
// x是左半部分所有可能值
// y是右半部分所有可能值
for(auto x : dp[i][i + t]){
for(auto y : dp[i + t + 2][i + step]){
// 根据中间连接符是+/*，来计算连接后的值
if(s[i + t + 1] == '+'){
// 因为学生猜测结果均在 [0,1000]，因此超限的值可以直接忽略。
if(x + y <= 1000)
dp[i][i + step].insert(x + y);
}
else{
if(x * y <= 1000)
dp[i][i + step].insert(x * y);
}
}
}
}
}
}
Step 4：统计所有错误结果
思路
上一步计算的 dp[0][len-1] 就是整个字符串，所有可能的计算结果。结合第一步统计的学生答案，做累加
代码及注释
for(auto p : dp[0][len - 1]){
if(p != right){ // 只有错误答案需要统计，防止二次统计正确同学
ans += 2 * count[p];
}
}
完整代码及注释
class Solution {
public:
int scoreOfStudents(string s, vector<int>& answers) {
// Step 1：统计所有学生答案
// 所有学生答案都在[0, 1000]，因此开一个差不多大小的空间即可
vector<int> count(1024);
for(auto p : answers){
count[p]++;
}
// Step 2：计算正确结果
stack<int> st;
st.push(s[0] - '0'); // 第一个元素入栈
for(int i = 1; i < s.length(); i += 2){
if(s[i] == '+'){ // 加法运算，暂不做，存到栈顶
st.push(s[i + 1] - '0');
}
else{ // 乘法运算，直接做
st.top() *= (s[i + 1] - '0');
}
}
// 弹栈，计算所有加法运算
int right = 0;
while(st.size() > 0){
right += st.top();
st.pop();
}
// 正确的得分 = 5 * 正确人数
int ans = 5 * count[right];
// Step 3：枚举所有可能结果
// 开空间，dp为n*n的数组，每一项为一个集合
int len = s.length();
vector<vector<unordered_set<int>>> dp(len + 2, vector<unordered_set<int>>(len + 2));
// 初始化，对于i=j情况，能组成的值为其本身
for(int j = 0; j < len; j += 2){
dp[j][j].insert(s[j] - '0');
}
// 枚举步伐，不断增大，即 step = j-i
for(int step = 2; step < len; step += 2){
// 枚举开始位置 i
for(int i = 0; i + step < len; i += 2){
// 枚举左半部分长度 t
for(int t = 0; t < step; t += 2){
// x是左半部分所有可能值
// y是右半部分所有可能值
for(auto x : dp[i][i + t]){
for(auto y : dp[i + t + 2][i + step]){
// 根据中间连接符是+/*，来计算连接后的值
if(s[i + t + 1] == '+'){
// 因为学生猜测结果均在 [0,1000]，因此超限的值可以直接忽略。
if(x + y <= 1000)
dp[i][i + step].insert(x + y);
}
else{
if(x * y <= 1000)
dp[i][i + step].insert(x * y);
}
}
}
}
}
}
// Step 4：统计顺序错误同学得分
for(auto p : dp[0][len - 1]){
if(p != right){ // 只有错误答案需要统计，防止二次统计正确同学
ans += 2 * count[p];
}
}
return ans;
}
};
网友评论