筛选选功能形网站建设,wordpress哪个模版好用,大连房地产网站开发,营销业务应用系统文章目录1. 题目2. 解题2.1 双指针2.2 二分查找1. 题目
链接#xff1a;https://ac.nowcoder.com/acm/contest/9752/B 来源#xff1a;牛客网
牛牛现在有一个长度为len只包含小写字母‘a’-z’的字符串x#xff0c;他现在想要一个特殊的子序列#xff0c; 这个子序列的长…
文章目录1. 题目2. 解题2.1 双指针2.2 二分查找1. 题目
链接https://ac.nowcoder.com/acm/contest/9752/B 来源牛客网
牛牛现在有一个长度为len只包含小写字母‘a’-z’的字符串x他现在想要一个特殊的子序列 这个子序列的长度为3*nn为非负整数 子序列的第[1,n]个字母全部为‘a’ 子序列的[n1,2*n]个字母全部为‘b’ 子序列的[2*n1,3*n]个字母全部为‘c’ 牛牛想知道最长的符合条件的独特子序列的长度是多少。
示例1
输入
cbacb
返回值
0
说明
没有符合条件的非空子序列所以输出0示例2
输入
abaabbcccc
返回值
6
说明
最长的符合条件的子序列为aabbcc所以输出62. 解题
2.1 双指针
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可* * param x string字符串 * return int整型*/// typedef pairint,int pii;int Maximumlength(string x) {// write code herestring s;for(auto c : x)if(ca || cb || cc)s c; //只需要abc字符int n s.size();if(n 3) return 0;vectorint numa(n1, 0), numb(n1, 0), numc(n1, 0);//前缀和个数for(int i 1; i n; i){if(s[i-1] a){numa[i] numa[i-1] 1;numb[i] numb[i-1];numc[i] numc[i-1];}else if(s[i-1] b){numa[i] numa[i-1];numb[i] numb[i-1]1;numc[i] numc[i-1];}else{numa[i] numa[i-1];numb[i] numb[i-1];numc[i] numc[i-1]1;}}int ans 0, a 0, b 0, c 0;int i 1, j n;// 贪心让 a c交替变多while(i j){int MIN min(a,min(b,c));//数量最少的if(MIN a){a numa[i];}else if(MIN c){c numc[n]-numc[--j];}elsebreak;b numb[j]-numb[i-1];ans max(ans, 3*min(a,min(b,c)));}return ans;}
};2.2 二分查找
通用解法
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可* * param x string字符串 * return int整型*/// typedef pairint,int pii;int Maximumlength(string x) {// write code herestring s;for(auto c : x)if(ca || cb || cc)s c;int n s.size();if(n 3) return 0;int l 0, r n/3, mid, ans 0;while(l r){mid (lr)/2;if(ok(s, mid)){ans mid*3;l mid1;}elser mid-1;}return ans;}bool ok(string s, int n){int a 0, b 0, c 0;for(int i 0; i s.size(); i){if(a n){if(s[i] a)a;}else if(b n){if(s[i] b)b;}else{if(s[i] c)c;}}return c n;}
};我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
