笔试刷题专题（一）

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

题目链接

题解

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;
}