首页 > 试题广场 >

幸运N串-研发

[编程题]幸运N串-研发

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

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

输入描述:

输入的第一行是一个正整数T（0 < T <= 20），表示有T组测试数据。对于每一个测试数据包含一行大写字符串S（0 < |S| <= 50000，|S|表示字符串长度）。

数据范围：

20%的数据中，字符串长度不超过100；

70%的数据中，字符串长度不超过1000；

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

输出描述:

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

示例1

输入

3
NNTN
NNNNGGNNNN
NGNNNNGNNNNNNNNSNNNN

输出

4
10
18

算法知识视频讲解

offer怎么这么难

基础的动态规划

import java.util.Scanner;

/**
 * @author lihaoyu
 * @date 2019/12/29 10:48
 */
public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        for (int t = 0; t < T; t++) {
            String string = scanner.next();
            int[] dp1 = new int[string.length() + 1];
            int[] dp2 = new int[string.length() + 1];
            int[] dp3 = new int[string.length() + 1];
            for (int i = 0; i < string.length(); i++) {
                if (string.charAt(i) != 'N') {
                    dp1[i + 1] = 0;
                    dp2[i + 1] = dp1[i] + 1;
                    dp3[i + 1] = dp2[i] + 1;
                } else {
                    dp1[i + 1] = dp1[i] + 1;
                    dp2[i + 1] = dp2[i] + 1;
                    dp3[i + 1] = dp3[i] + 1;
                }
            }

            int max = 0;
            for (int i = 0; i < dp3.length; i++) {
                max = Math.max(max, dp3[i]);
            }
            System.out.println(max);
        }
    }

}

发表于 2019-12-29 10:58:56 回复(2)

lpossible

#include<iostream>
#include<string>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        int n=s.length();
        int count=2;
        int k=0;
        int maxlen=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='N')
            {
                k++;
            }
            else
            {
                if(count)
                {
                    k++;
                    count--;
                }
                else
                {
                    count=2;
                    i=i-k;
                    k=0;
                }
            }
            if(maxlen<k) maxlen=k;
        }
        if(maxlen<k) maxlen=k;
        cout<<maxlen<<endl;
    }
    
}

发表于 2021-03-19 16:44:58 回复(0)

Crazyfrog

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    int t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        string s;
        cin>>s;
        int m=2;
        int r=0,sum=0;
        int add[2]={0};
        for(auto &c:s)
        {
            if(c=='N')
                sum++;
            else if(m>0)
            {
                add[m-1]=sum;
                sum++;
                m--;
            }
            else
            {
                sum-=add[1];
                add[1]=add[0]-add[1]-1;
                add[0]=sum-1;
            }
            r=max(r,sum);
        }
        cout<<r<<endl;
    }
}

编辑于 2019-12-30 22:45:26 回复(0)

秃娃

num_of_test = int(input())
for _ in range(num_of_test):
    string = input()
    window = []
    res = 0
    if len(string) - string.count('N') <= 2:
        print(len(string))
    else:
        for i in string:
            window.append(i)
            while len(window) - window.count('N') > 2:
                window.pop(0)
            res = max(res, len(window))
        print(res)

参考楼上的（牛客864355626号）的答案。

编辑于 2020-08-10 13:18:14 回复(0)

牛客864355626号

# python3

number = input()
for i in range(int(number)):
    a = input()
    b = []
    c = 0
    for j in a:
        b.append(j)
        if len(b) - b.count('N') >= 3:
            b.pop(0)
        c = max(c, len(b))
    print(c)

发表于 2019-12-29 16:44:49 回复(3)

tap4fun内推

动态规划，稍微优化了下，只保存前一个数据，以及最大的数据

#include <iostream>
using namespace std;

int main(){
    int T;
    cin >> T;
    while(T > 0){
        string s; cin >> s;
        int count = 0;
        // 保存修改一次和两次后N长度的最大值
        int mTime1 = 0,mTime2 = 0;
        // 此时修改一次或两次后的长度
        // 取代dp数组
        int time1 = 0, time2 = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == 'N'){
                ++count; ++time1; ++time2;
            }
            else{
                // 遇到的不是N，如果此时要修改且之前改了一次，那么time2和time1有关；如果此时要修改且之前为用修改次数，那么time1和count有关。
                time2 = time1 + 1;
                time1 = count + 1;
                count = 0;
            }
            mTime1 = mTime1 > time1 ? mTime1 : time1;
            mTime2 = mTime2 > time2 ? mTime2 : time2;
        }
        cout << mTime2 << endl;;
        --T;
    }
    return 0;
}

