首页 > 试题广场 > 最长全1串
[编程题]最长全1串
  • 热度指数:4303 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解

给你一个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 回复(2)
#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)
暴力解的话,考虑以0~n-k的字符开头的最长字符串长度,求出最大的路径。因为以0开头的字符串必定不会是最大的字符串长度,所以可以只考虑以1开头的字符串。
发表于 2019-08-09 10:54:00 回复(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)
#include <iostream>
(720)#include <cstdio>
#include <unordered_map>
using namespace std;

const int MAXN=300010;
int num[MAXN];
int num2[MAXN];
unordered_map<int,int> mp;
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++) scanf("%d",&num[i]);
    int cont=0;
    int mx=0;
    mp[0]=0;
    for(int i=0;i<n;i++)
    {
        if(num[i]) num2[i]=cont;
        else 
        {
            cont++;
            num2[i]=cont;
            mp[cont]=i;
        }
        if(cont >= k)
        {
            mx=max(mx,i-mp[cont-k]);
        }
        else
        {
            mx=max(mx,i+1);
        }
    }
    printf("%d\n",mx);
    return 0;
}
只需要维护一个当前位置之前0的个数就可以,如果当前位置之前的0大于k那么就找到第一个满足的位置的0用map查找总体复杂度on
发表于 2020-03-05 23:57:59 回复(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)

最长全1串

思路:维护一个最多有K个0存在的滑动窗口,用窗口中的元素数量(该窗口中所有0都可以变成1)更新答案。

因此,统计【0,i】区间内0的数量,到下标i的映射。i作为滑动窗口的右端点, 通过以下方式计算出滑动窗口的左端点,进而得到窗口内元素的数量(right - left + 1, 闭区间[left, right])。

如果当前0累计出现的次数不大于K次, 则可以将i左侧所有0变成1,左端点为0。

如果当前0累计出现次数(记为count)大于K次,我们只能最多将最近的K个0变成1,前count - k个0 无法变成1, 因此左端点为map.get(count-k) + 1。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] a = new int[n];
        for(int i=0; i < n; i++)  {
            a[i] = sc.nextInt();
        }
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0, count = 0;
        for(int i=0; i < n; i++) {
            if(a[i] == 0) {
                ++count;
                map.put(count, i); // 0的数量:当前位置
            }
            if(count > k) 
                res = Math.max(res, i-map.get(count-k));
            else
                res = Math.max(res, i+1);
        }
        System.out.println(res);
    }
}
编辑于 2020-06-24 13:24:02 回复(0)
暴力法:只有60
n, m = list(map(int,input().split()))
a = list(map(int,input().split()))

def Count(m,a):
    n = len(a)
    maxi = 0
    for i in range(n):
        if a[i] == 1:
            k = m
            for j in range(i+1,n):
                if a[j] == 0 and k != 0:
                    k -= 1
                elif (a[j] == 0 and k == 0)&nbs***bsp;j == n-1:
                    maxi = max(maxi,j-i)
                    break
    return maxi

print(Count(m,a))


双指针滑动窗口:也只有86.67,修改后ac了
n,k = list(map(int,input().split()))
num = list(map(int,input().split()))
def Count(k,num):
    i, j = 0, 0
    maxi = 0
    while j < n:
        if num[j] == 1:
            j += 1
        elif k > 0:
            k -= 1
            j += 1
        else:
            maxi = max(maxi,j-i)
            while i<j and num[i] == 1:
                i += 1
            i += 1
            j += 1
    maxi = max(maxi,j-i)
    return maxi

print(Count(k,num))


编辑于 2020-05-11 23:15:45 回复(0)
滑动窗口,感觉可以通过在最初记录下0的位置来优化。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @Author: coderjjp
 * @Date: 2020-05-10 22:26
 * @Description:
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int N = Integer.valueOf(s[0]);
        int K = Integer.valueOf(s[1]);
        String[] nums = br.readLine().split(" ");
        int ans = 0;
        int i = 0, j = 0;
        while (j < N){
            if ("1".equals(nums[j]))
                j++;
            else {
                if (K > 0){
                    K--;
                    j++;
                }else {
                    ans = Math.max(ans, j - i);
                    while ( i < j && nums[i].equals("1"))
                        i++;
                    i++;
                    j++;
                }
            }
        }
        System.out.println(Math.max(ans, j - i));
    }
}


编辑于 2020-05-11 10:27:39 回复(0)
没过,说是写的太复杂了🤔
#include <bits/stdc++.h>

using namespace std;

int main(){
	int n,k;
	cin>>n>>k;
	vector<int> num(n);
	for(int i=0;i<n;i++){
		cin>>num[i];
	}
	
	int count,max=0,t=k;
	for(int i=0;i<n;i++){
		k=t;
		count = 0;
		for(int j=i;j<n;j++){
			if(num[j] == 1){
				count++;
			}else if(k>0){
				k--;
				count++;
			}else{
				break;
			}
		}
		if(count>max)
			max = count;
	}
	cout<<max;
	
	return 0;
} 


