刷题day_2
继续坚持!!!
1. 牛牛的快递
题目链接:牛牛的快递
题目解析
- 这道题要求输入一个浮点型数和一个字符(
y
表示加急,n
表示不加急)- 让我们求出来需要支付的费用,(**费用 **:
1千克的起步费用是20
,超过1
千克的每千克一元,不足1千克的按1千克算
;如果加急则需要多支付5
元的费用)- 输出需要支付的费用
算法思路
根据上述题目,我们要求费用,就可以这样来求
- 我们将费用分成三部分,一是
起步价
、二是超出的部分需要支付的费用
、三就是加急的费用
- 这样显而易见,我们只需要求出来超出部分的费用就可以了,而超出部分有一个要求,就是不足
1千克
按1千克
计算;(比如(超出1.3
千克,就要按2千克
算。)这其实就是向上取整。- 求超出部分:这里提供一个函数
ceil
,它可以返回向下取整的结果;在这道题中,1千克费用为1元,直接加上即可。(这里我们也可以不使用这个函数,使用(int)a
,强转就是向下取整,再看一下小数部分(a-(int)a
)是否等于0(如果等于a-(int)a ==0
,加上1即可)。
代码实现
使用ceil
#include<iostream>
#include<cmath>
using namespace std;int main()
{float a;char b;cin>>a>>b;int money = 0;if(a<=1){money = 20;}else {a--;money = 20 + ceil(a);}if(b == 'y')money+=5;cout<< money <<endl;return 0;
}
自己实现向上取整
#include<iostream>
using namespace std;int main()
{float a;char b;cin>>a>>b;int money = 0;if(a<=1){money = 20;}else {a--;if(a-(int)a > 0)money = 20 + (int)a +1;elsemoney = 20 + (int)a;}if(b == 'y')money+=5;cout<< money <<endl;return 0;
}
2. 最小花费上楼梯
题目链接:最小花费上楼梯
题目解析
题目要求:给定一个数组cost
,其表示从这个位置离开需要的花费,(可以选择上一步或者两步);需要我们求出到达顶部的最低花费。
这里我们要理清思路,读懂题,这个顶部指的是
cost[n-1]
还是cost[n]
;这里显而易见的是cost[n]
的位置。
算法思路
第一次看到这个题,可以说是毫无思路,根本无从下手;(如果学习过动态规划算法
这一题可以说是一眼秒了)。
现在来说思路:
题目要求我们求出来到顶部的最小花费,但是这该如何求呢?
我们先来看一下到
i
位置的最小花费,如何到达i
位置?根据题目,可以上一步或者两步
- 到达
i
位置只能从i-1
、i-2
两个位置跳过去,那要求最小花费,就在这两个里面找最小的即可;- 所以到
i
位置的最小距离,就等于(从i-1位置跳过去的花费
+到达 i - 1 位置的最小花费
) 和(从i - 2 位置跳过去的花费
+到达i - 2 位置的最小花费
)中最小的。- 那到达
i-1
和i-2
位置的最小花费该如何求呢?- 很简单,继续向下分解就好了;直到求到达第
2
个位置的最小花费;我们可以选择选择0
和1
开始,所以到达2
个位置的话费就等于0
和1
跳过去的花费中最小的。
代码实现
#include <iostream>
using namespace std;const int N = 1e5 + 10;
//这里可以进行空间优化一下,使用vector定义在局部函数内。
int dp[N];
int cost[N];int min(int x,int y)
{if(x<y)return x;elsereturn y;
}
int main() {int n;cin>>n;for(int i=0;i<n;i++){cin>>cost[i];}//这里定义的是全局变量数组,数组默认补充的就是0;for(int i=2;i<=n;i++){dp[i] = min(dp[i-1]+cost[i-1], dp[i-2] + cost[i-2]);}//直接输出n位置dp[n],就是到达n位置的最小花费cout<<dp[n]<<endl;return 0;
}
3. 数组中两个字符串的最小距离
题目链接:数组中两个字符串的最小距离__牛客网
题目解析
题目要求,给定两个字符串str1
和str2
,然后在给定的字符数组strs
中查找两个字符串的最小距离,如果str1
和str2
为NULL
或者不在strs
中就返回-1
。
题目看起来很简单,直接来看如何实现。
算法思路
暴力解法
暴力解法,两层循环,遍历整个
strs
数组,将所以的情况都列举出来。这里时间复杂度就是O(n^2)
。对暴力解法优化一下:
(这也是博主做题时想到的思路)
。
- 遍历
strs
,将str1
出现的下标和str2
出现的下标分别存到数组v1
和v2
当中- 遍历数组
v1
和v2
,找到距离最小的。这里看一下最坏情况,就是
strs
中一半是str1
,一半是str2
;这种情况下时间复杂度O(1/4 n^2)
,时间复杂度也是O(n^2)
。
但是题目要求时间复杂度为O(n)
,还能显然暴力解法是解决不掉问题的。
优化解法
这里如果了解过贪心算法,可能就比较容易了;(博主还没学到,这里就一起来看一下如何优化
)。
对于数组
strs
,我们可以从左往右来遍历它,然后只需要在遇到str1
(str2
)时注意前面最近的str2
(str1
)就行了。
这里可能有疑惑,那右边的就不需要管了吗?
这里是不需要的,因为我们从左往右遍历数组
strs
,当我们遍历到右边时就会注意到前面的了。
什么意思呢?
简单来说就是,如果我们左右两边同时关注,那在遍历到右面时就会再次计算一次重复的情况,这里没必要。
这里以示例2为例看一下
现在来说整个遍历的过程
首先定义变量
prev1
、prev2
和ret
(prev1
表示str1
最近的下标(遍历时离i
最近的),prev2
表示str2
最近的下标,ret
表示最终的结果)
- 遍历
strs
,遇到str1
,判断prev2
是否等于-1
(等于-1
表示前面没有出现过str2
),如果不等于-1
就更新ret
;更新prev1
。- 遇到
str2
,判断prev1
是否等于-1
(等于-1
表示前面没有出现过str1
),如果不等于就更新ret
;更新prev2
。
代码实现
在上述遍历过程中,我们可以看到
strs
中每一个字符串都只遍历了一次,所以这就可以不使用字符数组,直接边输入边更新结果即可。
#include<iostream>
#include<string>
using namespace std;
int min(int x,int y)
{if(x<=y) return x;else return y;
}
int main() {int n;string str1, str2;string s;cin >> n >> str1 >> str2;if (str1.empty() || str2.empty()) {cout << -1 << endl;return 0;}//ret定义一个非常大是数即可//这里定义成n+1,比数据个数大1,如果遍历结束以后ret还是n+1,就说明str1和str2至少有一个在strs中不存在。int prev1 = -1, prev2 = -1;int ret = n + 1;for (int i = 0; i < n; i++) {cin>>s;if (s == str1) { //遇到str1if (prev2 != -1) ret = min(ret, i - prev2); //更新retprev1 = i; //更新prev1} else if (s == str2) { //遇到str2if (prev1 != -1) ret = min(ret, i - prev1); //更新retprev2 = i; //更新prev1}}if(ret == n+1) cout<<-1<<endl;else cout<<ret<<endl;return 0;
}
继续加油!!!