首页 > 试题广场 >

编程题2

[编程题]编程题2

热度指数：395 时间限制：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

输出

说明

把第一个 'b' 或者第二个 'b' 置成 'a'，可得到长度为 5 的全 'a' 子串。

算法知识视频讲解

Java

重洋

分别存储ab的下标数组，分别作为空洞来填补

1.空洞从第一个开始填

2.从最后一个往前填

3.i为空洞开始的坐标，从1开始且i+m-1+1<length, 两端坐标 i i+m-1 分别向两边移一位，即可求出当前最长字串，故

temp=arr.get(i+m)-arr.get(i-1)-1;

import java.util.*;

public class Main {

	public static void main(String[] args){
		
        ArrayList<Integer> aindex=new ArrayList<Integer>();
        ArrayList<Integer> bindex=new ArrayList<Integer>();
        int result=0;
        
		Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[] str=sc.next().toCharArray();
        for(int i=0;i<n;i++)
        {
            if(str[i]=='a')
                aindex.add(i);
            else
                bindex.add(i);
        }
        
        if(m>=aindex.size()||m>=bindex.size()){//这种情况下可以把所有字符全变成a或b
            result=str.length;
            System.out.println(result);
            return ;
        }
        
        ArrayList<Integer> arr;
        for(int j=0;j<=1;j++)
        {
            if(j==0)
                arr=aindex;
            else 
                arr=bindex;

            int head=arr.get(m);//从第一个字符开始
            int end=str.length-1-arr.get(arr.size()-m-1);//从最后一个字符往前          总串下坐标length-1减去倒数第m+1个空洞的下坐标
            result=result>head?result:head;
            result=result>end?result:end;
            //计算时，将i与i+m-1分别向左向右移一位
            for(int i=1;i+m<arr.size();i++){
            	//i+m-1   i
            	int temp=arr.get(i+m)-arr.get(i-1)-1;
                result=result>temp?result:temp;
            }
        }
        System.out.println(result);
	}
}

编辑于 2019-09-02 11:30:42 回复(0)