20190811163816

Posted on by mannuan One min read
Table of Contents

题目描述:

小A很喜欢字母N，他认为连续的N串是他的幸运串。 有一天小A看到了一个全部由大写字母组成的字符串， 他被允许改变最多2个大写字母（也允许不改变或则只改变1个大写字母）， 使得字符串中所包含的最长的连续的N串的长度最长，你能帮助他吗？

输入描述:

输入的第一行是一个正整数T(0 对于每一个测试数据包含一行大写字符串S (0<|S|<50000, |S|表示字符串长度)。

数据范围:

20%的数据中，字符串长度不超过100;
70%的数据中，字符串长度不超过1000;
100%的数据中，字符串长度不超过50000。

输出描述:

对于每一组测试样例，输出一个整数，表示操作后包含的最长的连续N串的长度

示例1:

输入:

3
NNTN
NNNNGGNNNN
NGNNNNGNNNNNNNNSNNNN

输出:

4
10
18

import java.util.*;
public class Test02 {
    private static int findLargeSeq2(char[] arr) {
        int max_len = 0;
        int curr_max_len = 0;
        int max_low = 0;
        int max_high = 0;
        for(int i=0;i<arr.length;i++){
            if("N".equals(arr[i]+"")){
                curr_max_len ++;
            }else{
                if(max_len < curr_max_len){
                    max_len = curr_max_len;
                    max_low = i-max_len;
                    max_high = max_low+max_len-1;
                }
                curr_max_len = 0;
            }
        }
        int not_N_count = 0;
        int i=0;
        for(i=max_high+1;i<arr.length&&not_N_count<=2;i++){
            if(!"N".equals(arr[i]+"")){
                not_N_count ++;
            }
        }
        int search_high = i-2;
        not_N_count = 0;
        i=0;
        // System.out.println(arr[max_low-1]);
        for(i=max_low-1;i>=0&&not_N_count<=2;i--){
            if(!"N".equals(arr[i]+"")){
                not_N_count ++;
            }
        }
        int search_low = i+2;
        not_N_count = 0;
        int[] not_N_arr = new int[4];
        for(i=search_low;i<=search_high;i++){
            if(!"N".equals(arr[i]+"")){
                not_N_arr[not_N_count] = i;
                not_N_count++;
            }
        }
        curr_max_len = 0;
        max_len = 0;
        for(i=0;i<not_N_arr.length-1;i++){
            for(int j=search_low;j<=search_high;j++){
                if(!"N".equals(arr[j]+"")&&(j==not_N_arr[i])){
                    curr_max_len = 1;
                }else if(!"N".equals(arr[j]+"")&&(j!=not_N_arr[i])&&(j!=not_N_arr[i+1])){
                    curr_max_len -= 1;
                    break;
                }
                curr_max_len++;
            }
            if(curr_max_len > max_len){
                max_len = curr_max_len;
            }
        }
        // for(i=0;i<not_N_arr.length;i++){
        //     System.out.println(not_N_arr[i]);
        // }
        // System.out.println(search_low);
        // System.out.println(search_high);
        // System.out.println(max_low);
        // System.out.println(max_high);
        return max_len;
    }
    public static void main(String[] args) {
        // String a = "NNNGNNNNNGNNNNGNNNNNNNNSNNNNSNNNNNSS";
        String a = "NGNNNNGNNNNNNNNSNNNN";
        char [] arr = a.toCharArray();
        // System.out.println(arr.length);
        int len = findLargeSeq2(arr);
        System.out.println(len);
    }
}