牛客编程巅峰赛S2第7场 - 钻石&王者 A.牛牛的独特子序列 (字符串,二分)

题意:给你一个字符串,找出一个类似为\(aaabbbccc\)这样的由连续的\(abc\)构成的子序列,其中\(|a|=|b|=|c|\),问字符串中能构造出的子序列的最大长度.
题解:这题刚开始一直想怎么线性扫过,结果好像没有什么思路(其实是可以预处理\(b\)的个数然后双指针的),但这题最好写的其实还是二分答案,在check的时候,因为\(a,b,c\)的长度是相同的,那么我们就直接线性找目前二分的长度\(cur\)个\(a\),然后再去找\(cur\)个\(b\),最后找\(cur\)个\(c\),如果发现\(a,b,c\)中任意一个字符有剩余,那么我们肯定是找大了,更新右区间,否则更新左区间.

代码:

class Solution {

public:

    /**

     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

     *

     * @param x string字符串

     * @return int整型

     */

    bool check(string s,int cur){

        int cnt1=cur,cnt2=cur,cnt3=cur,i=0;

        while(i<(int)s.size() && cnt1){

            if(s[i]=='a') cnt1--;

            i++;

        }

        while(i<(int)s.size() && cnt2){

            if(s[i]=='b') cnt2--;

            i++;

        }

        while(i<(int)s.size() && cnt3){

            if(s[i]=='c') cnt3--;

            i++;

        }

        return !(cnt1+cnt2+cnt3);

    }

    int Maximumlength(string x) {

        // write code here

        int l=0,r=(int)x.size();

        while(l<r){

            int mid=(l+r+1)>>1;

            if(check(x,mid)) l=mid;

            else r=mid-1;

        }

        return r*3;

    }

};

巴特西

牛客编程巅峰赛S2第7场 - 钻石&王者 A.牛牛的独特子序列 (字符串,二分)

最新文章

热门文章