当前位置: 首页> 科技> 能源 > 北京公司车牌指标_如何设计个人网站_快速排名程序_关键词自动优化工具

北京公司车牌指标_如何设计个人网站_快速排名程序_关键词自动优化工具

时间:2025/7/11 8:25:59来源:https://blog.csdn.net/LH__1314/article/details/146179409 浏览次数:1次
北京公司车牌指标_如何设计个人网站_快速排名程序_关键词自动优化工具

刷题day_2

继续坚持!!!

1. 牛牛的快递

题目链接:牛牛的快递在这里插入图片描述

题目解析

  • 这道题要求输入一个浮点型数和一个字符(y表示加急,n表示不加急)
  • 让我们求出来需要支付的费用,(**费用 **:1千克的起步费用是20,超过1千克的每千克一元,不足1千克的按1千克算;如果加急则需要多支付5元的费用)
  • 输出需要支付的费用

算法思路

根据上述题目,我们要求费用,就可以这样来求

  1. 我们将费用分成三部分,一是起步价、二是超出的部分需要支付的费用、三就是加急的费用
  2. 这样显而易见,我们只需要求出来超出部分的费用就可以了,而超出部分有一个要求,就是不足1千克1千克计算;(比如(超出1.3千克,就要按2千克算。)这其实就是向上取整。
  3. 求超出部分:这里提供一个函数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-1i-2两个位置跳过去,那要求最小花费,就在这两个里面找最小的即可;
  • 所以到i位置的最小距离,就等于(从i-1位置跳过去的花费 + 到达 i - 1 位置的最小花费) 和(从i - 2 位置跳过去的花费+到达i - 2 位置的最小花费)中最小的。
  • 那到达i-1i-2位置的最小花费该如何求呢?
  • 很简单,继续向下分解就好了;直到求到达第2个位置的最小花费;我们可以选择选择01开始,所以到达2个位置的话费就等于01跳过去的花费中最小的。

在这里插入图片描述

代码实现

#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. 数组中两个字符串的最小距离

题目链接:数组中两个字符串的最小距离__牛客网

在这里插入图片描述

题目解析

题目要求,给定两个字符串str1str2,然后在给定的字符数组strs中查找两个字符串的最小距离,如果str1str2NULL或者不在strs中就返回-1

题目看起来很简单,直接来看如何实现。

算法思路

暴力解法

暴力解法,两层循环,遍历整个strs数组,将所以的情况都列举出来。这里时间复杂度就是O(n^2)

对暴力解法优化一下:(这也是博主做题时想到的思路)

  • 遍历strs,将str1出现的下标和str2出现的下标分别存到数组v1v2当中
  • 遍历数组v1v2,找到距离最小的。

这里看一下最坏情况,就是strs中一半是str1,一半是str2;这种情况下时间复杂度O(1/4 n^2),时间复杂度也是O(n^2)

但是题目要求时间复杂度为O(n),还能显然暴力解法是解决不掉问题的。

优化解法

这里如果了解过贪心算法,可能就比较容易了;(博主还没学到,这里就一起来看一下如何优化)。

对于数组strs,我们可以从左往右来遍历它,然后只需要在遇到str1(str2)时注意前面最近的str2(str1)就行了。

这里可能有疑惑,那右边的就不需要管了吗?

这里是不需要的,因为我们从左往右遍历数组strs,当我们遍历到右边时就会注意到前面的了。

什么意思呢?

简单来说就是,如果我们左右两边同时关注,那在遍历到右面时就会再次计算一次重复的情况,这里没必要。

这里以示例2为例看一下

在这里插入图片描述

现在来说整个遍历的过程

首先定义变量prev1prev2retprev1表示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;
}

继续加油!!!

关键字:北京公司车牌指标_如何设计个人网站_快速排名程序_关键词自动优化工具

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: