每周算法2:数学+模拟+哈希表+栈+线性dp+贪心(简单)
目录
1.统计数字
描述
输入描述：
输出描述：
题解
2.两个数组的交集(哈希表)
描述
题解
3.点击消除(栈)
描述
输入描述：
输出描述：
题解
4.牛牛的快递(模拟+补充)
描述
输入描述：
输出描述：
题解
5.最小花费爬楼梯(简单线性dp)
描述
输入描述：
输出描述：
示例1
题解
6.数组中两个字符串的最小距离(贪心)
题解
1.统计数字
题目地址:[NOIP2010]数字统计_牛客题霸_牛客网
描述
请统计某个给定范围[L, R]的所有整数中，数字2出现的次数。
比如给定范围[2, 22]，数字2在数2中出现了1次，在数12中出现1次，在数20中出现1次，在数21中出现1次，在数22中出现2次，所以数字2在该范围内一共出现了6次。
输入描述：
输入共1行，为两个正整数L和R，之间用一个空格隔开。
输出描述：
输出共1行，表示数字2出现的次数。
示例1
输入：
2 22输出：
6示例2
输入：
2 100输出：
20
题解
#include<bits/stdc++.h>
using namespace std;
size_t fun(int n)
{
int cnt=0;
while(n)
{
if(n%10==2)cnt++;
n/=10;
}
return cnt;
}
int main()
{
int L,R;cin>>L>>R;
int ret=0;
for(int i=L;i<=R;i++)
ret+=fun(i);
cout<<ret<<endl;
return 0;
}2.两个数组的交集(哈希表)
题目地址:两个数组的交集_牛客题霸_牛客网
描述
给定两个整数数组分别为nums1,nums1, nums2,nums2，找到它们的公共元素并按返回。
数据范围：
1≤nums1.length,nums2.length≤10001≤nums1.length,nums2.length≤1000
1≤nums1[i],nums2[i]≤10001≤nums1[i],nums2[i]≤1000示例1
输入：
[1,2 ],[2,2,2,2]返回值：
[2]说明：
两个数组的公共元素只有2示例2
输入：
[1,2,3],[8,2,2,3,8]返回值：
[2,3]说明：
两个数组的公共元素为2和3，返回[3,2]也是一个正确的答案
题解
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
vector<int>ret;
bool hash[1002]={0};
for(auto x:nums1)
{
hash[x]=true;
}
for(auto x:nums2)
{
if(hash[x])
{
ret.push_back(x);
hash[x]=false;
}
}
return ret;
}
};3.点击消除(栈)
题目地址:点击消除_牛客题霸_牛客网
描述
牛牛拿到了一个字符串。
他每次“点击”，可以把字符串中相邻两个相同字母消除，例如，字符串"abbc"点击后可以生成"ac"。
但相同而不相邻、不相同的相邻字母都是不可以被消除的。
牛牛想把字符串变得尽可能短。他想知道，当他点击了足够多次之后，字符串的最终形态是什么？输入描述：
一个字符串，仅由小写字母组成。（字符串长度不大于300000）
输出描述：
一个字符串，为“点击消除”后的最终形态。若最终的字符串为空串，则输出0。
示例1
输入：
abbc输出：
ac示例2
输入：
abba输出：
0
题解
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s;string st;
cin>>s;
for(auto x:s)
{
if(!st.empty()&&x==st.back())
{
st.pop_back();
}
else {
st.push_back(x);
}
}
if(st.empty())cout<<0<<endl;
else cout<<st<<endl;
return 0;
}这道题考察的是数据结构中的栈的使用,我们可以使用stack但是最后打印的时候需要reverse一下,所以我们干脆直接使用一个字符数组string来模拟栈,遍历原来的字符串,如果栈不为空的情况下就判断栈顶元素和当前元素是否一样,如果一样那么就可以消除(将栈顶元素弹出),继续遍历,最后剩下的就是没有挨在一起的字符,如果栈为空那就打印0;
4.牛牛的快递(模拟+补充)
题目地址:牛牛的快递_牛客题霸_牛客网
描述
牛牛正在寄快递，他了解到快递在 1kg 以内的按起步价 20 元计算，超出部分按每 kg 1元计算，不足 1kg 部分按 1kg计算。如果加急的话要额外付五元，请问牛牛总共要支付多少快递费
输入描述：
第一行输入一个单精度浮点数 a 和一个字符 b ，a 表示牛牛要寄的快递的重量，b表示牛牛是否选择加急，'y' 表示加急 ，'n' 表示不加急。
输出描述：
输出牛牛总共要支付的快递费用
示例1
输入：
1.5 y输出：
26示例2
输入：
0.7 n输出：
20
这道题写出来并不难,主要是为了补充两个函数 ceil(double)向上取整,floor(double)向下取整;
题解
#include<bits/stdc++.h>
using namespace std;
int main()
{
double x;char ch;
cin>>x>>ch;
int ret=0;
if(floor(x)>=1)//如果向下取整大于等于1,那就一定有超出的部分
{
ret+=20;
ret+=ceil(x-1);//加上取整的部分
}
else {
ret+=20;
}
if(ch=='y')ret+=5;
cout<<ret<<endl;
return 0;
}5.最小花费爬楼梯(简单线性dp)
题目地址:最小花费爬楼梯_牛客题霸_牛客网
描述
给定一个整数数组 cost cost ，其中 cost[i] cost[i] 是从楼梯第i i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
数据范围：数组长度满足 1≤n≤105 1≤n≤105 ，数组中的值满足 1≤costi≤104 1≤costi≤104
输入描述：
第一行输入一个正整数 n ，表示数组 cost 的长度。
第二行输入 n 个正整数，表示数组 cost 的值。
输出描述：
输出最低花费
示例1
输入：
3 2 5 20输出：
5说明：
你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5
十分经典的线性dp问题,细节要注意,dp[i]是到达第i级台阶的最小费用;
状态转移方程为:dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]),这里为了方便,我们cost从下标1开始存储数据;
题解
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;cin>>n;
vector<int>cost(n+1);
for(int i=1;i<=n;i++)
cin>>cost[i];
vector<int>dp(n+1);
dp[1]=0,dp[2]=0;
for(int i=3;i<=n;i++)
{
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
cout<<min(dp[n]+cost[n],dp[n-1]+cost[n-1]);
return 0;
}6.数组中两个字符串的最小距离(贪心)
题目地址:数组中两个字符串的最小距离__牛客网
这道题暴力解法肯定是超时的,因为需要的是两个字符串的最小距离,我们可以使用两个变量分别储存s1和s2的下标,遍历数组,如果遇到s1就找前面最近的s2,更新长度ret=min(ret,i-prev2);遇到s2就找前面最近的s1,更新ret=min(ret,i-prev1);并同时更新prev1和prev2的值;
题解
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;cin>>n;
string s1,s2;cin>>s1>>s2;
int prev1=-1;int prev2=-1;int ret=0X3f3f3f3f;
string s;
for(int i=0;i<n;i++)
{
cin>>s;
if(s==s1)//去找前面最近的s2
{
if(prev2!=-1)
{
ret=min(ret,i-prev2);
}
prev1=i;//更新s1下标
}
else if(s==s2)//去找前面最近的s1
{
if(prev1!=-1)
{
ret=min(ret,i-prev1);
}
prev2=i;//更新s2下标
}
}
if(prev1==-1||prev2==-1)cout<<-1<<endl;
else
cout<<ret<<endl;
}