C++日常刷题积累
- 今日刷题汇总 - day002
- 1、牛牛的快递
- 1.1、题目
- 1.2、思路
- 1.3、程序实现
- 1.4、程序实现(扩展)
- 2、最小花费爬楼梯
- 2.1、题目
- 2.2、思路
- 2.3、程序实现
- 3、数组中两个字符串的最小距离
- 3.1、题目
- 3.2、思路
- 3.3、程序实现
- 3.4、补充0x3f3f3f3f
- 4、题目链接
今日刷题汇总 - day002
1、牛牛的快递
1.1、题目
描述
牛牛正在寄快递，他了解到快递在 1kg 以内的按起步价 20 元计算，超出部分按每 kg 1元计算，不足 1kg 部分按 1kg计算。如果加急的话要额外付五元，请问牛牛总共要支付多少快递费
输入描述：
第一行输入一个单精度浮点数 a 和一个字符 b ，a 表示牛牛要寄的快递的重量，b表示牛牛是否选择加急，‘y’ 表示加急 ，‘n’ 表示不加急。
输出描述：
输出牛牛总共要支付的快递费用
示例1
输入：
1.5 y
输出：
26
1.2、思路
首先，读完题知道，这类题就是要理解题意，实现模拟场景的应用。了解到规则，需要处理快递的重量和是否加急的关系。通过分析，不难得出，以下四种情况：
(1)、快递不加急且小于20kg;
(2)、快递加急且小于20kg;
(3)、快递不加急且大于20kg;
(4)、快递加急且大于20kg;
其中关键在于，快递重量大于20kg时，1元/kg，且不足1kg仍然是1元计算。接下来就是程序实现。
1.3、程序实现
根据题目要求，定义重量a和是否加急b两个变量，并完成输入。注意变量的类型即可。
#include <iostream>
using namespace std;
int main()
{
float a = 0;
char b = 0;
cin >> a >> b;
return 0;
}
接着根据思路中分析出的四种情况编写判断程序，并且定义一个count表示一元钱。
#include <iostream>
using namespace std;
int main()
{
float a = 0;
char b = 0;
int count = 0;
cin >> a >> b;
if(a < 1 && b == 'n')
cout << 20;
else if(a < 1 && b == 'y')
cout << 25;
else if(a>=1 && b == 'n')
{
}
else if(a>=1 && b == 'y')
{
}
return 0;
}
最后，处理快递重量大于20kg时，1元/kg，且不足1kg仍然是1元计算。那么思考得出，既然此时处于情况3和情况4，那么a肯定大于20kg，然后，我们就作减减运算，直到小于0，因为不足1也算一元计算。最后，根据起步价和是否加急，输出总结即可。
#include <iostream>
using namespace std;
int main()
{
float a = 0;
char b = 0;
int count = 0;
cin >> a >> b;
if(a < 1 && b == 'n')
cout << 20;
else if(a < 1 && b == 'y')
cout << 25;
else if(a>=1 && b == 'n')
{
while(--a > 0)
{
count++;
}
cout << 20 + count;
}
else if(a>=1 && b == 'y')
{
while(--a > 0)
{
count++;
}
cout << 20 + count + 5;
}
return 0;
}
1.4、程序实现(扩展)
补充一个更优化的方法：ceil函数，用于向上取整，floor函数向下取整
#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;
/*
double c = a - 1;
if(c-(int)c > 0)
ret += (int)c + 1;
else
ret += (int)c;
*/
//等价
ret += ceil(a);
}
if (b == 'y') ret += 5;
cout << ret << endl;
return 0;
}
2、最小花费爬楼梯
2.1、题目
2.2、思路
首先，读完题，发现是典型的动态规划题型。那么动态规划就会涉及状态表示和状态转移方程。再次分析题目需要理解，cost[i]表示在第i个台阶向上爬，才支付费用，意味着由之前的cost[i-1]或cost[i-2]跳到cost[i]位置时，不需要支付cost[i]的费用，而是支付cost[i-1]或cost[i-2]的费用。，此外，我们可以根据示例分析得出，楼梯顶部是所有台阶的下一个位置，即cost[n].(注意：cost[n-1]是数组的最后一个元素，因为下标从0开始)。明白了题意，接着分析，状态表示和状态转移方程。
状态表示：定义一个dp[i]数组，用来表示到达i位置的最小花费；这里是到达楼顶那么i 就等于n即可。
继续理解，dp[i] 为到达i位置的最小花费，那么刚才理解题目，仅仅到达是不用支付费用的，说明dp[i]的实际费用是cost[i-1]或cost[i-2]位置支付的最小费用，依次类推，cost[i-1]位置的最小费用dp[i-1]的费用来自于cost[i-1-1]或cost[i-1-2]支付的费用，那么推理得出状态转移方程。
状态转移方程：dp[i] = min(dp[i-1] + cost[i-1],dp[i-2],cost[i-2]);为最小费用。
值得注意的是理解了最终的收费dp[n]，那么第一个和第二个台阶的收费就是dp[0] = 0;dp[1] = 0;
也就是说dp[2] = min(cost[0],cost[1])，直接从第三个台阶计算收费即可。
所以接下来，就是程序实现。
2.3、程序实现
首先，按照题目要求，定义变量n，表示数组长度；再定义cost数组；接着定义收费dp数组；
编写输入语句。注意这里直接定义为全局的变量和数组考虑性能和、生命周期和作用域，以及数据范围实数表示满足题目需求。
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int cost[N];
int dp[N];
int main()
{
cin >> n;
for(int i = 0;i < n;i++)
{
cin >> cost[i];
}
return 0;
}
接着，完善状态转移方程即可，直接从第三个台阶计费for(int i = 2; i <= n; i++) ，最后输出dp[n]就是到达楼顶的最小费用。
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int cost[N];
int dp[N];
int main()
{
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;
}
3、数组中两个字符串的最小距离
3.1、题目
3.2、思路
首先，读完题得知，要求一个字符串数组strs其中两个字符串str1和str2下标之间的最小距离。然后，得考虑以下几种情况：
(1)、strs中不存在str1或不存在str2时，输出-1；
(2)、strs中存在str1和str2且str1或str2为空时，输出-1；
(3)、strs中可能存在多个str1和str2，求其中最小的距离。
那么关键就在于怎么处理下标之间的关系。
采用蛮力法就是两层for循环遍历加一个判断，找匹配得下标位置，更新一个中间变量ret存放最小距离即可。但是此时时间复杂度为O(n^2)，超出题目限制了。
那么思考可想到除了利用一个中间变量ret，不断记录和更新最小距离，此外，还需要利用两个变量prev1和prev2记录str1和str2的下标，辅助ret的更新。遍历strs，找到其中一个str1或str2时，再更新str1或str2之前是否有str2或str1，有则更新ret，否则更新当前下标prev1或prev2继续遍历，直到遍历结束得到的ret就是最小距离，接下来，就是程序实现。
3.3、程序实现
按照题目要求，编写输入项。注意按照题目要求的逐行输入。第一行输入n，代表strs长度，第二行输入要找的str1和str2，
第三行输入strs对应的n个字符串元素。
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
string str1, str2;
string strs;
cin >> n;
cin >> str1 >> str2;
for (int i = 0; i < n; i++)
{
cin >> strs;
}
return 0;
}
接下来，我们需要对输入strs中的数组字符串元素进行处理，先定义变量prev1和prev2表示str1下标的位置和str2下标的位置；再进行思路分析出来的情况进行判断。相当于遍历strs，从输入的第一个字符串开始判断，如果strs[0] 等于 str1则更新并纪律str1下标的位置prev1,，同理，如果等于str2，则更新记录str2的下标位置prev2。值得注意的是这里直接可以用C++运算符重载” == “完成字符串的比较，对于C语言得用strcmp.
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
string str1, str2;
string strs;
cin >> n;
cin >> str1 >> str2;
int prev1 = -1, prev2 = -1;
for (int i = 0; i < n; i++)
{
cin >> strs;
if (strs == str1)
{
prev1 = i;
}
else if (strs == str2)
{
prev2 = i;
}
}
return 0;
}
接着，对关键的下标之间的关系，进行处理。思考后这里需要利用一个中间变量ret，不断记录和更新存放最小距离。最好初始化一个不容易相等的数，比如INT_MAX或0x3f3f3f3f，然后，根据prev1和prev2的下标关系，建立最小关系。也就是说，当进入strs==str1时，找最近的prev2的下标位置，与当前位置即strs等于str1的下标位置，即prev1的位置，相减(i - prev2)即可。当strs 等于str2时，同理。
#include <iostream>
#include <string>
#include <climits> // 用于 INT_MAX
using namespace std;
int main() {
int n;
string str1, str2;
string strs;
cin >> n;
cin >> str1 >> str2;
int prev1 = -1, prev2 = -1, ret = INT_MAX ;//0x3f3f3f3f
for (int i = 0; i < n; i++)
{
cin >> strs;
if (strs == str1)
{
// 去前⾯找最近的 str2
if (prev2 != -1)
{
ret = min(ret, i - prev2);
}
prev1 = i;
}
else if (strs == str2)
{
// 去前⾯找 str1
if (prev1 != -1)
{
ret = min(ret, i - prev1);
}
prev2 = i;
}
}
if(ret == INT_MAX ) //说明str1和str2其中一个或两个不存在或为NUlL //0x3f3f3f3f
cout << -1 << endl;
else
cout << ret << endl;
return 0;
}
3.4、补充0x3f3f3f3f
有时候使用的 0x3f3f3f3f 是一个在编程中常见的技巧，尤其是在竞赛编程和算法实现中。这个值是一个十六进制数，转换为十进制后大约是 1061109567，这个值比 int 类型（通常是32位）能表示的最大值（INT_MAX，通常为 2147483647）要小，但足够大，可以用作一个初始的“无穷大”值，在后续的比较中被实际的最小值替换。
使用 0x3f3f3f3f 而不是 INT_MAX 的原因主要有两个：
1.避免溢出：
在某些情况下，如果你试图将 INT_MAX 与另一个正数相加，结果可能会溢出并变成负数，这可能会破坏你的算法逻辑。而 0x3f3f3f3f足够小，以至于与任何合理的正数相加都不太可能溢出。
2.历史和习惯：
在某些编程社区和竞赛中，使用 0x3f3f3f3f 作为一种习惯或传统。这可能是因为早期的程序员发现这个值在特定情况下很有用，并且这个习惯被后来的程序员所采纳。
然而，在大多数情况下，直接使用 INT_MAX（或 std::numeric_limits::max()，如果你想要更明确的类型依赖）是更安全、更清晰的选择。这是因为 INT_MAX 是标准库定义的，具有明确的含义，并且与整数类型的最大值直接相关。
4、题目链接
牛牛的快递
最小花费爬楼梯
数组中两个字符串的最小距离