发表于 2020-04-03 15:48:20 回复(0)

一个大番茄z

cpp 双指针滑动窗口

#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    while(n--){
        string s;
        cin>>s;
        int cnt=0,_max=0;
        for(int i=-1,j=0;j<s.length();j++){
            if(s[j]!='N') cnt++;
            while(cnt>2) if(s[++i]!='N') cnt--;
            _max=max(_max,j-i);
        }
        cout<<_max<<endl;
    }
}

发表于 2021-03-29 20:21:27 回复(0)

CrazyMario

双指针滑窗：

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int T;
    cin >> T;
    while(T--){
        string s;
        cin >> s;
        int count = 0;
        int res = 0;
        int change = 2;
        int slow = 0;
        for(int  i = 0;i < s.size();i++){
            if(s[i] != 'N'){  //
                if(change){
                   change--;
                }else{ // change == 0 , s[i] != 'N'  //窗口缩小
                    while (slow < i && s[slow] == 'N')  slow++;
                    slow++;
                }
            }
            count = i-slow+1;
            res = max(res,count);
        }
        cout << res << endl;
    }
    return 0;
}

编辑于 2022-08-18 14:58:05 回复(0)

C/C++

蓬岐

双指针滑动

#include<iostream>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        string str;
        cin>>str;
        int i = 0;
        int count = 0;
        int num = str.size();
        int localmax = 0;
        for(int j = 0; j < num; j++){
            if(str[j] != 'N'){
                
                count++;
            }
            
            while(count>2){
                if(str[i] != 'N'){
                    count--;                  
                }
                i++;
            } 
            if(j-i+1 > localmax){
                localmax = j-i+1;
            }
        }
        cout<<localmax<<endl;
        
    }
}

发表于 2022-08-15 21:35:44 回复(0)

C/C++

西北向长安

统计并保存字符串中非N字符出现的位置，根据非N字符的位置遍历判断最长结果，时间复杂度2n。
#include<stdio.h>
#include<vector>
#include<string>
#include<algorithm>
#include<iostream>
using namespace std;
int res(string s){
    int length = s.size();
    vector<int> temp; //记录非 N 字符的位置
    for(int i = 0;i < length;++i){
        if(s[i] != 'N')
            temp.emplace_back(i);
    }
    if(temp.size() <= 2)  //最长N串是原字符串
        return length;
    int n = temp.size();
    int cnt = 0;
    cnt = max(temp[2],length - temp[n - 3] - 1);
    for(int j = 2;j < n - 1;++j){
        cnt = max(cnt,temp[j + 1] - temp[j - 2] - 1);
    }
    return cnt;
}
int main(){
    //按条件输入
    int n;
    vector<string> stringN;
    cin>>n;
    string s;
    cin.get();
    for(int i = 0;i < n;++i){
        getline(cin,s);
        stringN.emplace_back(s);
    }
    for(int i = 0;i < n;++i){
        cout<<res(stringN[i])<<endl;
    }
    return 0;
}

发表于 2022-03-16 20:37:19 回复(0)

文和906

这道题一个主要难点是数据的读入😓，可能是我基础不牢，在读取字符数据时遇到很多坑。最开始只接用cin，发现自动跳过了换行，把三组数据读成了一组，然后换成getchar()，每次读取也存在一定问题，最后使用了cin的格式控制方法，cin>>noskipws>>，总算是解决了问题。说实话这题本身不难，大部分时间都花在读数据上了。基础不牢，地动山摇。

然后解题的核心思想就是碰到不为N的字符就变换，用一个变量控制变换字符的次数，再用一个变量控制当变换次数超过2时，重新开始计算长度的位置。最终取得到的最长的长度即可。

这里需要注意每次重新计算长度的位置实际上就是上一轮计算中第一次碰到非N字符的位置，因为最长的情况必定是要变换字符的(只要入参中存在非N字符)。

#include <iostream>
#include <vector>
using namespace std;
 
int nextN(vector<char> vc,int i){
    for(int j = i+1;j < vc.size();j++){
        if(vc.at(j) == 'N'){
            return j;
        }
    }
    return -1;
}
 
