首页 > 试题广场 > 最长全1串
[编程题]最长全1串

给你一个01字符串,定义答案=该串中最长的连续1的长度,现在你有至多K次机会,每次机会可以将串中的某个0改成1,现在问最大的可能答案


输入描述:
输入第一行两个整数N,K,表示字符串长度和机会次数

第二行输入N个整数,表示该字符串的元素

( 1 <= N <= 300000
, 0 <= K <= N )


输出描述:
输出一行表示答案
示例1

输入

10 2 
1 0 0 1 0 1 0 1 0 1

输出

5
双指针,一次遍历!博客有粗略的讲解:https://blog.csdn.net/weixin_42564710/article/details/98513244
n,k = list(map(int,raw_input().split()))
num = list(map(int,raw_input().split()))
i,j =0,0
res = 0
while j<n:
    if num[j]==1:
        j += 1
    elif k > 0:
        k -= 1
        j += 1
    else:
        res = max(res,j-i)
        while i<j and num[i]==1:
            i += 1
        j += 1
        i += 1
res = max(res,j-i)
print(res)



发表于 2019-08-05 20:10:42 回复(0)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,k,x,s=0,l=1,r=1;
    cin>>n>>k;
    int a[n+1];
    a[0] = 0;
    for(int i=1;i<=n;i++){
        cin>>x;
        a[i] = a[i-1] + x;
    }
    while(r<=n){
        if((r-l+1)-(a[r]-a[l-1])<=k){
            s = max(s, r-l+1);
            r++;
        }else if(l<r)
            l++;
        else{
            l++;
            r++;
        }
    }
    cout<<s<<endl;
    return 0;
}

发表于 2019-09-16 08:03:09 回复(0)

双指针,时间复杂度O(N)
思路:
用left,right分别表示,满足翻转k次所能达到连续1的起始和结束位置

n,k = map(int, input().split())
l = list(map(int, input().split()))
left, right = 0, 0
res = 0
while right < n:
    if l[right] == 0:
        k -= 1
    if k == 0:
        res = max(res, right - left + 1)
    if k < 0:
        if l[left] == 0:
            k += 1
        left += 1
        while left < right and l[left] == 0:
            left += 1
            k += 1
    right += 1
print(max(res, right-left))
发表于 2019-08-23 20:25:42 回复(0)

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = scanner.nextInt();
        }
        int left = 0;
        int max = 0;
        for (int i = 0; i < N; i++) {
            if (nums[i] == 0) {
                K--;
                while (K < 0) {
                    if (nums[left] == 0) {
                        K++;
                    }
                    left++;
                }
            }
            max=Math.max(i-left+1,max);
        }
        System.out.println(max);
    }
}

发表于 2019-09-21 09:35:33 回复(0)
暴力解的话,考虑以0~n-k的字符开头的最长字符串长度,求出最大的路径。因为以0开头的字符串必定不会是最大的字符串长度,所以可以只考虑以1开头的字符串。
发表于 2019-08-09 10:54:00 回复(0)
#include<bits/stdc++.h>
 
usingnamespacestd;
constintmaxn = 3e5+10;
 
intsum[maxn];
intmain()
{
    intn,k,x;
    cin>>n>>k;
    for(inti = 1; i <= n; i++)
    {
        cin>>x;
        sum[i] = sum[i-1] + x;
    }
    intl = 1, r = 1 , ans = 0;
    while(r <= n) // 双指针尺取法一下 左右区间推进一下就行了
    {
        if((r - l + 1) - (sum[r] - sum[l - 1]) <= k)// 总数减去1的个数就是0的个数
        {
            ans = max(ans,r - l + 1);r++;continue;
        }
        elseif(l < r) l++;
        else{l++;r++;}
    }
    cout<<ans<<endl;
    return0;
}

发表于 2019-05-29 22:45:44 回复(0)

66.66%

编辑于 2019-05-13 20:09:38 回复(0)
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,tmp;
int main(){
    scanf("%d %d",&n,&m);
    int sum[n+1];
    sum[0]=0;
    for (int i=1;i<=n;++i) {
        scanf("%d",&tmp);
        sum[i]=sum[i-1]+tmp;
        //cout<<sum[i]<<endl;
    }
    int ans=m;
    int i=0,j;
    while (i<n){
        if (sum[i+1]-sum[i]>0){
            int j=ans+i;
            while (j<=n){
                if (j-i-sum[j]+sum[i]>m) break;
                ++j;
            }
            if (j!=n) --j;
            //cout<<j<<' '<<i<<endl;
            ans=max(ans,j-i);
        }
        ++i;
    }
    cout<<ans<<endl;
}

发表于 2019-05-09 15:30:22 回复(3)

热门推荐

通过挑战的用户

查看代码