备战秋招c++ 【持续更新】

本文主要是介绍备战秋招c++ 【持续更新】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

T1 牛牛的快递

原题链接：牛牛的快递_牛客题霸_牛客网 (nowcoder.com)

题目类型：模拟

审题&确定思路：

1、超过1kg和不足1kg有两种不同收费方案 ---- 起步价问题

2、超出部分不足1kg的按1kg计算 ----- 向上取整

3、向上取整的实现思路

a：使用库函数ceil() //要包含头文件 #inlcude<cmath>

b:强转 + 判断

if(ch - (int)ch > 0) //  eg: (int)1.5 = 1 
//说明需要向上取整

参考代码

#include <iostream>
#include <cmath>
using namespace std;int main() {float a;char b;cin >>a>>b;if(a >1){int ret = ceil(a)-1;cout<<(b == 'y' ? 25+ret : ret+20)<<endl;}else {cout <<(b == 'y' ? 25: 20)<<endl;}return 0;
}

T2最小花费爬楼梯

原题链接：最小花费爬楼梯_牛客题霸_牛客网 (nowcoder.com)

题目类型：dp

审题&确定思路：

1、确定状态表示：dp[i]表示以i位置为结尾，从0或1下标开始到这个位置的最小花费

2、确定状态转移方程：以i位置为结尾进行思考。因为可以选择跳一层或者两层，说明当站在i这层位置的时候，可能是从前一层或者前两层跳上来的。要使得当前i位置的花费最小，则要对比从前一层跳过来的最低花费和从前两层跳过来的最低花费谁更小再加上往上跳对应要支付的花费，就得到当前层最低花费

其中最低花费对应状态表示dp[i]

将上述关系转化为代码

dp[i] = min(dp[i-1] +cost[i-1] ,dp[i-2]+cost[i-2]);

3、确定填表顺序

因为需要用到前两层的dp信息，所以从左往右填表

4、处理边界情况

因为下标从0开始，可以从0也可以从1开始跳，而刚站上这层楼梯时是不需要花费的，往上跳才需要支付这层的花费。所以dp[0]和dp[1]都为0

接着填表从i = 2开始，就不会发生越界问题。

参考代码：

#include <iostream>
#include<vector>
#include<cmath>
using namespace std;int main() {int n;cin>>n;vector<int>cost(n);for(int i = 0;i<n;i++){cin>>cost[i];}vector<int>dp(n+1);dp[0] = 0;dp[1] = 0;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];return 0;}

T3数组中两个字符串的最小距离

原题链接：数组中两个字符串的最小距离__牛客网 (nowcoder.com)

题目类型：贪心、字符串

审题&确定思路：

1、题目说的strs其实是个字符串类型的数组，里面存放的都是字符串

2、暴力解法，先固定一个字符串str1，然后再搜索str2，计算两个字符串间的距离，并与记录的最短距离进行比较

3、优化思路：贪心 ---- 使用一个或多个变量来表示前驱的信息，即预处理信息。（最终达到优化一层循环的效果）

4、优化实现方法：设置两个int变量prev1 和 prev2 分别记录str1和str2最后一次出现的下标。

5、优化效果：可以不用创建字符串数组来记录strs中的字符串，而是直接用一个字符串来模拟当前遍历到的strs字符串数组中的字符串。因为prev1 和 prev2 这两个变量已经记录了信息，strs遍历完的元素不会再次遍历，所以可以省去构建数组的这一步。

参考代码：

#include <iostream>
#include<vector>
#include<cmath>
using namespace std;int main() {//处理输入信息string str1 ,str2;int n;cin >>n>>str1>>str2;//使用一个字符串变量来表示当前遍历到的字符串string s;//设置变量记录前驱信息，优化一层循环//初始化为-1是为了区别str1/str2是否在strs中出现int prev1 = -1,prev2 = -1;//ret 记录两字符串间的最短距离，为不影响最短距离的比较，所以设置个较大值//0x3f3f3f3f是常用数据，可近似看做无限大值int ret = 0x3f3f3f;for(int i = 0;i<n;i++){cin >>s;if(s == str1){prev1 = i;if(prev2 != -1)ret = fmin(ret,abs(prev2 - prev1));}else if(s == str2) //要写出 s == str2 不能直接写else if，因为除了str1和str2，strs中的字符串（即s）还有其他样式的{prev2 = i;if(prev1 != -1)ret = fmin(ret,abs(prev2 - prev1));}}//判断是否str1和str2都在strs中出现了if(ret != 0x3f3f3f){cout << ret<<endl;}else {cout<<-1<<endl;}return 0;}