int main(){
    int round = 0;
    cin>>round;
    for(int r = 0;r < round;r++){
        vector<char> vc;
        char tmp;
        if(r == 0){
            tmp = getchar();
        }
        while(cin>>noskipws>>tmp && tmp != '\n'){
            vc.push_back(tmp);
        }
        if(vc.size() == 0){
            cout<<0<<endl;
            break;
        }
        int lack = 0;
        int start = 0;
        int len = 0;
        int max = 0;
        for(int i = 0;i < vc.size();i++){
            if(vc.at(i)=='N'){
                len++;
            }
            else if(lack < 2){
                len++;
                lack++;
                if(lack == 1){
                    start = i;
                }
            }
            else{
                if(max < len){
                    max = len;
                }
                i = start;
                lack = 0;
                len = 0;
            }
        }
        if(max < len){
            max = len;
        }
        cout<<max<<endl;
    }
    return 0;
}

发表于 2021-09-23 15:31:20 回复(0)

Kpure1000

滑动窗口

#include <iostream>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        string strIn;
        cin >> strIn;
        int l = 0, r = 0, size = strIn.size(), exc = 0, maxs = 0;
        while (r < size)
        {
            if (strIn[r] != 'N')
            {
                ++exc;
                while (exc > 2 && l < r)
                {
                    if (strIn[l++] != 'N')
                        --exc;
                }
            }
            if (r - l + 1 > maxs)
            {
                // printf("%d -> %d, exc: %d, sum: %d\n", l, r, exc, r - l + 1);
                maxs = r - l + 1;
            }
            ++r;
        }
        printf("%d\n", maxs);
    }
}

不过上次在博客里还看到个更简单的解法

#include <bits/stdc++.h>
using namespace std;

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        string str;
        cin >> str;
        vector<int> res;
        int max = -1;
        for (int j = 0; j < str.size(); j++) {
            if (str[j] != 'N') res.push_back(j);
        }
        if (res.size() <= 2) cout << str.size() << endl;
        else
        {
            max = res[2];
            for (int k = 3; k < res.size(); k++) {
                max = (res[k] - res[k - 3] - 1) > max ? res[k] - res[k - 3] - 1 : max;
            }
            max = str.size() - res[res.size() - 3] - 1 > max ? str.size() - res[res.size() - 3] - 1 : max;
            cout << max << endl;
        }
    }
    return 0;
}

妙啊，直接跳过所有的N，加速了窗口的滑动，只不过占用了一点空间O(n)

发表于 2021-03-29 15:27:42 回复(0)

Allen_0x4bb

滑动窗口啰，leetcode上有原题

#include <bits/stdc++.h>

using namespace std;

int main() {
    int T;
    cin >> T;
    for (int i = 0; i < T; i++) {
        int N;
        cin >> N;
        int cnt[32] = {0};
        int res = 0;
        for (int j = 0; j < N;j++) {
            int num;
            cin >> num;
            int c = 0;
            while (num) {
                if (num & 1) c++;
                num = num >> 1;
            }
            if (++cnt[c] == 1) {
                res++;
            }
        }
        cout << res << endl;
    }
    return 0;
}

发表于 2021-03-12 18:32:22 回复(0)

牛客802680790号

直接观察各N串长度，然后找连续三个和最长的，再考虑特殊情况即可

import re
N = int(input())
for _ in range(N):
    s = input()
    s = (re.sub(r'[A-M]', 'O', s))
    s = (re.sub(r'[P-Z]', 'O', s))
    t = s.split("O")
    t = [len(i) for i in t]
    myans = 0
    if len(t)<3:
        temp = sum(t)+len(t)-1
        if temp>myans:
            myans=temp
     
    for i in range(len(t)-2):
        temp = t[i]+t[i+1]+t[i+2]+2
        if temp>myans:
            myans=temp
    print(myans)

发表于 2021-03-12 18:26:14 回复(0)

露西恩缇努维尔

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int T;
    string strT;
    getline(cin,strT);
    T=stoi(strT);
    while(T--)
    {
        string line;
        getline(cin,line);
        int l=0,r=0;
        int cnt=0,res=0;
        while(r<line.size())
        {
            if(line[r]!='N')
                cnt++;
            while(cnt>=3 && l<r)
            {
                res=max(res,r-l);
                cnt-=(line[l]!='N');
                l++;
            }
            r++;
        }
        res=max(res,r-l);
        cout<<res<<endl;
    }
    return 0;
}

发表于 2020-09-27 18:30:39 回复(0)

天一天一🎓

用动态规划属于小题大做。这道题的重点在于，必须移动出去两个挨着的非N字母，才有可能得到最大值，例如，a+b+c+d，你不可能让a+b或者c+d取到最大值，最大值一定在a+b+c或者b+c+d中取到，这样的话，就最适用于滑动窗口来解题了。

