首页 > 试题广场 >

最长全1串

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

数据范围：字符串长度满足  ，保证输入的字符串只包含 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
算法知识视频讲解
添加回答
Java
牛客35031561号头像 牛客35031561号

最长全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)
Java
何止hz头像 何止hz
滑动窗口，感觉可以通过在最初记录下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)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 贪心 美团 2019 Java工程师
来自：美团2019年秋招部分...
上传者：小小
难度：
3条回答 13248浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最长全1串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号