【C++笔试强训】如何成为算法糕手Day2
学习编程就得循环渐进，扎实基础，勿在浮沙筑高台
循环渐进Forward-CSDN博客
目录
循环渐进Forward-CSDN博客
第一题：牛牛的快递
第二题：最小花费爬楼梯
第三题：数组中两个字符串的最小距离
补充0x3f3f3f3f
第一题：牛牛的快递
牛客网做题链接：牛牛的快递_牛客题霸_牛客网 (nowcoder.com)
思路：
读题可知总共有四种解决方式
(1)快递不加急且小于20kg;
(2)快递加急且小于20kg;
(3)快递不加急且大于20kg;
(4)快递加急且大于20kg;
#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;
}
第二题：最小花费爬楼梯
牛客网做题链接：最小花费爬楼梯_牛客题霸_牛客网 (nowcoder.com)
这道题目是一个典型的动态规划问题。解决这类问题通常采用从后向前的思考方式。考虑到每次可以选择跳一级或者两级台阶，因此到达最后一个台阶的最小花费，取决于从倒数第二个台阶或倒数第三个台阶到达所需的最小花费。我们只需要计算这两种情况下的最小值，就可以得到到达最后一个台阶的总花费。按照这种逻辑，从后向前推算，每一级台阶的最小花费都可以通过这种方式得出。我们可以使用一个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];
}
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;
}
第三题：数组中两个字符串的最小距离
牛客网做题链接：数组中两个字符串的最小距离__牛客网 (nowcoder.com)
-
初始化变量：
-
pre1和pre2初始化为-1，表示尚未找到字符串1和字符串2。 -
ret初始化为一个非常大的数，用于记录两个字符串之间的最小距离。
-
-
遍历数组：
-
在一次遍历中，检查当前元素是否为字符串1或字符串2。
-
如果找到字符串1：
-
如果
pre2已经指向字符串2，计算当前pre1和pre2之间的距离，并更新ret为最小值。 -
更新
pre1为当前索引。
-
-
如果找到字符串2：
-
如果
pre1已经指向字符串1，计算当前pre1和pre2之间的距离，并更新ret为最小值。 -
更新
pre2为当前索引。
-
-
-
算法的正确性：
-
当
pre1首次找到字符串1后，继续遍历直到pre2找到字符串2，此时计算的距离是最小的，因为后续的字符串2距离pre1都会更远。 -
如果在
pre1和pre2之间还有更优的字符串1位置，那么在pre2找到字符串2之后，继续遍历会找到这个更优的位置，并更新最小距离。
-
这个贪心算法之所以有效，是因为它在每次找到字符串1或字符串2时，都会尝试计算并更新最小距离，而不是等到遍历结束后再计算。这种方法确保了每次更新都是基于当前找到的最优解，从而避免了不必要的重复计算，降低了时间复杂度。
#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;
}
补充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 是标准库定义的，具有明确的含义，并且与整数类型的最大值直接相关。
学习编程就得循环渐进，扎实基础，勿在浮沙筑高台