0%

美团技术笔试——最长全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)