郑州模板建站,锐酷网站建设教程,先进的网站建设,社交网络推广方法有哪些子串简写#xff08;跳跳双指针、妙妙剪枝#xff09;
1.子串简写 - 蓝桥云课 (lanqiao.cn)
这里的剪枝实在是泰妙啦#xff01;
回顾一下我这个蠢蛋的思路#xff1a;一开始遍历leni#xff0c;结果只过了俩#xff1b;然后遍历i和j#xff0c;len直接计算#xff…子串简写跳跳双指针、妙妙剪枝
1.子串简写 - 蓝桥云课 (lanqiao.cn)
这里的剪枝实在是泰妙啦
回顾一下我这个蠢蛋的思路一开始遍历leni结果只过了俩然后遍历i和jlen直接计算只过了70%之后将a、b的位置全部存储遍历ab的所有情况过了80%最后使用剪枝确定了a确定了首个满足的b就可以计算得到以a为起点的所有满足条件的b的个数然后直接break这才能全过。
本题你可以学到的存储关键位置解决子串问题、双指针剪枝用计算的方式求出当前情况下的数量总数-首个位置
#include iostream
#include string
#include vector
using namespace std;//思路把字符串中等于a的下标都存起来把等于b的下标也都存起来。
// 然后判断两者下标之间有无大于等于k直接加上
// b的个数-当前b下标因为cnt2等于b的个数加1所以直接减就好不用在加1int main()
{string s;int k;char a, b;long ans 0;cin k s a b;vectorintlista;vectorintlistb;for (int i 0; i s.size();i) //把a b的位置存起来{if (s[i] a) lista.push_back(i);else if (s[i] b) listb.push_back(i);}//这样遍历只能过80%/*for (int i 0; i lista.size(); i){for (int j 0; j listb.size(); j)if (listb[j] - lista[i] 1 k)ans;}*///优化一下仔细想想listb[j]lista[i]的就完全没有必要再遍历一遍所以我们可以通过一个jump来跳转 //同时比如 aabbbbbbb这种我们不必一个一个加因为我们存进去的listb是递增的// 所以当找到第一个满足要求的b的时候就只需要用size-j就得到以i为起点的所有b的个数了int jump 1;for (int i 0; i lista.size(); i)for (int j jump; j listb.size(); j)if (listb[j] - lista[i] 1 k){ans listb.size() - j;jump j; //这里用jumpj这样下次来的时候就不用再遍历jump之前的j了那些都是不满足的break; //这里直接跳出了因为只要确定i和首个j就可以得到以i为起点的所有满足的个数只用算这一次}cout ans;return 0;
}二刷
能成功自己做出来了哇咔咔咔刷到后面脑海里面其实真的没有印象了但是实际上潜意识还是会引导你走向正确的道路所以加油吧刷题人QWQ。
//子串简写
#include iostream
#include string
#include vector
using namespace std;//可以将对应位置记录下来然后遍历不不用遍历直接累加b数组后面没计算的个数 int n;
string s;
char a,b;
vectorintamp;
vectorintbmp;int main()
{cinnsab;for(int i0;is.size();i){if(as[i]) amp.push_back(i);if(bs[i]) bmp.push_back(i);}long long ans0; //不开long long 只能过90%//没有跳转只能过90%剩下一个超时跳转是为了避免重复计算 bmp[j]-amp[i]1n 的内容
// for(int i0;iamp.size();i)
// for(int j0;jbmp.size();j)
// {
// if(bmp[j]-amp[i]1n)
// {
// ansbmp.size()-j;
// break;
// }
// }int temp0; for(int i0;iamp.size();i)for(int jtemp;jbmp.size();j){if(bmp[j]-amp[i]1n){ansbmp.size()-j;tempj;break;}}coutans;return 0;}
