感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接
🐒🐒🐒 个人主页
🥸🥸🥸 C语言
🐿️🐿️🐿️ C语言例题
🐣🐣🐣 python
🐓🐓🐓 数据结构C语言
🐔🐔🐔 C++
🐿️🐿️🐿️ 文章链接目录
🏀🏀🏀 笔试练习题

BC64 牛牛的快递

链接BC64 牛牛的快递

题目解析

这道题和出租车那种是一个意思,首先要有一个起步价格,之后多出来的要额外收费,这样看起来就是一个一次函数的方程,y=kx+b+a,k=1是每千克收的钱,x是快递的重量(这里要注意x有小数的话要往整数进1),b=20表示的是起步价,而a就是是否加急的费用,不加急a=0,加急a=5

解法

模拟

我们需要先模拟一下这个过程,假设有akg,对于a来说有两种情况,一种是<=1,另一种是>1

对于<=1这种情况比较简单,>1这种情况是要考虑a-1是否有小数,如果有小数就需要向上取整,比如1.1向上取整就是2
这里的向上取整有两种方法
第一种就是先判断(a-1)-(int)(a-1)是否大于0,如果大于0就再加1
第二种就是用一个函数ceil(a-1),这个函数可以自动向上取整(需要包含头文件cmath)

最后再判断要不要加急

代码

方法1

#include <iostream>
#include<cmath>
using namespace std;int main() {double a;char b;cin >> a >> b;int ret = 0;if (a <= 1) {ret += 20;} else {ret += 20;double c=a-1;if(c-(int)c>0)ret+=int(c)+1;elseret+=c;}if (b == 'y')ret += 5;cout << ret << endl;return 0;
}

方法2

#include <iostream>
#include<cmath>
using namespace std;int main() {double a;char b;cin >> a >> b;int ret = 0;if (a <= 1) {ret += 20;} else {ret += 20;a -= 1;ret += ceil(a);}if (b == 'y')ret += 5;cout << ret << endl;return 0;
}

DP4 最小花费爬楼梯

链接DP4 最小花费爬楼梯

题目解析

为了方便我们将第一个例子用图来表示,假设小人从第-1个台阶开始走(事实上没有第-1个台阶),此时在第-1个台阶开始他只需要支付0元就可以选择爬1个或2个台阶

这里需要注意的一点就是楼顶我们需要判断在哪
根据第一个例子第0层花2元,第一层花5元
如果楼顶在第二层的话,花费最少的方式就是选择第0层开始爬,这样我们就只需花2元就到达第2层(这里是将第2层看作楼顶)
如果楼顶在第三层的话,花费最少的方式就是选择第1层开始爬,这样我们就只需话5元就到底第3层(这里是将第3层看作楼顶)
根据示例我们可以得出结果为5元,所以楼顶应该是在3楼

对于楼顶在第3层我们有如下的几种方式到达
第一种方式0->1->3

第二种方式0->2->3

第三种方式1->3

解法

动态规划

状态表示

我们可以将上面的台阶简化成下面的一个数组,第i个台阶就表示数组第i个元素,现在需要求到第i个元素的最小花费,我们用dp[i]表示

状态转移方程

状态转移方程我们一般从最后一步去划分情况
比如到达i位置时我们可以花费cost[i-1]从i-1位置跳到i位置
也可以划分cost[i-2]从i-2位置跳到i位置

而从i-2到i的总费用就是到达i-2时的最小花费加上cost[i-2],也就是dp[i-2]+cost[i-2]
从i-1到i的总费用就是到达i-1的最小花费加上cost[i-1],也就是dp[i-1]+cost[i-1]
dp[i]就是判断dp[i-1]+cost[i-1]和dp[i-2]+cost[i-2]谁花费的价钱最少
所以dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
从上面的方程可知dp[i]的值需要知道dp[i-1]和dp[i-2]的值,而dp[i-1]和dp[i-2]的值又需要知道他们前面的dp[i-3]…的值,所以我们需要从左向右开始推导
因为dp[2]需要知道dp[0]和dp[1]的值,但是dp[0]和dp[1]不能继续细分dp[-1]…,所以dp[0]和dp[1]我们需要初始化
根据题意我们是可以选择从0或1台阶开始起跳的,也就是说我们到达0台阶和到达1台阶是不需要花钱的
所以dp[0]=dp[1]=0,知道dp[0]和dp[1]后就可以往后推dp[n]了(注意这里的n是楼顶表示的是最后一块台阶的下一个位置)

