首页 > 试题广场 >

最长全1串

[编程题]最长全1串
  • 热度指数:6339 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
给你一个 01 字符串,定义答案为该串中最长的连续 的长度,现在你有至多 k 次机会,每次机会可以将串中的某个 改成 ,现在问最大的可能答案

数据范围:字符串长度满足  ,保证输入的字符串只包含 0 和 1 ,

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

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


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

输入

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

输出

5
示例2

输入

10 5
1 0 0 1 0 1 0 1 0 1

输出

10
双指针,一次遍历!博客有粗略的讲解: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 回复(1)

双指针,时间复杂度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)
用双指针组成窗口,计算窗口内的最长全一串长度
n, k = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))
# calsum[i]表示区间[0, i]中有多少个1
calsum = [0]*n
calsum[0] = arr[0]
for i in range(1, n):
    calsum[i] = calsum[i - 1] + arr[i]
left = 0
maxLen = 0
for right in range(1, n):
    if right - left + 1 - (calsum[right] - (calsum[left - 1] if left > 0 else 0)) > k:
        # 如果[left, right]的区间中0的个数超过k了,就不能在此窗口通过k个更改操作内将0全部改为1
        left += 1
    maxLen = max(maxLen, right - left + 1)
print(maxLen)


发表于 2021-02-02 12:51:26 回复(0)
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }
        int res = getAns(arr, N, K);
        System.out.println(res);
    }

    public static int getAns(int[] arr, int N, int K) {
        int left = 0, right = 0, res = 0;
        while (right < N) {
            if (arr[right] == 0)
                K--;
            while (K < 0) {
                if (arr[left] == 0)
                    K++;
                left++;
            }
            res = Math.max(res, right - left + 1);
            right++;
        }
        return res;
    }
}

发表于 2020-08-13 23:25:35 回复(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)
package main

import (
	"fmt"
)

func main() {
	n, k := 0, 0
	fmt.Scan(&n, &k)
	str := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scanf("%d", &str[i])
	}

	right, left, count, res, num := 0, 0, 0, 0, 0
	for ; right < n; right++ {
		if str[right] == 0 {
			num++
			count++
		}
		if count > k {
			if str[left] == 0 {
				count--
			}
			left++
		}
		if count == k && right-left+1 > res {
			res = right - left + 1
		}
	}

	if num <= k {
		res = n
	}
	fmt.Println(res)
}

发表于 2022-09-15 23:20:08 回复(0)
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	var n, k int
	fmt.Scan(&n, &k)
	reader := bufio.NewReader(os.Stdin)
	str, _ := reader.ReadString('\n')
	str = str[:len(str)-1] //去掉换行符
	strSlice := strings.Split(str, " ")
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i], _ = strconv.Atoi(strSlice[i])
	}
	l, r, ans := 0, 0, 0
	for r < n {
		if arr[r] == 1 {
		} else if k > 0 {
			k--
		} else {
			for arr[l] == 1 {
				l++
			}
			l++
		}
		if r-l+1 > ans {
			ans = r - l + 1
		}
		r++
	}
	fmt.Println(ans)
}

发表于 2022-08-05 14:34:33 回复(0)
双指针滑动窗口,通过100%测试
# include <iostream>
# include <vector>

//双指针滑动窗口
int main(int argv, char* argc[]){
    int n, k;
    int item;
    std::vector<int> numbers;
    std::cin >> n >> k;
    for (int i =0; i< n; ++i){
        std::cin>>item;
        numbers.push_back(item);
    }
    while(numbers.back() == 0 && numbers.size() > k)
        numbers.pop_back();
    n = numbers.size();
    int max_len = 0;
    int l = 0, r = 0;
    for (r = 0; r < n; ++r){
        if((numbers[r] == 1))
            continue;
        if(k > 0){
            --k;
            continue;
        }
        //得到一个全1字串,更新max_len
        if (max_len < (r - l))
            max_len = r-l;
        //更新l,进入下个循环
        if (numbers[l] == 0)
            while(numbers[l] == 0 && l <= r){
                ++l;
                ++k;
            }
        else{
            while(numbers[l] == 1 && l <= r)
                ++l;
            while(numbers[l] == 0 && l <= r){
                ++l;
                ++k;
            }
        }
        //抵消++r
        --r;
    }
    
    //最后再更新一下
    if (max_len < (r - l))
        max_len = r-l;
    std::cout<< max_len<< '\n';
    return 0;
}


