牛牛的AC

[编程题]牛牛的AC

热度指数：1740 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一年一度的春招就要到来了，牛牛为了备战春招，在家刷了很多道题，所以牛牛非常喜欢AC这两个字母。他现在有一个只包含A和C的字符串，你可以任意修改最多k个字符，让A变成C，或者C变成A。请问修改完之后，最长连续相同字符的长度是多少。

示例1

输入

1,"AAAC"

输出

说明

样例一：将最后一位C改成A即可。

备注:

字符串长度<=10^6，且只包含'A'和'C'，k<=10^6。

算法知识视频讲解

slaxes_G

Python3滑动窗口，区间内a、c数量不都大于k时计算长度并移动右端点，反之移动左端点

class Solution:
    def Solve(self , k , s ):
        if s == '':
            return 0
        res, left, right, l = 1, 0, 0, len(s)
        a_num = 0 if s[0] == 'C' else 1
        c_num = 0 if s[0] == 'A' else 1
        while True:
            if a_num > k and c_num > k:
                if s[left] == 'A':
                    a_num -= 1
                else:
                    c_num -= 1
                left += 1
            else:
                res = max(res, right-left+1)
                right += 1
                if right == l:
                    break
                else:
                    if s[right] == 'A':
                        a_num += 1
                    else:
                        c_num += 1
        return res

发表于 2020-03-29 02:10:51 回复(0)

C/C++

nbgao

class Solution {
public:
    /**
     * 
     * @param k int整型 
     * @param s string字符串 
     * @return int整型
     */
    int Solve(int k, string s) {
        int a=0, c=0, Max=0;
        for(int l=0,r=0;r<s.length();r++){
            if(s[r]=='A')
                a++;
            else
                c++;
            while(a>k && c>k){
                if(s[l++]=='A')
                    a--;
                else
                    c--;
            }
            Max = max(Max, a+c);
        }
        return Max;
    }
};

发表于 2020-08-23 03:06:41 回复(0)

Java

牛客179078319号

运行效率太低了，超大字符串测试时内存和效率不通过。结果都正常。不知道怎么解了。

public int Solve (int k, String s) {

// write code here
String maxStr = "";
for (int i = 0;i<s.length();i++) {
for (int j=s.length();j>i;j--) {
String sub = s.substring(i,j);
if (j-i <maxStr.length()) {
continue;
}
if (sub.replaceAll("A","").length()<=k || sub.replaceAll("C","").length()<=k) {
if (maxStr.length() < sub.length()){
maxStr = sub;
}
}
}
}
return maxStr.length();
}

发表于 2021-07-28 22:42:30 回复(0)

yeshichen

滑动窗口

 public int Solve(int k, String s) {
        char[] chs = s.toCharArray();
        int start = 0, end = 0, n = s.length(), max = 0, a = 0, c = 0;
        while (end < n) {
            if (chs[end++] == 'A') a++;
            else c++;
            while (a > k && c > k) {
                if (chs[start++] == 'A') a--;
                else c--;
            }
            max = Math.max(a + c, max);
        }
        return max;
    }

编辑于 2020-08-14 21:14:06 回复(1)