首页 > 试题广场 > 编程题2
[编程题]编程题2
  • 热度指数:4850 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
有一个仅包含’a’和’b’两种字符的字符串s,长度为n,每次操作可以把一个字符做一次转换(把一个’a’设置为’b’,或者把一个’b’置成’a’);但是操作的次数有上限m,问在有限的操作数范围内,能够得到最大连续的相同字符的子串的长度是多少。

输入描述:
第一行两个整数 n , m (1<=m<=n<=50000),第二行为长度为n且只包含’a’和’b’的字符串s。


输出描述:
输出在操作次数不超过 m 的情况下,能够得到的 最大连续 全’a’子串或全’b’子串的长度。
示例1

输入

8 1
aabaabaa

输出

5

说明

把第一个 'b' 或者第二个 'b' 置成 'a',可得到长度为 5 的全 'a' 子串。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


/**
 * 利用前缀和数组
 * 例如:
 * n=10,m=1,s=baabaabaab
 *   b a a b a a b a a b
 *   0 1 2 3 4 5 6 7 8 9
 *   
 *   将 b-->a
 *   b 的前缀和数组为
 *          sums={ 0, 3, 6, 9, 10}//10 为字符串长度
 *   计算长度分别为: 
 *          3  6-0-1=5   9-3-1=5  10-6-1=3
 *     ==>>max = max{ max, sums[i]-sum[i-m-1]-1}
 */

public class Main{
    public static int change(int n, int m, String s, char k) {
        int max = 0;
        List<Integer> sums = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == k) {
                sums.add(i);
            }
        }
        if (sums.size() <= m) {
            return n;
        }
        sums.add(s.length());
        max = sums.get(m);
        for (int i = m + 1; i < sums.size(); i++) {
            max = Integer.max(max, sums.get(i) - sums.get(i - m - 1) - 1);
        }
        return max;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        String s = scanner.next();
        System.out.println(Integer.max(change(n, m, s, 'a'), change(n, m, s, 'b')));
    }
}
发表于 2019-02-01 02:44:10 回复(8)
复杂度O(n)解法: 设置两个指针l,r分别指向当前最长可行翻转的子串(也就是该串的'a'或者'b'字符加起来不超过m的子字符串)的头和尾,遍历一次字符串即可求解。
#include<stdio.h>

char c[50010];
int n, m;

int main(){
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++) scanf("%c", &c[i]);
    int maxl=0, l=0, r=0, an=0, bn=0;
    while(r<=n){
        if(c[r]=='a') an++;
        else bn++;
        if(an<=m||bn<=m){
            r++;
        }else{
            if((r-l)>maxl) maxl=r-l;
            if(c[l]=='a'){
                l++;
                an--;
            }else{
                l++;
                bn--;
            }
            r++;
        }
    }
    if((r-l)>maxl) maxl=r-l;
    printf("%d", maxl);
    return 0;
}

编辑于 2019-04-13 10:50:44 回复(4)
def length(s, n, m):
    res = m                    # 初始化长度为m,因为即使是把前m个字符全改成a或b也没问题
    num_a = s[:m].count("a")   # 记录a的个数
    num_b = m - num_a          # 记录b的个数
    start = 0                  # 记录起始下标
    for i in range(m, n):      # 开始遍历
        if s[i]=='a':
            num_a += 1         # 更新a的个数
        else:
            num_b += 1         # 更新b的个数
        if min(num_a, num_b) <= m:    # 这种情况说明m个替代操作内可以使字符串变成一种
            res = max(res , i-start+1)# 以s[i]结尾的情况下的最大长度为i-start+1
        elif s[start] == 'a':  # 当a和b的长度都超过m时,起点必须要变才能使m个操作内的替代成立
            num_a -= 1         # 如果起点位置为a,则更新a的个数
            start += 1         # 更新起点位置
        else:
            num_b -= 1         # 如果起点位置为a,则更新a的个数
            start += 1         # 更新起点位置
    return res
n,m = map(int, input().split(' '))
s = input()
print(length(s, n, m))

发表于 2019-08-19 16:17:15 回复(0)
# O(n)复杂度的解法
def main(s,m):

    a_index = [i for i in range(len(s)) if s[i] == 'a']
    b_index = [i for i in range(len(s)) if s[i] == 'b']
    a_index = [-1] + a_index + [len(s)]
    b_index = [-1] + b_index + [len(s)]
    if len(a_index)-2 <= m or len(b_index)-2 <= m:
        return len(s)
    else:
        max_a = [a_index[i+m]-a_index[i-1]-1 for i in range(1,len(a_index)-m)]
        max_b = [b_index[i+m]-b_index[i-1]-1 for i in range(1,len(b_index)-m)]
        return max(max_a+max_b)

