【C++笔试强训】如何成为算法糕手Day2

小文要打代码

发布于 2024-10-16 15:22:45

950

发布于 2024-10-16 15:22:45

文章被收录于专栏：C++学习历程

第一题：牛牛的快递

牛客网做题链接：牛牛的快递_牛客题霸_牛客网 (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 是标准库定义的，具有明确的含义，并且与整数类型的最大值直接相关。

学习编程就得循环渐进，扎实基础，勿在浮沙筑高台

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-15，如有侵权请联系 cloudcommunity@tencent.com 删除

数组