发表于 2020-09-09 22:39:33 回复(0)

Python

牛客961885550号

不用pop的方法
T = int(input())
for i in range(T):
    s = list(input())
    su = 0
    m = []
    for i in range(len(s)):
        if s[i] == 'N':
            su += 1
        else:
            m.append(i)
    if len(m) <= 2:
        print(len(s))
    else:
        length=[]
        length.append(m[2]+1)
        for k in range(1,len(m)-2):
                length.append((m[k + 2] - m[k-1]))
        length.append(len(s)-m[len(m)-3])
        print(max(length)-1)

编辑于 2020-09-04 21:03:00 回复(0)

在攒经验的考拉很放浪

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while(T>0){
            --T;
            String S = scan.next();
            System.out.println(longest(S));
        }
    }
    public static int longest(String S){
        ArrayList<Integer> list = new ArrayList();
        for(int i=0;i<S.length();i++)
            if(S.charAt(i)!='N')
                list.add(i+1);
        int max=0;
        if(list.size()<=2) return S.length();
        else if(list.size()==3){
            return max=Math.max(S.length()-list.get(0),list.get(2)-1);
        }else{
                        //非N字符＞3的情况
            for(int j=0;j<list.size();j++){
                                //上下界考虑
                if(j==0) max=Math.max(max,list.get(j+2)-1);
                else if(j==list.size()-2)//list.size()-1和list.size()-2即最后两个非N数都被化成N
                    return max=Math.max(max,S.length()-list.get(j-1));
                else
                                        //一般情况
                    max=Math.max(max,list.get(j+2)-list.get(j-1)-1);
            }
            return max;
        }
    }
}

考虑最长连续N字串长度，则可以从字符串中非N的个数和位置出发：

当存在非N字符≤2个时，则最长字串长度MaxLength=字符串长Length；
当非N字符为3个时，考虑上下界，则MaxLength=MAX(Length-第一个非N字符的位置，第三个非N字符位置-1)；
当非N字符＞3个，则一般情况下MaxLength=(MaxLength，当前非N字符位置的后一个非N字符位置-当前非N字符位置的前一个非N字符位置-1)，然后分别考虑上下界情况。

编辑于 2020-09-03 10:08:56 回复(0)

C/C++

一城烟雨柳色青

//滑动窗口思想， 但是卡在90过不去了，最后的例子也不显示哪里出错了，求大佬指出
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int n;
    while(cin >> n)
    {
        while(n--)
        {
            string s;
            cin >> s;
            int flag = 2,Max = 0,end = 1;
            vector<int> v(s.size()+1,0);
            //找到不为N的地方将它改为N，然后继续往后面找最长的N
            for(int start = 0; start < (int)s.size(); ++start)
            {
                //不为N且没被更改过
                if(s[start] != 'N' && v[start] == 0)
                {
                    --flag;
                    v[start] = 1;
                    if(flag < 0)
                        flag = 0;
                }
                if(start >= end)
                {
                    end += start - end + 1;
                }
                while(end < s.size())
                {
                    if(s[end] == 'N')
                        ++end;
                    //不为N且还能更改，标记更改位置
                    else if(s[end] != 'N' && flag > 0 && flag <= 2)
                    {
                        ++end;
                        v[end] = 1;
                        --flag;
                    }
                    else if(s[end] != 'N' && flag <= 0)
                        break;
                }
                Max = max(Max,(end - start));
                if(s[start] != 'N')
                {
                    ++flag;
                }
            }
            cout << Max << endl;
        }
    }
    return 0;
}

发表于 2020-08-23 18:34:13 回复(0)

ZhenK

for i in range(int(input())):
    s1 = input()
    #dic1 = {}
    answer = []
    if len(s1)<=2:
        print(len(s1))
    else:
        for i in range(len(s1)):
            count = 0
            num = s1[i]
            shuliang = 1
            index = i
            if i == len(s1)-1:
                pass
            #print(s1[i+1:])
            else:
                for j in s1[i+1:]:
                    #print(j)
                    if j != num and count <=2:
                        count +=1
                        shuliang +=1
                        answer.append(shuliang)
                    elif j == num and count <=2:
                        shuliang+=1
                        answer.append(shuliang)
                    elif index == (len(s1)-1):
                        answer.append(shuliang)
    print(max(answer))

我这个在本地是跑出来的，这里一直是报错，有没有大佬帮我看看哪里错了啊

发表于 2020-08-11 00:19:20 回复(0)