n,m = list(map(int,input().strip().split()))
s = input().strip()

print(main(s,m))
发表于 2019-06-02 11:42:02 回复(0)
#include <bits/stdc++.h>
using namespace std;
int presuma[50005];
int presumb[50005];
int main() {
    int n, m; cin >> n >> m;
    string s; cin >> s;
    for (int i=0; i<n; i++) {
        if (s[i] == 'a') {
            presuma[i+1] = presuma[i] + 1;
            presumb[i+1] = presumb[i];
        }
        else {
            presuma[i+1] = presuma[i];
            presumb[i+1] = presumb[i] + 1;
        }
    }
    int i=1, j=1, ans = 0;
    while(j <=n) {
        if (presuma[j] - presuma[i-1] <= m) {
            ans = max(ans, j-i+1);
            j++;
        } else {
            i++;
        }
    }
    i = 1; j = 1;
    while(j <=n) {
        if (presumb[j] - presumb[i-1] <= m) {
            ans = max(ans, j-i+1);
            j++;
        } else {
            i++;
        }
    }
    cout << ans << endl;
    return 0;
}
编辑于 2019-04-12 22:30:09 回复(1)
import java.util.Scanner;
public class Main {
    public static void main(String[] args)
    {
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            int n=scan.nextInt();
            int m=scan.nextInt();
            String s=scan.next();
            int a=get('a',n,m,s);
            int b=get('b',n,m,s);
            System.out.println(Math.max(a,b));
        }
    }
    public static int get(char ch,int n,int m,String s){
        int []data=new int[n+2];
        data[0]=-1;
        int poi=1;
        for(int i=0;i<n;i++){
            if(s.charAt(i)==ch){
                data[poi]=i;
                poi++;
            }
        }
        data[poi]=n;
        int ans=0;
        for(int i=0;i+m+1<=poi;i++){
            ans=Math.max(ans,data[i+m+1]-data[i]-1);
        }
        if(m>=poi)
            return n;
        else
            return ans;
    }
}

发表于 2019-04-11 15:19:45 回复(0)
## 19:45 -- 20:27
n, m = [int(x) for x in input().split()]
s = input()
max_a = 0
max_b = 0
a_index = []
b_index = []
for i in range(n):
    if s[i] == 'a':
        a_index.append(i)
    else :
        b_index.append(i)
if len(a_index) <= m or len(b_index) <= m :
    print(n)
else :
    for i in range(len(a_index) - m):
        if i == 0:
            temp = a_index[m]
            if temp > max_b :
                max_b = temp
        elif i == len(a_index) - m :
            temp = n - a_index[i]
            if temp > max_b :
                max_b = temp
                print(i)
        else :
            temp = a_index[m+i] - a_index[i-1] - 1
            if temp > max_b :
                max_b = temp
    
    for i in range(len(b_index) - m):
        if i == 0:
            temp = b_index[m]
            if temp > max_a :
                max_a = temp
        elif i == len(b_index) - m :
            temp = n - b_index[i]
            if temp > max_a :
                max_a = temp
        else :
            temp = b_index[m+i] - b_index[i-1] - 1
            if temp > max_a :
                max_a = temp
    print(max(max_a, max_b))

发表于 2019-02-17 20:27:55 回复(1)
a换b时:
1、遍历字符串,返回所有b的索引值,存为数组num=[num1,num2, , , ,]
2、取包含m个b的最大区间,num[i+m]-num[i-1]-1,注意首位处理
3、比较得到最大值
编辑于 2018-10-04 16:46:05 回复(3)
您的代码已保存
正在查询结果...

等到花儿都谢了
发表于 2020-02-18 22:28:43 回复(0)
典型的滑动窗口
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int oper = sc.nextInt();
        String str = sc.next();
        System.out.println(Math.max(solve(str, oper, len, 'a', 'b'), solve(str, oper, len, 'b', 'a')));
    }
    
    private static int solve(String str, int oper, int len, char swap, char src) {
        int i = 0, j = 0;
        int c = 0;
        int ans = Integer.MIN_VALUE;
        while (j < len) {
            if(c < oper) {
                if(str.charAt(j) == src) {
                    j++;
                } else {
                    c++;
                    j++;
                }
                ans = Math.max(ans, j - i + 1);
                continue;
            }

            if(str.charAt(j) == src) {
                ans = Math.max(ans, j - i + 1);
                j++;
                continue;
            }

            while (i < len && i < j && str.charAt(i) == src) {
                i++;
            }

            if(str.charAt(i) == swap) {
                i++;
            }

            ans = Math.max(ans, j - i + 1);
            j++;
        }

        return ans;
    }

}


