每周算法2:数学+模拟+哈希表+栈+线性dp+贪心(简单)

这道题考察的是数据结构中的栈的使用,我们可以使用stack但是最后打印的时候需要reverse一下,所以我们干脆直接使用一个字符数组string来模拟栈,遍历原来的字符串,如果栈不为空的情况下就判断栈顶元素和当前元素是否一样,如果一样那么就可以消除(将栈顶元素弹出),继续遍历,最后剩下的就是没有挨在一起的字符,如果栈为空那就打印0;比如给定范围[2, 22]，数字2在数2中出现了1次，在数12中出

啊QQQQQ

1392人浏览 · 2024-11-10 15:57:08

啊QQQQQ · 2024-11-10 15:57:08 发布

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;
}

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; 
}