美团2018.9.6笔试最长全1串

系统管理员 2022-05-14 12:08 210阅读 0赞

# 题目描述 #

给你一个01字符串，答案=该串中最长的连续的1的长度，现在你有至多K次机会，每次机会可以将串中的某个0改成1，现在问最大的可能答案。  
**输入：**  
输入第一行为两个整数N,K，表示字符串长度和机会次数  
第二行输入N个整数，表示该字符串的元素  
（1≤N≤300000, 0≤K≤N）  
**输出：**  
最大的可能答案  
**样例输入：**  
10 2  
1 0 0 1 0 1 0 1 0 1  
**样例输出：**  
5  
**提示：**  
可以把两个机会花在最后两个0上，这样就变成了1 0 0 1 0 1 1 1 1 1，最后有连续的5个1，这是最长的了，所以输出5

# 思路 #

如果输入的数组里没有1，那么返回K即机会次数。  
如果输入的数组有1，且K>=N-1，那么返回N。  
如果输入的数组有1，且K小于N-1：  
那么返回的值，至少应该是1+K。想象有个1+K宽度的窗口，在数组上滑动，在某一次滑动时，窗口内有1个1，K个0，这样就用掉K次机会，把窗口内的0都变成1，就形成了连续1串。  
进一步说（考虑已有1串），  
如果数组已有的最长连续1子串的长度为max，那么返回的值至少为max+K。（读者可以画图验证）

程序的整体思路为：  
滑动窗口slide初始大小为max+K。即slide = max+K。  
滑动窗口总和sum初始大小为max。即sum = max。

循环每次检测，当前大小为slide 的滑动窗口，是否有一次滑动使得总和>=sum。  
如果有，说明返回结果至少为slide，但还有可能更大，所以slide和sum都++。  
如果没有，说明返回结果应该为slide-1，停止循环。

# 代码 #

#提交代码时，取消以下注释
    ##N,K = map(int,input().split())
    ##num = list(map(int,input().split()))
    
    #提交代码时，删除以下代码
    #[1, 0, 0, 1, 0, 1, 0, 1, 0, 1]
    N = 10
    K = 2
    num = [1, 0, 0, 1, 1, 1, 0, 1, 0, 1]
    
    
    def checkInterval(possible,sumvalue):
    
        startmax = N - possible
        for start in range(0,startmax+1):
            #start范围是从start到startmax
            end = start + possible
            #start和end指分片的开始与结束
            if sum(num[start:end]) >= sumvalue:
                return True
        return False
    
    
    if(1 not in num):#如果数组里没有1，那么最长也就是机会个数
        print(K)
    elif(K>=N-1):
        print(N)
    else:
        #找出最长1的长度
        maxleng = 0
        tempmaxleng = 0
        for i in num:
            if(i == 1):
                tempmaxleng += 1
            else:
                if(tempmaxleng>maxleng):
                    maxleng = tempmaxleng
                tempmaxleng = 0
        #得到了最长连续1的长度
        sumvalue = maxleng#滑动窗口求和至少为sumvalue
        possible = sumvalue+K#滑动窗口的长度至少为possible
    
        while(True):
            if(not checkInterval(possible,sumvalue)):
               break 
            sumvalue += 1
            possible += 1
        print(possible -1)

运行结果为7  
即可以改为\[1, 0, 0, 1, 1, 1, 1, 1, 1, 1\]  
不知道`sum(num[start:end])`这条语句的速度如何，也许用线段树更快，毕竟线段树查询某个区间内的sum很快。如果用线段树，那么先建立[线段树][Link 1]，然后这条语句改为线段树的查询函数query。

[Link 1]: https://blog.csdn.net/anlian523/article/details/80766794