首页 > 试题广场 >

编程题2

[编程题]编程题2
  • 热度指数：1212 时间限制：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' 子串。
算法知识视频讲解
添加回答
bobbymly头像 bobbymly
编辑于 2018-02-17 09:25:05 回复(1)
FlushHip头像 FlushHip
今日头条2018校园招聘后端开发工程师(第四批)编程题 - 题解
http://blog.csdn.net/flushhip/article/details/79458502
详细解答，没有之一(自吹一波)

源码：https://github.com/FlushHip/AlgorithmnCode
发表于 2018-03-06 17:43:21 回复(0)
正在卷的三文鱼很讨厌吃香菜头像 正在卷的三文鱼很讨厌吃香菜 
import java.io.*;
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] strs1=br.readLine().split(" ");
        int n=Integer.parseInt(strs1[0]);
        int m=Integer.parseInt(strs1[1]);
        String s=br.readLine();
        int[] A=new int[n];
        int[] B=new int[n];
        A[0]=s.charAt(0)=='a'?1:0;
        B[0]=s.charAt(0)=='b'?1:0;
        for(int i=1;i<n;i++){
            if(s.charAt(i)=='a'){
                A[i]=A[i-1]+1;
                B[i]=B[i-1];
            }else{
                B[i]=B[i-1]+1;
                A[i]=A[i-1];
            }
        }
        int max=0;
        for(int k=0;k<n;k++){
            int i=0;
            int j=k;
            if(s.charAt(k)=='a'){
                while(i<j){
                    int mid=i+(j-i)/2;
                    if(func(B,mid,k,m)) j=mid;
                    else i=mid+1;
                }
            }else{
                while(i<j){
                    int mid=i+(j-i)/2;
                    if(func(A,mid,k,m)) j=mid;
                    else i=mid+1;
                }
            }
            max=Math.max(max,k-i+1);
        }
        System.out.println(max);
    }
    public static boolean func(int[] dp,int i,int j,int m){
        if(i==0){
            return dp[j]<=m;
        }else{
            return dp[j]-dp[i-1]<=m;
        }
    }
}
前缀和+二分，时间复杂度O(NlogN)
发表于 2020-02-26 21:36:32 回复(0)
java的神秘男友script头像 java的神秘男友script 
// 滑动窗口 +队列记录
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int m = in.nextInt();
            String str = in.next();
            int max = Math.max(getMax(str,'a',m),getMax(str,'b',m));
            System.out.println(max);
        }
     }
    // 统计变a和变b的最长长度
    public static int getMax(String str,char ch,int count){
        int max = 0;
        LinkedList ll = new LinkedList(); // 用于记录需要变换的字符的下标
        int len = str.length();
        int d = 0; // 窗口的大小
        for ( int i = 0; i < len; ++i ) {
            if (str.charAt(i) == ch) {
                d++;  // 不需替换的字符 窗口直接增大
            }else {
                if (count > 0) { // 需替换的字符且有剩余替换次数 窗口增大 次数减少1
                    d++; 
                    count--;    
                }else {  // 需替换的字符且没有剩余替换次数 则取出最左边被替换的字符的下标(index) 同时重新计算窗口大小[i-index]
                    int index = (int)ll.poll();
                    d = i - index;
                }
                ll.add(i); // 记录需要替换字符的下标
            }
            max = Math.max(d,max);
            
        }
        return max;
    }
}

发表于 2022-02-10 01:58:40 回复(0)
牛客74645407号头像 牛客74645407号 
//时间复杂度o（n）,使用滑动窗口的思想，维持左指针和右指针，窗口大小为反转次数用完后a或b的最大长度。
#include<vector>
#include<string>
#include<iostream>
using namespace std;


int inverse(string& str,int dept,char target){
    int left=0,right=-1,max_len=0,times=0;
    for(int i=0;i<str.size();i++){
        right++;
        if(str[i]!=target){
            times++;
            
            if(times>dept){
                max_len=max(max_len,right-left);
                while(left!=right && str[left]==target){
                    left++;
                }
                if(str[left]!=target){
                   left++;
                   times--;
                }
            }
        }
    }
    return max_len;
}

int main(){
    int lenght,dept;
    cin>>lenght>>dept;
    string str;
    cin>>str;
    int max_a=inverse(str,dept,'a');
    int max_b=inverse(str,dept,'b');
    cout<<max(max_a,max_b);
    return 0;
}

发表于 2021-09-10 10:46:44 回复(0)
清香的茉莉头像 清香的茉莉 
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();//吃空格
        String s = sc.nextLine();
        System.out.println(fun(s.toCharArray(),m));
    }
    static private int fun(char[] chars,int k){
        int res=0;
        int len = chars.length;
        int right=0,left=0;
        int[] window = new int[2];
        while (right<len){
            char cur = chars[right];
            window[cur-'a']++;
            res=Math.max(window[cur-'a'],res);//最大字母的出现次数
            while (res+k<right-left+1){
                window[chars[left]-'a']--;
                left++;
            }
            right++;
        }
        return len-left;
    }




