当前位置: 首页 > article >正文

笔试刷题专题(一)

文章目录

  • 最小花费爬楼梯(动态规划)
    • 题解
    • 代码
  • 数组中两个字符串的最小距离(贪心(dp))
    • 题解
    • 代码
  • 点击消除
    • 题解
    • 代码

最小花费爬楼梯(动态规划)

题目链接
在这里插入图片描述

题解

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


http://www.kler.cn/a/585990.html

相关文章:

  • 《MySQL数据库从零搭建到高效管理|表的增删改查(基础)》
  • STM32与HAL库开发实战:深入探索ESP8266的多种工作模式
  • 46. HarmonyOS NEXT 登录模块开发教程(一):模态窗口登录概述
  • Flask使用Blueprint注册管理路由
  • 搭建基于chatgpt的问答系统
  • Python 推导式详解
  • MySQL学习笔记(4)三大日志
  • 基于Matlab设计GUI图像处理交互界面
  • 计算机网络基础:网络安全基础
  • python-leetcode-删掉一个元素以后全为 1 的最长子数组
  • 将docker images导入crictl images
  • 基于腾讯云高性能HAI-CPU的跨境电商客服助手全链路解析
  • uniapp页面跳转带参数获取,需要注意在小程序和web下是不一样的
  • 网络爬虫相关
  • DeepLabv3+改进10:在主干网络中添加LSKBlock|动态调整其大型空间感受野,助力小目标识别
  • element-plus中Autocomplete自动补全输入框组件的使用
  • 硬件工程师入门教程(四)
  • linux ptrace 图文详解(二) PTRACE_TRACEME 跟踪程序
  • 解决Docker Desktop中ext4.vhdx文件过大的问题
  • 【Java 进阶实战】一 学习成果检验