发表于 2019-10-11 00:41:18 回复(0)
//按照第一名的思路写了一遍
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            CAL(sc);
        }
    }
    public static void CAL(Scanner sc){
        int n=sc.nextInt();
        int m=sc.nextInt();
        String s=sc.next(); 
        System.out.println(Math.max(CC(s,m,n,'a'),CC(s,m,n,'b')));
    }
    public static int CC(String s,int m,int n,char cha) {
        ArrayList<Integer> arr=new ArrayList<>();
        arr.add(0);
        for(int i=0;i<s.length();i++) {
            if (s.charAt(i)==cha) {
                arr.add(i+1);
            }
        }
        arr.add(s.length()+1);
        Integer[] A=arr.toArray(new Integer[] {});
        if(m>=A.length-2) {
            return s.length();
        }
        int max=0;
        for (int i=m+1;i<A.length;i++) {
            if(A[i]-A[i-m-1]-1>max) {
                max=A[i]-A[i-m-1]-1;
            }
        }
        return max;     }
}

发表于 2019-06-25 11:29:42 回复(0)
#include<iostream>
#include<deque>
#include<string>
using namespace std;
int main(){
    int n,m;cin>>n>>m;
    string s;cin>>s;
    deque<char> dq;
    //以a为子串
    int max=0,t=m;
    for(int i=0;i!=n;++i){
        if(s[i]=='a'){
            dq.push_back(s[i]);
        }
        else{
            if(t){
                dq.push_back(s[i]);
                t--;
            }
            else{
                while(dq.front()=='a') dq.pop_front();
                dq.pop_front();
                dq.push_back(s[i]);
            }
        }
        if(dq.size()>max)max=dq.size();
    }
    //以b为子串
    dq.clear();t=m;
    for(int i=0;i!=n;++i){
        if(s[i]=='b'){
            dq.push_back(s[i]);
        }
        else{
            if(t){
                dq.push_back(s[i]);
                t--;
            }
            else{
                while(dq.front()=='b') dq.pop_front();
                dq.pop_front();
                dq.push_back(s[i]);
            }
        }
        if(dq.size()>max)max=dq.size();
    }
    cout<<max;
}
发表于 2019-05-05 10:33:25 回复(0)

链接:https://blog.csdn.net/ansizhong9191/article/details/88365647

以b替换a为例,记录每一个b的位置,那么将连续m个b的置换为a必然存在最长的字串。对索引为i的b而言,将前面m个b置换为a,此时索引为i的b与索引为i-m-1的b之间的字串的长度为loc[i] - loc[i-m-1]-1。初始化时,i从m+1开始,因为前面不足m个b的时候,只要全部置为a即可。

``` python
def change(alpha):  
    loc = list() # loc存的是当前字符是ALPHA的位置  
    for i in range(len(s)):  
        if s[i] == alpha:  
            loc.append(i)
    loc.append(n) # 最后一个alpha以后的另一种字符情况也要计算,所以要加上len(s)              
    length = loc[m] # 当所有字符都为alpha是,最大的连续字符情况是m,所以说长度一定大于m\  
    for i in range(m + 1, len(loc)):          
        length = max(length, loc[i] - loc[i - m] - 1) 
    return length
n, m = list(map(int, input().split()))
s = input() print(max(change('a'), change('b')))

```

发表于 2019-04-12 13:07:09 回复(0)

