[已解决]Python：每日一题 308

zltzlt

今天的题目：

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 k 个值从 0 变成 1 。

返回仅包含 1 的最长连续子数组的长度。

示例 1：

输入：A = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]，k = 2
输出：6
解释：[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
粗体数字从 0 变为 1，最长的子数组长度为 6。

示例 2：

输入：A = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1]，k = 3
输出：10
解释：[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]
粗体数字从 0 变为 1，最长的子数组长度为 10。

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

kinkon

2020-1-18 11:52:36

1. def fun308(A, k):
   
2.     res = [-1]+[i for i in range(len(A)) if not A[i]]+[len(A)]
   
3.     if len(res)-k-2 <= 0: return len(A)   
   
4.     return max([max(res[i+k]-res[i-1]-1,0) for i in range(1, len(res)-k)])

复制代码

跳转到最佳答案楼层

Croper

1. def func308(l:list,k:int):
   
2.     l.append(2)
   
3.     prev=1
   
4.     count=0
   
5.     ret,temp=0,0
   
6.     prev_blank=0
   
7.     que=[deque(),deque()]
   
8.     for i in l:
   
9.         if i!=prev:
   
10.             que[prev].append(count)
    
11.             temp+=count
    
12.             if prev==0:
    
13.                 k-=count
    
14.                 while k<0:
    
15.                     temp-=que[1].popleft()
    
16.                     prev_blank=que[0].popleft()
    
17.                     k+=prev_blank
    
18.                     temp-=prev_blank
    
19.             ret=max(ret,temp+min(prev_blank,k))
    
20.             count=0
    
21.             prev=i
    
22.         count+=1
    
23.     return ret

复制代码

阴阳神万物主

跟昨天好像啊。
代码：

1. def solve(A:'list of 0 or 1',k:int):
   
2.     res = 0
   
3.     le = len(A)
   
4.     pos = [-1]+[i for i in range(le) if not A[i]]+[le]
   
5.     for i in range(1,len(pos)-k):
   
6.         res = max(pos[i+k]-pos[i-1]-1,res)
   
7.     return res
   
8. if __name__ == '__main__':
   
9.     print('示例1 输出：',solve(A = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0],k = 2))
   
10.     print('示例2 输出：',solve(A = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1],k = 3))

复制代码

wanting-for

1. list1 = input().split()
   
2. k = int(input())
   
3. m = k
   
4. list1_result = []
   
5. list2 = list1.copy()
   
6. first = 0
   
7. count = 0
   
8. while True:
   
9.     for i in range(first,len(list1)):
   
10.         if list1[i] == '0':
    
11.             list2[i] = '1'
    
12.             k-=1
    
13.             if k == 0:
    
14.                 for j in list2:
    
15.                     if j == '1':
    
16.                         count+=1
    
17.                     else:
    
18.                         list1_result.append(count)
    
19.                         count = 0
    
20.                 list1_result.append(count)
    
21.                 count = 0
    
22.                 first+=1
    
23.                 list2 = list1.copy()     
    
24.                 k = m
    
25.                 break
    
26.     if list1[first:len(list1)].count('0') == 0:#消除尾数全是1的BUG
    
27.         break
    
28.     if first == len(list1):
    
29.         break         
    
30. print(max(list1_result))
    

复制代码

#感觉有点像暴力求解

wanting-for

阴阳神万物主 发表于 2020-1-17 21:50
跟昨天好像啊。
代码：

大佬的代码，有些难于理解，可否解释一下啊

阴阳神万物主

wanting-for 发表于 2020-1-17 23:16
大佬的代码，有些难于理解，可否解释一下啊

首先，把0的位置标出来。
然后，依次把相邻的跨度为k个0的位置的索引作差，就得到一个相对长的子数组的长度。
最后，把最大的那个长度返回就好了。
这个思路主要基于 最长连续子数组 一定具有的特性：两头的外面相邻的，不是 0 就是 A的边界，其中包含的 0 的数量一定为 k. 但是满足这个特性的，不一定是 最长连续子数组 ，所以就要在满足这个特性的 连续子数组 中选出最长的那个。

sunrise085

#设置一定宽度窗口在输入列表上进行滑动（窗体初始大小为列表长度），并检查窗体内0的个数
#若窗体内的count(0)=k，返回当前窗体大小，
#若滑动到列表尾部，都不满足条件，则缩小窗体再次寻找

1. def fun308(list1,k):
   
2.     length= len(list1)
   
3.     for i in range(length,k-1,-1):
   
4.         for j in range(length-i+1):
   
5.             if list1[j:i+j].count(0)==k:
   
6.                 return i
   
7. 
   
8. list1=[1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]
   
9. list2=[0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1]
   
10. print(fun308(list1,2))
    
11. print(fun308(list2,3))
    
12. print(fun308([0,0,0,0,0,0,0],4))

复制代码

kinkon

偷换阴阳神解法

1. def fun308(A, k):#以0解法
   
2.     res = [-1]+[i for i in range(len(A)) if not A[i]]+[len(A)]
   
3.     if len(res) == 2: return len(A)   
   
4.     return max([max(res[i+k]-res[i-1]-1,0) for i in range(1, len(res)-k)])