代码

#include <iostream>
using namespace std;int main() {
int cost[100000],dp[100000]={0};
int n=0;
cin>>n;
for(int i=0;i<n;i++)
{cin>>cost[i];
}
for(int i=2;i<=n;i++)
{
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
cout<<dp[n]<<endl;
return 0;
}

注意这里的min是一个自带的函数,当然也可以自己去实现

数组中两个字符串的最小距离

链接数组中两个字符串的最小距离

题目解析

这道题有点难读懂,我们以示例2为例子
strs是一个字符串数组,字符串数组的每一个元素都是字符串
str1和str2都是一个字符串,他们可能是在字符串数组里的,现在需要我们去在这个字符串数组中找出str1和str2,并且求出他们对应位置的最小值(因为strs里可能含义多个相同的字符串,所以要对他们的距离进行比较,得到最后的值),如果没有找到就返回-1

这个图中str1在strs中出现了两次,一个是在第0个位置,另一个是在第5的一个位置
str2只出现了一次,是在第4的一个位置
他们的距离是|0-4|和|4-5|,也就是4和1,显然最短的距离就是1,所以返回1
这道题也可以换成下面这样
在数组中求出a和b的最小距离

或者在下面字符串求出a和b的最小距离

解法

方法1暴力解法(会超时)

我们还是以示例2为例子
先用一层for循环用一个指针ptr1去找出QWER的位置
然后在这一层for循环里面再嵌套一次for循环用指针ptr2去找666
之后用一个ret去记录他们之间的距离

记录完后再让ptr2往后找是否有是否还有相同的字符串,因为有可能会出现下面这种情况,就是QWER会在第一次的666后面

内部for循环找完后,又回到外部for循环,再让ptr1往后找是否有QWER,找到后又进入内部for循环
这种解法的时间复杂度是O(n^2),会超时,所以这里只是提供一个思路

方法2贪心(动态规划)

这个方法是在方法1的基础上进行了优化

我们还是让ptr1和ptr2分别记录QWER和666的下标,并且因为是数组,所以我们让ptr1和ptr2记录的位置初始化成-1,表示他们还没有开始记录下标

然后我们先让ptr1去找QWER的位置

找到后向左查找最近的一次666出现的位置,如果没有出现那么ptr2就不会变,仍为-1

此时我们还需要注意ptr1记录的下标需要更新,这里的QWER下标为0,所以ptr1记录的值也应该变成0

然后再向右开始遍历,如果右边的QWER比666先出现,那么就先更新ptr1,如果666比QWER先出现,那么就先更新ptr2

这里的666先出现,所以就将ptr2记录的值变成3,然后ret比较一下他们现在的距离和之前的最短距离谁更短
因为之前没有666出现,所以ret是没有最短距离的,因此这里的ret直接就等于3
之后再向右遍历,因为右边只有一个QWER了,所以就让ptr1更新一下

这次的距离是最短的,所以ret更新为1
这个方法的时间复杂度为O(N),只用一次循环就找出了最短距离

代码

#include <iostream>
#include<string>
using namespace std;int main() {int n;string s1, s2;string s;cin >> n;cin >> s1 >> s2;int ptr1 = -1, ptr2 = -1, ret = 0x3f3f3f3f;for (int i = 0; i < n; i++) {cin >> s;if (s == s1) {if (ptr2 != -1) {ret = min(ret, i - ptr2);}ptr1 = i;}else if (s == s2) {if (ptr1 != -1){ret = min(ret, i - ptr1);}ptr2 = i;}}if (ret == 0x3f3f3f3f)cout << -1;elsecout << ret;return 0;
}

这段代码中ret初始化为0x3f3f3f3f表示非常大的一个值,也就是这道题的距离不会有比这个值更大的