免费头像生成制作网站,Wordpress标签与分类,优化型网站模板,福清市住房和城乡建设局网站题目 思路和解题方法 程序首先定义了一个函数check#xff0c;用于判断一个字符是否为字母。接下来#xff0c;程序读取输入的整数k和一行字符串str。定义了两个空的向量a和b#xff0c;用于存储满足条件的子串的起始位置。使用for循环遍历字符串str的每个字符#xff0c;检…题目 思路和解题方法 程序首先定义了一个函数check用于判断一个字符是否为字母。接下来程序读取输入的整数k和一行字符串str。定义了两个空的向量a和b用于存储满足条件的子串的起始位置。使用for循环遍历字符串str的每个字符检查是否存在以Alice和Bob开头的满足条件的子串并将其起始位置记录在向量a和b中。初始化变量ans为0用于记录满足条件的子串对数。使用双指针技巧遍历向量a中的元素即以Alice开头的子串维护一个窗口窗口的左边界为l右边界为r。在每次遍历时通过移动右指针r和左指针l的位置保证窗口内的子串满足要求。具体而言右指针r向右移动直到超过以Alice开头的子串的末尾位置k5左指针l向右移动直到超过以Alice开头的子串的起始位置-k-3。每次更新窗口后将满足条件的子串对数加上窗口中的元素个数即r-l并累加到ans中。最后输出ans即满足条件的子串对数。 复杂度 时间复杂度: O(n) 时间复杂度假设输入的字符串长度为n那么代码中的主要操作是遍历字符串、查找子串以及双指针移动。遍历字符串的时间复杂度为O(n)查找子串的时间复杂度为O(n)而双指针移动的时间复杂度为O(n)。因此总体时间复杂度为O(n)。 空间复杂度 O(n) 空间复杂度代码中使用了两个向量a和b用于存储满足条件的子串的起始位置。最坏情况下向量a和b的长度都可能达到n因此它们所占用的空间复杂度为O(n)。此外还有一些辅助变量和常数空间的占用但相对来说是常数级别的。因此总体空间复杂度为O(n)。 c 代码
#includeiostream
#includevector
using namespace std;typedef long long ll;
bool check(char c){return cAcZ||cacz;
}
int main(){ll k;cink; getchar();string str;getline(cin,str);vectorll a,b; // 遍历字符串找出Alice和Bob的位置for(ll i 0;i3str.size();i){// 判断是否为Aliceif(str.substr(i,5) Alice (!check(str[i5]))(!check(str[i-1])) i5str.size())a.push_back(i);// 判断是否为Bobif(str.substr(i,3) Bob (!check(str[i3]))(!check(str[i-1])))b.push_back(i);}ll ans 0 ;for(ll i 0,l0,r0; i a.size(); i){ //遍历Alice数组元素 while(l b.size() b[l] a[i] - k - 3) l; //维护窗口左边界 while(r b.size() b[r] a[i] k 5) r; //维护窗口右边界 ans r - l; //答案加上窗口中元素个数 }coutansendl;
}注释ll 是 long long 类型的别名用于存储较大的整数值。
check() 函数用于判断一个字符是否为字母。
k 是输入的一个整数值表示一个窗口的大小。
str 是输入的字符串。
a 和 b 分别是存储 Alice 和 Bob 出现位置的数组。
遍历字符串 str找出每个 Alice 和 Bob 的位置并将其存储在对应的数组中。
ans 是计数变量记录符合条件的情况个数。
使用两个指针 l 和 r 维护一个滑动窗口。
遍历数组 a对于每个 Alice 的位置更新滑动窗口的左右边界。
l 和 r 分别指向滑动窗口的左右边界。
ans 加上窗口中元素的个数即 r - l。
最后输出答案 ans。
觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
