算法竞赛入门【码蹄集进阶塔335题】(MT2326-2330）
算法竞赛入门【码蹄集进阶塔335题】(MT2326-2330）
文章目录
- 算法竞赛入门【码蹄集进阶塔335题】(MT2326-2330）
- 前言
- 为什么突然想学算法了？
- 为什么选择码蹄集作为刷题软件？
- 目录
- 1. MT2326 长度最小的连续子数组
- 2. MT2327 无重复字符的最长子串
- 3. MT2328 最小子串覆盖
- 4. MT2329 方块桶
- 5. MT2330 相似基因
- 结语
前言
为什么突然想学算法了？
> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下快到了考研和找工作的年纪(ಥ_ಥ)，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个暑假速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~
为什么选择码蹄集作为刷题软件？
码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。
目录
1. MT2326 长度最小的连续子数组
（1）题目描述
给定一个含有n个非负整数的数组和一个正整数m 。(1<n ≤100000,1 ≤m ≤1000000000)
找出该数组中满足其和 的长度最小的连续子数组 ，并返回其长度。如果不存在符合条件的子数组，返回0。
格式
输入格式:
第一行输入两个整型n和m
第二行输入整型数组，数组中数字取值范围在0~15000
.
输出格式: 输出整型
样例1
输入格式:
6 7
2 3 1 2 4 3
.
输出格式: 2
（2）参考代码
#include<bits/stdc++.h>
using namespace std;
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0; //滑动窗口数值之和
int subLength = 0; // 滑动窗口的长度
int result = INT32_MAX; //最终结果（标记的作用，目的看是否结果有变化）
int i = 0; //滑动窗口起始位置
for(int j = 0;j < nums.size();j++){ //滑动窗口终止位置
sum += nums[j];
while(sum >= target){
subLength = j-i+1; //子数组的长度
result = subLength < result ? subLength : result;
sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，
//不断变更i（子序列的起始位置）先用i再加，先数值之和减去第i个数的数值移动位
}
}
return result == INT32_MAX ? 0 : result; //如果最终结果没有变化，那么就返回0说明没有找到目标的最小子数组
}
int main(){
int n,m;
scanf("%d %d",&n,&m);
vector<int> nums(n,0);
for(int i=0;i<n;i++){
cin>>nums[i];
}
int res=minSubArrayLen(m, nums);
cout<<res;
return 0;
}
2. MT2327 无重复字符的最长子串
（1）题目描述
给定一个字符串s ，请你找出其中不含有重复字符的最长字串的长度。s 由英文字母、数字、符号和空格组成，长度不大于105。
格式
输入格式: 输入一串字符串
.
输出格式: 输出如题所述最长字串的长度
样例1
输入格式: abcabcbb
.
输出格式: 3
（2）参考代码
#include<bits/stdc++.h>
using namespace std;
int main( )
{
string s;
getline(cin,s);
set<char>ss;
int ans=0;
int len=s.size();
int r=-1;
for(int i=0;i<len;i++){
if(i){
ss.erase(s[i-1]);
}
while(r+1<len&&ss.find(s[r+1])==ss.end()){
r++;
ss.insert(s[r]);
}
ans=max(ans,r-i+1);
}
cout<<ans<<endl;
return 0;
}
3. MT2328 最小子串覆盖
（1）题目描述
给定两个字符串source和target.求source中最短的包含target中每一个字符的子串。若不存在，则输出“No”。
1.字符串全由字母组成，长度不大于1000000 。
2.对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于
target 中该字符数量。
3.若字串存在则唯一。
4.大小写敏感
格式
输入格式:
第一行输入字符串source
第二行输入字符串target
.
输出格式: 输出字符串
样例1
输入格式:
ADOBECODEANXBC
BANC
.
输出格式: ANXBC
（2）参考代码
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
#define int long long int
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define fi first
#define se second
#define rep(i,s,n) for(int i=s;i<n;i++)
#define repd(i,s,n) for(int i=s;i>=n;i--)
const int MOD=1e9+7;
const int maxN=5e3+1;
const int INF=2e9;
const int MB=20;
const int MAX_LEN=200001;
ll s[MAX_LEN];
int t1[128]; //当前串中各元素的个数
int t2[128]; //目标串中的各元素的个数
void solve()
{
string s1,s2;
cin>>s1>>s2;
//统计目标串数量
int lens1=s1.length();
int lens2=s2.length();
for (int i=0;i<lens2;i++)
t2[s2[i]]++;
int minlen=0x3f3f3f3f;
//下面使用滑动窗口来寻找符合的子串
int found=0,start=0;//当前匹配字段长度
int first=-1,end=0;//目标串的位置
for (int i=0;i<s1.length();i++)
{
t1[s1[i]]++;
if (t1[s1[i]]<=t2[s1[i]])
found++;
if (found==lens2)
{
//去除掉前面无用的点
while( start<i &&t1[s1[start]]>t2[s1[start]])
{
t1[s1[start]]--;
start++;
}
if (i-start+1<minlen)
{
first=start;
end=i;
minlen=i-start+1;
}
//最小值更新
t1[s1[start]]--;
start++;
found--;
}
}
if (first==-1)
cout<<"No"<<"\n";
else
cout<<s1.substr(first,end-first+1)<<"\n";
}
signed main()
{
/*
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);*/
solve();
return 0;
}
4. MT2329 方块桶
（1）题目描述
给定n个非负整数表示n个连续竖直放置的方块，请计算这样的方块能装多少水。如，101能装一单位的水。
格式
输入格式:
第一行输入一个整型n(n ≤1000000 )
第二行输入一个整型数组
.
输出格式: 输出一个整型
样例1
输入格式:
12
0 1 0 2 1 0 1 3 2 1 2 1
.
输出格式: 6
（2）参考代码
#include<stdio.h>
const int MAX = 1e6 + 1;
int len, arr[MAX];
int main()
{
scanf("%d", &len);
for (int i = 0; i < len; i++)
scanf("%d", &arr[i]);
int left = 0; //左指针
int right =len - 1; //右指针
int leftMax = arr[0]; //初始左边最大值
int rightMax = arr[len - 1]; //初始右边最大值
long result = 0l;
while (left < right) {
if (arr[left] < arr[right]) {
//左指针移动
++left;
//确定左边最大值(从端点开始，找最大值无非就是比较当前和保存起来的最大值
if (leftMax < arr[left]) {
leftMax = arr[left];
}
result += (leftMax - arr[left]);
}
else {
//右指针移动
--right;
//确定右边最大值
if (rightMax < arr[right]) {
rightMax = arr[right];
}
result += (rightMax - arr[right]);
}
}
printf("%d", result);
return 0;
}
5. MT2330 相似基因
（1）题目描述
基因片段由 四个字母组成。下面给定两个基因片段，请返回它们的相似度。
基因片段中每个字符前都有一个数字(不超过 )，表示该字符连续出现的次数，如，3A4T表示AAATTTT 。
相似表示在相同位置的字符相同。计算得出的相似度以分数的形式表示，无需化简。
保证扩充后两基因片段长度相同，且扩充后长度小于300,000 。
格式
输入格式: 两行字符串
.
输出格式: 一行字符串
样例1
输入格式:
3A4C
1A1C5G
.
输出格式: 1/7
（2）参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
char ch;
static int str1[300005];
static int str2[300005];
int num = 0;
int end = 0;
int size;
int ans = 0;
while (ch = getchar())
{
if ((ch < 'A' || ch > 'Z') && (ch < '0' || ch > '9'))
{
size = end;
end = 0;
num = 0;
break;
}
if (ch >= 'A' && ch <= 'Z')
{
for (int i = end; i < end + num; i++)
{
str1[i] = ch - 'A';
}
end += num;
num = 0;
continue;
}
num = num * 10 + ch - '0';
}
while (ch = getchar())
{
if ((ch < 'A' || ch > 'Z') && (ch < '0' || ch > '9'))
break;
if (ch >= 'A' && ch <= 'Z')
{
for (int i = end; i < end + num; i++)
{
str2[i] = ch - 'A';
}
end += num;
num = 0;
continue;
}
num = num * 10 + ch - '0';
}
for (int i = 0; i < size; i++)
{
if (str1[i] == str2[i])
{
ans++;
}
}
printf("%d%c%d", ans, '/', size);
}
结语
感谢大家一直以来的不断支持与鼓励，码题集题库中的新手村600题现已全部完结，之后会逐步跟进黄金，钻石，星耀，王者的题，尽请期待！！！
同时，也希望这些题能帮助到大家，一起进步，祝愿每一个算法道路上的“苦行僧”们，都能够历经磨难，终成正果，既然选择了这条路，走到了这里，中途放弃，岂不是太过可惜？
另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0，供大家更好的进行学习与刷题～(￣▽￣～)~
愿你的结局，配得上你一路的颠沛流离。