发表于 2020-04-29 10:19:55 回复(0)
这种题目还不熟练,就是那种一看很简单,一写全bug,然后半小时过去了,然后一小时过去了,然后。。。贼特么烦。
n,k = map(int,input().split())
ss = ''.join(input().split())
i,j,max_value = 0,0,0
while j<len(ss):
    if ss[j] =='1':
        j+=1
    elif k>0:
        k-=1
        j+=1       
    else:
        if ss[i]=='0':
            k+=1
            i+=1
        else:
            i+=1
    max_value = max(max_value,j-i)
print(max_value)


编辑于 2020-04-22 20:20:29 回复(0)
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] nums = new int[N];
        for (int i=0;i<N;i++)
            nums[i] = sc.nextInt();
        int left = 0, right = 0;
        int res = 0;
        while (right < N){
            if (nums[right] == 0)
                K--;
            if (K == 0)
                res = Math.max(res, right - left + 1);
            if (K < 0) {
                if (nums[left] == 0)
                    K++;
                left++;
                while (nums[left] == 0 && left < right){
                    K++;
                    left++;
                }
            }
            right++;
        }
        res = Math.max(res, right - left);
        System.out.println(res);
    }
}
发表于 2020-03-24 16:05:07 回复(0)
#include<bits/stdc++.h>
using namespace std;


const int maxn = 3 * 1e5 + 10;
int n,k;
int a[maxn];
int main(){
#ifdef ONLINE_JUDGE
#else
	 freopen("E:/input.txt", "r", stdin);
#endif

    cin >> n >>k;
    vector<int> zeroPos;
    for(int i = 0; i < n; ++i)
    {
        cin >> a[i];
        if(a[i] == 0)
        {
            zeroPos.push_back(i);
        }
    }

    if(zeroPos.size() <= k)
    {
        cout << n << endl;
        return 0;
    }

    if(zeroPos.size() == n)
    {
        cout << k << endl;
        return 0;
    }

    int maxLen = 0;
    for(int i = 0; i < zeroPos.size()-k; ++i)
    {
        if(i == 0)
        {
            maxLen = zeroPos[i+k];
        }else
        {
            maxLen = max(maxLen,zeroPos[i+k] - zeroPos[i-1] - 1);
        }
    }

    cout << maxLen;



    return 0;
}




我看了很久博主的代码,但是博客代码中没有做说明,这里试着解释下:
整个代码的思路就是用vector记录所有0出现的位置,根据0的个数(记为num),可以分为三种情况,num 在(0,k],(k,n),[n,n]三个区间,第一个区间返回n,第二个区间使用滑窗(我也不是很懂滑窗,就看博主的代码说说自己的理解),第三个区间返回k,下面解释第二个区间情况。
当num大于k,又小于n时,循环只要到num-k即可结束,至于为什么可以接着看循环的代码,首先对于第一个0的位置,可以初始化maxlen = zeroPos[k],即将k个0改为1后可以得到的长度,后面代码zeroPos[i+k]表示第i个0,将该0和其后总共k个0改为1后的位置,扣掉第i-1个0的位置,(再减1可以自己画画就得出来了,我觉得是因为数组是从0开始数的),最后与maxlen取最大即可,不知道这种理解是否有问题
编辑于 2020-03-07 16:42:58 回复(0)
动态规划一直不太好,如果用暴力解的话,这样的动态规划可以行吗,在内存和时间允许的条件下。。。这个代码只过了6%,有没大神指点一波。
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, K;
    cin>>N>>K;
    int nums[N];
    for(int i=0; i<N; i++) cin>>nums[i];

    //int dp[N][K+1];
    //memset(dp, INT_MIN, sizeof(dp));
    vector<vector<int>> dp(N, vector<int>(K+1, INT_MIN));
    for(int i=0; i<N; i++)
    {
        if(i==0)
        {
            if(nums[0]==0) dp[i][0] = 0, dp[i][1] = 1;
            else dp[i][0] = 1;
        }
        else 
        {
            if(nums[i]==0)
            {
                dp[i][0] = 0;
                for(int j=1; j<=K; j++)
                {
                    dp[i][j] = dp[i-1][j-1]+1;
                }
            }
            else if(nums[i]==1)
            {
                dp[i][0] = dp[i-1][0]+1;
                for(int j=1; j<=K; j++)
                {
                    dp[i][j] = dp[i-1][j]+1;
                }
            }
        }
    }
    int ans = 0;
    for(int u=0; u<=K; u++) ans = max(ans, dp[N-1][u]);
    cout<<ans<<endl;
    return 0;
}
dp[i][j] i表示字符当前位置, j表示变化了多少次。


发表于 2019-12-25 11:38:20 回复(0)
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    vector<int>arr(n+1);
    int tmp;
    for(int i=1;i<=n;i++){
        cin>>tmp;
        arr[i]=arr[i-1]+tmp;
    }
    if(arr[n]>=(n-k)){
        cout<<n<<endl;
        return 0;
    }
    int m=0;
    int l=1,r=1;
    while(r<=n){
        if((r-l+1)-(arr[r]-arr[l-1])<=k){
            r++;
            continue;
        }
        r--;
        tmp=r-l+1;
        m=tmp>m?tmp:m;
        l++;
    }
    cout<<m<<endl;
    return 0;
}

发表于 2019-10-15 23:46:12 回复(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)

热门推荐

通过挑战的用户

查看代码