笔试刷题专题（一）

最小花费爬楼梯（动态规划）

题目链接

题解

1. 状态表示：以i位置为结尾的最小花费
2. 状态转移方程：
dp[i] = min(dp[i-1] + cost[i-1,dp[i-2] + cost[i-2])
可以从 i-1 位置和 i-2 到达 i 位置
注意 dp[i] 表示的是 i 位置之前的最小花费，还要加上该点的位置才是到达这个点的最小花费
注意楼顶的位置是n下标的位置
3.从左往右开始填表
4. 初始化：dp[0] = dp[1] = 0，因为从0或者1位置开始向后走，之前是没有花费的

代码

class Solution 
{
public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> dp(n+1);// 初始化// 1.到达dp[i]这个位置的值是不用算进去的// 从这个位置起跳后才把这个位置的值加入到dp表中// 2.楼顶是在下标为n的位置dp[0] = dp[1] = 0;for(int i = 2;i <= n;i++){// 填表dp[i] = min(dp[i-1] + cost[i-1],dp[i-2] + cost[i-2]);}return dp[n];}
};

数组中两个字符串的最小距离（贪心（dp））

题目链接

题解

1. 第二种解法是：
使用两个额外的变量来记录两个字符串的下标，每遇到其中一个字符串就去这个字符串的前面找另一个字符串，记录两个字符串之间的最小距离，记得找完后要更新下标
2. 这样不用暴力地固定一个字符串找另一个字符串了，时间复杂度优化为了O(N)

代码

#include <iostream>
#include<string>
using namespace std;int n;
int main() 
{  cin >> n;string s1,s2;cin >> s1 >> s2;int ans = 0x3f3f3f3f;// 最大的数int prev1 = -1,prev2 = -1;for(int i = 0;i < n;i++){string s;cin >> s;if(s1 == s){if(prev2 != -1){ans = min(ans,i - prev2);}prev1 = i;}else if(s2 == s){if(prev1 != -1){ans = min(ans,i - prev1);}prev2 = i;}}if(ans == 0x3f3f3f3f) cout << -1 << '\n';else cout << ans << '\n'; return 0;
}

点击消除

题目链接

题解

1. 这题和括号匹配是类似的，都是两两消除
2. 可以使用栈或者用一个string来模拟栈
3. 如果是使用栈的话，把栈中的元素取出来放入string中，最后需要逆置一下
4. 用字符串模拟栈，如果栈是空的，就加入st字符串的尾部，如果栈非空并且st尾部的元素和字符串中的元素相同就出栈，如果栈非空并且st尾部的元素和字符串的元素不同就入栈，模拟是不需要逆置的

代码

栈
#include<vector>
#include<string>
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;int main()
{string s;cin >> s;int n = s.size();stack<char> sk;for (int i = 0; i < n; i++){if (sk.empty()) sk.push(s[i]);else{if (sk.top() == s[i]){sk.pop();}else sk.push(s[i]);}}string t;if (sk.empty()) cout << 0 << '\n';else{while (!sk.empty()){char ch = sk.top();t.push_back(ch);sk.pop();}reverse(t.begin(), t.end());cout << t << '\n';}return 0;
}用字符串模拟栈
#include <iostream>
#include<string>
using namespace std;int main() 
{string s,st;cin >> s;for(auto ch : s){if(st.size() && st.back() == ch) st.pop_back();else st += ch;}int k = st.size();if(k == 0) cout << 0 << '\n';else cout << st << '\n';return 0;
}