复制代码

zltzlt

Croper 发表于 2020-1-17 21:32

deque 是从 collections 模块来的吧？

zltzlt

阴阳神万物主 发表于 2020-1-17 21:50
跟昨天好像啊。
代码：

解答错误

输入：A = [0,0,0,1]，k = 4
输出：0
预期结果：4

zltzlt

wanting-for 发表于 2020-1-17 22:54
#感觉有点像暴力求解

输入 A = [1,1,1,0,0,0,1,1,1,1,0]，k = 2 出错

ValueError: max() arg is an empty sequence

zltzlt

sunrise085 发表于 2020-1-17 23:42
#设置一定宽度窗口在输入列表上进行滑动（窗体初始大小为列表长度），并检查窗体内0的个数
#若窗体内的cou ...

解答错误

输入：A = [0,0,0,1]，k = 4
输出：None
预期结果：4

zltzlt

kinkon 发表于 2020-1-18 11:23
偷换阴阳神解法

输入 A = [0, 0, 0, 1]，k = 4 出错

ValueError: max() arg is an empty sequence

776667

1. def fun308(A,k):
   
2.     result = []
   
3.     for i in range(len(A)-1):
   
4.         for j in range(len(A))[i+1:][::-1]:
   
5.             if A[i:j+1].count(0) == k:
   
6.                 result.append(j - i + 1)
   
7.                 break
   
8.     return max(result)

复制代码

zltzlt

776667 发表于 2020-1-18 11:45

解答错误

输入：[0,0,0,1]，k = 4
输出：0
预期结果：4

kinkon

1. def fun308(A, k):
   
2.     res = [-1]+[i for i in range(len(A)) if not A[i]]+[len(A)]
   
3.     if len(res)-k-2 <= 0: return len(A)   
   
4.     return max([max(res[i+k]-res[i-1]-1,0) for i in range(1, len(res)-k)])

复制代码

Croper

zltzlt 发表于 2020-1-18 11:31
deque 是从 collections 模块来的吧？

恩，忘了粘贴那一句，list的pop(0)代价太高。

godfishs

1. import itertools
   
2. 
   
3. def max_1(lis):  #求由0,1组成的A数组仅包含 1 的最长连续子数组的长度
   
4.     c = 0
   
5.     re = 0
   
6.     for i in lis:
   
7.         if i == 1:
   
8.             c += 1
   
9.         else:
   
10.             if c > re :
    
11.                 re = c
    
12.             c = 0
    
13.     if c > re:
    
14.         re = c
    
15.     return re
    
16. 
    
17. def zc(A,k):
    
18.     index = []
    
19.     re = 0
    
20.     for i in range(len(A)):
    
21.         if A[i] == 0:
    
22.             index.append(i)    #分析数组A，找到数字为0的位置
    
23.             
    
24.     if k > len(index):  #k比0的个数还多的情况
    
25.         return len(A)
    
26.    
    
27.     for i in itertools.combinations(index,k):   #从index列表记录的0的位置中取出k个0的位置，每一个i是一种不同取法
    
28.         temp = A.copy()  #必须用一个复制的原列表用作计算
    
29.         for j in range(k):  #把对应该种取法的0位置换为1
    
30.             temp[i[j]] = 1
    
31.         max_temp = max_1(temp)  #计算最大子组的长度
    
32.         if max_temp > re:
    
33.             re = max_temp
    
34.     return re
    
35. 
    
36. if __name__ == '__main__':
    
37.     A = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0]
    
38.     k = 2
    
39.     print(zc(A,k))
    
40.     A = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1]
    
41.     k = 3
    
42.     print(zc(A,k))

复制代码

zltzlt

godfishs 发表于 2020-1-18 12:49
import itertools

def max_1(lis):  #求由0,1组成的A数组仅包含 1 的最长连续子数组的长度

解答错误

输入：[0, 0, 0, 1]，k = 4
输出：None
预期结果：4

kinkon

帮godfishs改下，看看效率怎样

1. from itertools import combinations as ct
   
2. def max_1(lis):  #求由0,1组成的A数组仅包含 1 的最长连续子数组的长度
   
3.     c, re = 0, 0
   
4.     for i in lis:
   
5.         if i == 1: c += 1
   
6.         else:
   
7.             if c > re : re = c
   
8.             c = 0
   
9.     if c > re: re = c
   
10.     return re
    
11. 
    
12. def zc(A,k):
    
13.     index = []
    
14.     re = 0
    
15.     for i in range(len(A)):
    
16.         if A[i] == 0: index.append(i)    #分析数组A，找到数字为0的位置
    
17.     if k > len(index): return len(A)     #k比0的个数还多的情况
    
18.         
    
19.     for i in ct(index,k):   #从index列表记录的0的位置中取出k个0的位置，每一个i是一种不同取法
    
20.         temp = A.copy()  #必须用一个复制的原列表用作计算
    
21.         for j in range(k):  #把对应该种取法的0位置换为1
    
22.             temp[i[j]] = 1
    
23.         max_temp = max_1(temp)  #计算最大子组的长度
    
24.         if max_temp > re:
    
25.             re = max_temp
    
26.     return re

复制代码