#include<set>
#include<math.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<math.h>
#include<queue>
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{vector<int>a;
 vector<int>b;
 string s;
 int n,m;
 while(cin>>n>>m>>s)
 {a.clear();
  b.clear();
  int max=0;
  int maxu=0;
  a.push_back(0);
  b.push_back(0);
   for(int i=0;i<s.size();i++)
   {if(s[i]=='a')
       a.push_back(i+1);
       else b.push_back(i+1);
 }
  a.push_back(s.size()+1);
  b.push_back(s.size()+1);
 // cout<<s<<endl;
 // for(int i=0;i<a.size();i++)cout<<a[i]<<' ';
  //cout<<endl;
  if(m>=a.size()||m>=b.size())
  {max=s.size();
  }
  else{
      for(int i=0;i<a.size();i++)
      {if(i+m+1>a.size()-1)break;
       maxu=a[i+m+1]-a[i]-1;
       //   cout<<maxu<<' ';
       if(maxu>max)max=maxu;
      }
        for(int i=0;i<b.size();i++)
      {if(i+m+1>b.size()-1)break;
       maxu=b[i+m+1]-b[i]-1;
    
       if(maxu>max)max=maxu;
      }
  }
  cout<<max<<endl;
}
 return 0;
}
发表于 2019-04-10 10:13:33 回复(0)
我用两重循环查找,复杂度太大,跑出来70%案例。看了下大家的代码才明白,原来用下标计算长度更简单,不需要一个一个查找相加。
发表于 2019-04-09 22:32:44 回复(0)
增加一个指针(int 变量),从头扫过去,遇到'b'就 ”变一下”,如果变不了,那么把 l 指针往右移,直到遇到 'b',再把 'b' ”变回来” 即可。
上面是使 ‘a’ 最多的方法,求 'b' 最多反过来即可。
取个最大值就做完了。
#include <bits/stdc++.h>
#define QAQ 0x3f3f3f3f
using namespace std;
int main()
{
    int l,n,m,i,ans=0,num,buff;
    char s[50001];
    scanf("%d %d",&n,&m);
    scanf("%s",s);
    buff=m;
    l=0;
    num=0;
    for(i=0;s[i]!='\0';i++)
    {
        if(s[i]=='a')
        {
            num++;
        }
        else
        {
            if(buff==0)
            {
                while(l!=i&&s[l]!='b')
                {
                    l++;
                    num--;
                }
                l++;
            }
            else
            {
                buff--;
                num++;
            }
        }
        ans=max(ans,num);
    }
    buff=m;
    l=0;
    num=0;
    for(i=0;s[i]!='\0';i++)
    {
        if(s[i]=='b')
        {
            num++;
        }
        else
        {
            if(buff==0)
            {
                while(l!=i&&s[l]!='a')
                {
                    l++;
                    num--;
                }
                l++;
            }
            else
            {
                buff--;
                num++;
            }
        }
        ans=max(ans,num);
    }
    printf("%d",ans);
    return 0;
}

编辑于 2019-04-10 14:20:28 回复(0)
谁能完整解答下公式是怎么出来的
发表于 2019-03-31 11:27:40 回复(1)
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
public class Main{
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        if(n==1){
            System.out.println(1);
            return;
        }
        String str=sc.next();
        List<Integer> list_a=new ArrayList<Integer>();
        List<Integer> list_b=new ArrayList<Integer>();
        for(int i=0;i<n;i++){
            char s=str.charAt(i);
            if(s=='a'){
                list_a.add(i);
            }
            else{
                list_b.add(i);
            }
        }
        int max=0;
        max=Math.max(findMax(list_a,m,n),findMax(list_b,m,n));
        System.out.println(max);
           
    }
    public static int findMax(List<Integer> list,int m,int n){
        if(m>=list.size()){
            return n;
        }
        list.add(n);
        int max=0;
        max=list.get(m);
        for(int i=m+1;i<list.size();i++){
            max=Math.max(max,list.get(i)-list.get(i-m-1)-1);
        }
        return max;
    }
}
发表于 2019-03-30 16:59:33 回复(0)
while True:
    try:
        line = list(map(int, input().split()))
        n, m = line[0], line[1]
        s = input()
        i, j = 0, 0
        countA, countB = 0, 0
        if s[0] == "a":
            countA += 1
        else:
            countB += 1
        res = 0
        while i <= j and j < n - 1:
            if countA <= m or countB <= m:
                res = max(res, j-i+1)
                j += 1
                if s[j] == "a":
                    countA += 1
                else:
                    countB += 1
            else:
                i += 1
                if s[i-1] == "a":
                    countA -= 1
                else:
                    countB -= 1
        print(res)
    except:
        break

发表于 2019-03-14 15:33:34 回复(0)
n, m = map(int, input().strip().split())
str_n = list(input().strip())


def find_best_sub_string(char_digit):  # 变成char_digit后的最长子串
    lst = [-1]
    for i in range(len(str_n)):
        if str_n[i] != char_digit:
            lst.append(i)
    lst.append(len(str_n))
    if len(lst) - 2 <= m:
        return len(str_n)
    else:
        max_length = 0
        for j in range(1, len(lst) - m):
            if max_length < (lst[j + m] - lst[j - 1] - 1):
                max_length = lst[j + m] - lst[j - 1] - 1
        return max_length


print(max(find_best_sub_string('a'), find_best_sub_string('b')))
发表于 2019-02-20 10:45:44 回复(0)