0%

美团技术笔试——最长全1串

发表于 更新于 阅读次数： Valine：
本文字数： 493 阅读时长 ≈ 1 分钟

题目描述

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

输入描述:
1
2
3
4
5
6
输入第一行两个整数N,K，表示字符串长度和机会次数

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

( 1 <= N <= 300000
, 0 <= K <= N )
输出描述:
1
输出一行表示答案
输入例子1:
1
2
10 2 
1 0 0 1 0 1 0 1 0 1
输出例子1:
1
5

解题思路

​ 首先应该分几种情况进行分类讨论：

1.当K>N时，输出应该直接为K

2.当K<N，如果K等于0，结果直接为最长连续1子串长度

​ 如果K不等于0，那么需要进行动态滑动窗口实验

滑动窗口实验思路为：

​ 1.首先计算不进行替换时，最长连续1子串长度，即为max

​ 2.设置初始值

​ 滑动窗口大小初始值 slide = max+K

​ 滑动窗口最大和初始值 slide_sum = max

​ 3.使用当前滑动窗口大小进行扫描数据，看是都存在一个滑动窗口内的和超过当前滑动窗口最大和

​ 如果有，那么说明存在更大的连续子串，因此将silde和silde_sum都加1(在初始值时已经设置了相当于K个空位，如果值大于silde_sum,说明空格还没用完，如果等于说明空格用完了，但是还可能存在更大的连续1，因此只有当值小于silde_sum才能保证是最大的连续1串）

​ 如果没有，那么说明silde-1为最大窗口，也就是最长全1串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 10 2
# 1 0 0 1 0 1 0 1 0 1


n,k = map(int,input().split())

nums = list(map(int,input().split()))

#判断新的滑动窗口是不是存在和大于等于原来的最大和
def get_maxsum(silde,nums,max_sum):

    end = silde
    start = 0
    while end<len(nums):
        new_max_sum = sum(nums[start:end])
        if new_max_sum>=max_sum:
            return True

        start += 1
        end+=1

    return False


if k>n:
    print(n)
else:
    max_len = 0
    i =0
    tmp_len = 0
    while i<n:
        if nums[i]==1:
            tmp_len +=1
        else:
            tmp_len = 0


        max_len = max(max_len,tmp_len)
        i+=1

    if max_len+k>=n:
        print(n)
    else:
        flag = True
        silde = max_len + k
        max_sum = max_len
        while flag:
            if get_maxsum(silde,nums,max_sum):
                silde += 1
                max_sum+=1
            else:
                flag = False
    print(silde-1)