网站代备案公司,电子商务论文网站建设,wordpress 修改导航,兰州网站建设技能论文目录
A-B数对
解法一#xff1a;双指针
解法二#xff1a;STL二分查找
解法三#xff1a;map
求和
元音字母
最短连续子数组
无重复字符的最长子串
最小子串覆盖
方块桶 双指针特点#xff1a;双指针绝不回头 A-B数对 解法一#xff1a;双指针 先把数列排列成…目录
A-B数对
解法一双指针
解法二STL二分查找
解法三map
求和
元音字母
最短连续子数组
无重复字符的最长子串
最小子串覆盖
方块桶 双指针特点双指针绝不回头 A-B数对 解法一双指针 先把数列排列成递增的就可以使用双指针了。找到满足a[r]-a[l]c即可 对每个l找对应的两个r一个是满足条件且在最左边的一个是满足条件且在最右边的 如果刚好可以取等那么右减左就是该情况下的答案否则右减左就是0
#include bits/stdc.h
#define ll long long
using namespace std;
const int N 2e5 10;
int n , c;
int a[N];
int main ()
{cin n c;for(int i 1 ; i n ; i ) cin a[i];sort(a 1 , a 1 n); //首先就必须要排序int l 1, r1 1 , r2 1;ll ans 0;for(l 1 ; l n ; l ) {while(r1 n a[r1] - a[l] c) r1 ;//对每一个数A找右边刚不满足A-BC的数下标while(r2 n a[r2] - a[l] c ) r2 ;//再找左边刚满足A-BC的数下标ans r1 - r2;}cout ans;return 0;
}
解法二STL二分查找
在有序数组找某个数不用stl用什么
#include bits/stdc.h
using namespace std;
int N, C, A[200010];int main() {scanf( %d%d, N, C );for( int i 1; i N; i ) scanf( %d, A[ i ] );sort( A 1, A N 1 );long long ans 0;for( int i 1; i N; i ) ans upper_bound( A 1, A N 1, A[ i ] - C ) - lower_bound( A 1, A N 1, A[ i ] - C );printf( %lld\n, ans );return 0;
}解法三map
既然要同一个值得数量那么就拿数值存下标说错了。这样会爆掉的直接上map进行离散化数组就行了什么意思就是你别拿一个连续的玩意去存你拿一个离散的东西去存就行了。
#include iostream //A-B数对P1102 (map映射法) 有点耗时
#include unordered_map //A-BC -- A-CB
using namespace std;
typedef long long LL;
LL a[200001];
unordered_mapLL,LL m; //建立一个数字到出现次数的映射 mapnum,times
int main() {int n; LL c;LL ans0;cin n c; for(int i1;in;i) {cin a[i]; m[a[i]]; //标记每个数字和对应的映射a[i]-c; //把first减c找更新后映射的数量} for(int i1;in;i) ansm[a[i]];cout ans endl;return 0;
} 求和
求满足和为x所有的自然数区间如果没有输出No 思路
对每个l开头的区间尝试求解。
双指针移动时[l,r]恰好为x就说明[l,r1]和[l1,r]没用了所以整体右移l,r
[l,r]x就r右移[l,r]x就l右移(这次的l已经没用了)
然后就是注意一下结束条件lx/2
#include bits/stdc.h
using namespace std;
int main(){int x,l1,r2,sum0;cinx;int f0;while(lx/2){ //这个结束条件很有意思lx/2就没必要再找了sum(lr)*(r-l1)/2;if(sumx){f1;coutl r\n;l;r;}else if(sumx)r;else l;}if(!f)coutNo;
} 元音字母
给一个字符串s和整数k求s的长度为k的子串可能包含的最大元音字母个数
输入 输出3 abciiidef
思路
[l,r]一定是整体移动的所以只需要观察l和r1情况即可如果都是或都不是cnt不变直接不管剩下的就是cnt和cnt--了
#include bits/stdc.h
using namespace std;
int check(char ch){if(cha||che||chi||cho||chu)return true;return false;
}
int main(){string s;int k;cinsk;int l0,rk-1,ans0,cnt0,lens.size();for(int i0;ik;i){if(check(s[i]))cnt;//初始化}anscnt;while(rlen){//整体移动一次就判断一次if(!check(s[l])check(s[r1]))cnt;if(check(s[l])!check(s[r1]))cnt--;l;r;ansmax(ans,cnt);}coutans;
}最短连续子数组
给一个含有n个非负数的数组和一个正整数m。找出该数组中满足和不小于m的长度最小的连续子数组并返回其长度否则返回0
输入 输出2 6 7 2 3 1 2 4 3 思路 在移动过程中[l,r]如果满足条件的话一定要l来取最小长度否则就r即可。
一直都是r在默默前行l只需要统计结果即可
#include bits/stdc.h
using namespace std;
const int N1e510;
int n,m,a[N],ans0x3f3f3f3f;int main(){cinnm;for(int i1;in;i){cina[i];}int sum0;for(int l0,r0;rn;r){suma[r];while(summ){ansmin(ans,r-l1);sum-a[l];l;}}cout(ans0x3f3f3f3f ? 0 : ans);
}无重复字符的最长子串
给一个字符串s找出其中不含有重复字符的最长字串的长度。 abcabcbb
思路 首先使用mapchar,int来统计每个字符出现次数一遍统计一遍检查是否有重复字符。
如果有对于[l,r]就l直到没有再r #include bits/stdc.h
using namespace std;
unordered_mapchar,intma1;
string s;
int ans0;
int main(){getline(cin,s);int len1s.size();for(int l0,r0;rlen1;r){ma1[s[r]];while(ma1[s[r]]2){ma1[s[l]]--;l;}ansmax(ans,r-l1);}coutans;
}最小子串覆盖
给两个字符串s,t求s中最短的包含t每一个字符的子串若不存在就返回No 输入
ADOBECODEANXBC 输出ANXBC BANC 思路
不是找子序列啊注意看样例。
首先要统计t字符串的字符情况然后在对s字符串使用双指针时候也要统计区间中的字符情况同时记录和t字符串的字符满足个数对应字符数量相等。
当[l,r]中已经满足条件时候就l取找答案同时对应的字符数量减一直到不满足再r。 #include bits/stdc.h
using namespace std;
unordered_mapchar,intma1,ma2;
string s,t;
int ans0x3f3f3f3f;
int main(){cinst;int len1s.size(),len2t.size();for(int i0;ilen2;i)ma2[t[i]];int sum0;//sum表示满足的个数int l0,r0,ll0,rr0;while(rlen1){ma1[s[r]];if(ma2[s[r]]!0ma1[s[r]]ma2[s[r]])//是t的字符且s的数量不多余sum;if(sumlen2){while(ma1[s[l]]ma2[s[l]]){//从左开始删掉多余的l一次删掉一次ma1[s[l]]--;l;}if(r-l1ans){ansr-l1;lll;rrr;//ll和rr是上次答案对应的左右指针}}r;} if(ans0x3f3f3f3f) coutNo;elsecouts.substr(ll,rr-ll1);
}方块桶
给n个非负整数表示连续n个竖直放置的方块计算这样的方块可以装多少水 12 0 1 0 2 1 0 1 3 2 1 2 1 思路
其实在模拟的时候发现左边这个高度下是否可以填水取决于右边的最大高度右边更高那么一定可以填水右边同理。然后两条同时开始统计就行了
#include bits/stdc.h
using namespace std;
const int N1e610;
int n,a[N],maxl,maxr,ans;
int main(){cinn;for(int i1;in;i)cina[i];maxla[1],maxra[n];int l1,rn;while(lr){if(maxlmaxr){l;maxlmax(maxl,a[l]);ansmaxl-a[l];}else{r--;maxrmax(maxr,a[r]);ansmaxr-a[r];}}coutans;
}