发表于 2021-07-23 00:30:05 回复(0)
Mikeeeee头像 Mikeeeee
把字符串转换为字符串中相邻相同字符个数的数组，然后通过累加计算。
发表于 2020-09-06 09:43:13 回复(0)
有点小菜哦头像 有点小菜哦
时间复杂度O(N),空间复杂度O(N) 
import java.util.List;
import java.util.ArrayList;
import java.io.*;
public class Main{
       public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] strs1=br.readLine().split(" ");
        int n=Integer.parseInt(strs1[0]);
        int m=Integer.parseInt(strs1[1]);
        String s=br.readLine();
        int res = 0;
        List<Integer> aList = new ArrayList<>();
        List<Integer> bList = new ArrayList<>();
        aList.add(-1);
        bList.add(-1);
        for(int i=0;i<n;i++){
            if(s.charAt(i)=='a')aList.add(i);
            else bList.add(i);
         }
        aList.add(n);
        bList.add(n);
        for(int i=1;i<aList.size()- m;i++){
            int j = i+m-1;
            int t = aList.get(j+1) - aList.get(i-1)-1;
            if(t >res)res = t;
             
        }
        for(int i=1;i<bList.size()-m ;i++){
            int j = i+m-1;
            int t = bList.get(j+1) - bList.get(i-1)-1;
            if(t >res)res = t;
        }
        System.out.print(res);
    }
}


发表于 2020-06-07 18:24:23 回复(0)
_Edison头像 _Edison 
#include<cstdio>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    string str;
    cin>>str;
    //全A的情况
    int dpa[50001] = {0};
    if(str[0] == 'a'){
        for(int i=0;i<=m;i++){
            if(i%2 == 0)
                dpa[i] = 1;
            else
                dpa[i] = 0;
        }
    }else{
        for(int i=0;i<m;i++){
            if(i%2 == 0)
                dpa[i] = 0;
            else
                dpa[i] = 1;
        }
    }
    int maxa=0;
    for(int i=2;i<=n;i++){
        for(int j = m;j>=0;j--){
            if(str[i-1] == 'a'){
                dpa[j] = dpa[j]+1;
            }else{
                if(j>=1){
                    dpa[j] = dpa[j-1]+1;
                }else{
                    dpa[j] = 0;
                }
            }
            if(dpa[j]>maxa){
                maxa = dpa[j];
            }
            if(maxa == n)
                break;
           // printf("dpa[%d][%d] = %d\n",i,j,dpa[i][j]);
        }
        if(maxa == n)
                break;
    }
        int maxb=0;
    //全B的情况
    if(maxa<=n-maxa){
        int dpb[50001] = {0};
    if(str[0] == 'a'){
        for(int i=0;i<m;i++){
            if(i%2 == 0)
                dpb[i] = 0;
            else
                dpb[i] = 1;
        }
    }else{
        for(int i=0;i<=m;i++){
            if(i%2 == 0)
                dpb[i] = 1;
            else
                dpb[i] = 0;
        }
    }
    for(int i=2;i<=n;i++){
        for(int j = m;j>=0;j--){
            if(str[i-1] == 'b'){
                dpb[j] = dpb[j]+1;
            }else{
                if(j>=1){
                    dpb[j] = dpb[j-1]+1;
                }else{
                    dpb[j] = 0;
                }
            }
            if(dpb[j]>maxb){
                maxb = dpb[j];
            }
            if(maxb == n)
                break;
        }
        if(maxb == n)
                break;
    }
    }
     
    printf("%d",max(maxa,maxb));
     
    return 0;
         
}
动态规划加滚动数组，通过53%超时了。

直接二分法，对长度进行二分搜索，通过100% 
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
    int n,m;
    int countt[50005]={0};
int ans = 0;
bool check(int len){
    for(int i=0;i<n-len+1;i++){
         int cnta = countt[i+len-1]-countt[i-1];
         int cntb = len-cnta;
         if(min(cnta,cntb)<=m){
             return true;
         }
    }
    return false;
}
 
int main(){    
    cin>>n>>m;
        string str;
    cin>>str;  
    int h = 0;
    for(int i=0;i<n;i++){
        if(str[i]=='a'){
            h = h+1;
            countt[i] = h;
        }else
            countt[i] = h;
    }     
    int right = n,left = 1,mid;
        while(left<=right){
            mid = left+(right-left)/2;
            if(check(mid)){
                left = mid+1;
            }
            else{
                right = mid-1 ;
            }
        }
     
        printf("%d\n",right);
    return 0;
     
}
要注意二分边界的处理，最后要返回的是右边界，左边界不可以。

编辑于 2019-10-19 17:50:27 回复(0)
提交观点

问题信息

贪心 C++工程师 字符串 2018 字节跳动 Java工程师
上传者：小小
难度：
9条回答 5914浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号