刷题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;
}
继续加油！！！