发表于 2022-04-08 15:21:35 回复(0)
#include <iostream>
#include <vector>

int main() {
    int N, K;
    std::cin >> N >> K;
    std::vector<int> nums(N, 0);
    for(int i = 0; i < nums.size(); i++) {
        std::cin >> nums[i];
    }
    
    int left = 0, right = 0;
    int count = 0, maxLen = 0;
    for(; right < nums.size(); right++)
    {
        if(nums[right] == 0) count++;
        
        while(count > K) {
            if(nums[left] == 0) --count;
            left++;
        }
        
        maxLen = std::max(maxLen, right - left + 1);
    }
    
    std::cout << maxLen << std::endl;
    
    return 0;
}

发表于 2021-06-29 16:33:19 回复(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[] bits = new int[n];
        for(int i = 0; i < n; i++){
            bits[i]=sc.nextInt();
        }
        int res = 0;
        int left = 0;
        int right = 0;
        while(left < n && right < n){
            while(right < n && (bits[right]==1 || k > 0)){
                if(bits[right]==0){
                    k--;
                }
                right++;
            }
            res = Math.max(right - left, res);
            if(bits[left]==0){
                k++;
            }
            left++;
        }
        System.out.println(res);
    }
}

发表于 2021-03-17 15:55:31 回复(0)
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader rf=new BufferedReader(new InputStreamReader(System.in));
        String s;
        while((s=rf.readLine())!=null){
            String[] de=s.split(" ");
            int n=Integer.valueOf(de[0]);
            int k=Integer.valueOf(de[1]);
            if(n<k){
                System.out.println(n);
                return;
            }
            String[] fr=rf.readLine().split(" ");
            int[] res=new int[n];
             
            for(int i=0;i<n;i++){
                res[i]=Integer.valueOf(fr[i]);
            }
            int left=0,right=0;
            int count=0;
            int max=0;
            while(right<n){
                if(res[right]==1){
                    count++;
                }
                if(count+k>=n){
                    System.out.println(n);
                    return;
                }
                if(count+k<right-left+1){
                    max=Math.max(count+k,max);
                    if(left<right){
                        if(res[left]==1){
                            count--;
                        }
                          left++;
                        
                    }
                    while(left<right&&res[left]==0){
                        left++;
                    }
                }
                right++;
            }
             System.out.println(max);
        }
}
}

发表于 2020-08-14 20:49:15 回复(0)

#include <iostream>
#include <vector>
#include <string>
using namespace std;
const int N = 300010;
int num[N];

int max(int a, int b)
{
	if (a >= b)
		return a;
	else
		return b;
}

int main()
{
	int n, m;
	cin >> n >> m;
	for (int i = 0; i<n; i++) 
		cin >> num[i];
	vector<int> Hash(2, 0);
	int res = 0, maxNum = 0;
	for (int i = 0, j = 0; j<n; j++) 
	{
		Hash[num[j]]++;
		maxNum = max(maxNum, Hash[1]); // 这里变为区间中1的个数
		while (j - i + 1 - maxNum>m)
			Hash[num[i++]]--;
		res = max(res, j - i + 1);
	}
	cout << res << endl;
}

发表于 2020-08-06 14:21:09 回复(2)

最长全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-09-06 12:12:59 回复(1)
滑动窗口,感觉可以通过在最初记录下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)

热门推荐

通过挑战的用户

查看代码