首页 > 编程语言 >每周算法2:数学+模拟+哈希表+栈+线性dp+贪心(简单)

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

时间:2024-11-10 15:50:17浏览次数:6  
标签:数组 int 题解 ret 输入 哈希 贪心 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; 
}

标签:数组,int,题解,ret,输入,哈希,贪心,dp,描述
From: https://blog.csdn.net/2301_80418172/article/details/143660969

相关文章

  • 【网络】套接字编程——UDP通信
    >作者:დ旧言~>座右铭:松树千年终是朽,槿花一日自为荣。>目标:UDP网络服务器简单模拟实现。>毒鸡汤:有些事情,总是不明白,所以我不会坚持。早安!>专栏选自:网络>望小伙伴们点赞......
  • wordpress站外调用指定ID分类下的推荐内容
    在WordPress中,如果你想从站外调用指定ID分类下的推荐内容,你可以使用WordPressRESTAPI来实现。以下是一个基本的步骤指南:1.启用RESTAPI确保你的WordPress站点已经启用了RESTAPI。大多数现代WordPress版本默认启用此功能。2.获取分类ID首先,你需要知道你要调用的分类的I......
  • 每日一题.设计相邻元素求和服务;暴力算法与哈希表的运用
    本题出自LeetCode每日一题3242,可以说比昨天的那道“每日抑题”简单不少呀,就是代码长一点,同时本题目使用了两种不同的方法,并对每一种用法进行了深度解析。本文全长5000字。题目 给你一个 nxn 的二维数组 grid,它包含范围 [0,n2-1] 内的不重复元素。实现 neighbo......
  • 【算法】状态压缩DP
    基本内容入门例子USACO06NOV]CornFieldsG-洛谷|计算机科学教育新生态题目简述:在一个\(N\timesM\)的玉米田中种玉米,有一些坏掉的土地是不能种玉米的,另外相邻的两个田也不可以种,一共有多少种种植方案(荒地也算一种),如图所示,由于相邻的土地不能种植,此时一号土地已经不能......
  • 带悔贪心 QOJ interval
    interval带反悔的贪心即通过堆(大根堆、小根堆)来维护当前贪心策略的最优解,若发现最优解不对,就退回上一步,更新最优解。将区间按照左端点排序,从左向右遍历区间。当前区间为\([l,r]\),取出当前右端点最左的区间,可以就匹配。如果不可以,去看看已经匹配的这些对区间中的\((b,c)\),\(c......
  • 关于 DP 的非常规优化
    感觉这个东西就是玄学啊,考场上真的有人能想得出来嘛。(还是我太菜了qwq)思想现在见到的有这几种:从\(i\)推到\(i+1\)时状态改变的数量不会太多,直接继承可以优化。可能对答案有贡献的状态不会太多。即通过一些性质来消除掉冗余状态以保证时间复杂度。ABC176FBraveCH......
  • InDepth Guide to Denoising Diffusion Probabilistic Models DDPM:DDPM扩散概率模型去
    AnIn-DepthGuidetoDenoisingDiffusionProbabilisticModelsDDPM–TheorytoImplementation中文翻译:DDPM扩散概率模型去噪深度指南——理论到实现https://learnopencv.com/denoising-diffusion-probabilistic-models/#forward-diffusion-equationhttps://github.com/......
  • 计算机网络 - UDP 协议
    定义UDP(UserDatagramProtocol)用户数据报协议:是一种无连接的数据传输协议,传输前不需要建立连接,没有复杂的协议优点是:首部开销小,不需要连接,机制简单,可以一对一,一对多,多对一通信,使用与直播、视频通话等业务领域缺点是:传输无序,不能保证消息一定送到,有丢包的问题报文如下UDP报......
  • cmu15545-哈希表(Hash Table)
    基本概念哈希和树一样,是数据库系统中用于访问数据的方法。空间复杂度:$O(n)$时间复杂度:$O(1)~O(n)$权衡:更大的哈希空间(碰撞减少),还是更少的哈希空间(碰撞处理)?哈希函数CRC-64(1975)MurmurHash(2008)GoogleCityHash(2011)FacebookXXHash(2012)【最常用】Goo......
  • 【论文系列】DDIM ---DDPM上的优化
    WhatDDIM是啥?DDIM(DenoisingDiffusionImplicitModels)是一种扩散模型的变体,旨在加速图像生成过程并保持生成质量。它是在DDPM(DenoisingDiffusionProbabilisticModels)的基础上发展出来的,提供了一种更高效的去噪采样过程,减少了采样所需的步骤数量。WhyDDIM提出了能干啥?DD......