2024.7.29 刷题总结

2024.7.29

**每日一题**

682.棒球比赛，这道题是一道简单的模拟题，用栈模拟题中的四个操作就可以了，操作一是将x加到列表末尾，操作二是将列表的后两项之和加到列表末尾，操作三是把列表最后一项的两倍加到列表末尾，操作四是去掉列表最后一项。

class Solution {
public:int calPoints(vector<string>& operations) {vector<int> st;for (auto& op : operations) {switch (op[0]) {case '+':st.push_back(st[st.size() - 2] + st.back());break;case 'D':st.push_back(st.back() * 2);break;case 'C':st.pop_back();break;default:st.push_back(stoi(op));}}return reduce(st.begin(), st.end(), 0);}
};

LCR 100.三角形最小路径和，这道题是一道入门的动态规划题目，当然也可以用dfs来求解。我们只需要用一个数组来记录到达每个点需要的最小路径，然后再把最后一行取一个最小值即可。

class Solution {
public:int minimumTotal(vector<vector<int>>& triangle) {int n = triangle.size();vector<vector<int>> f(n, vector<int>(n));f[0][0] = triangle[0][0];for (int i = 1; i < n; ++i) {f[i][0] = f[i - 1][0] + triangle[i][0];for (int j = 1; j < i; ++j) {f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];}f[i][i] = f[i - 1][i - 1] + triangle[i][i];}return *min_element(f[n - 1].begin(), f[n - 1].end());}
};