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

zltzlt

今天的题目：

给定一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是 “优美子数组”。

返回这个数组中 “优美子数组” 的数目。

示例 1：

输入：nums = [1,1,2,1,1]，k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1]。

示例 2：

输入：nums = [2,4,6]，k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。

示例 3：

输入：nums = [2,2,2,1,2,2,1,2,2,2]，k = 2
输出：16

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

TJBEST

2020-1-17 10:32:19

1. def fun307(nums , k):
   
2.     M = len(nums)
   
3.     jiIndexArr = [i for i in range(0,len(nums)) if nums[i]%2 ]
   
4.     N = len(jiIndexArr)
   
5.     if N < k:
   
6.         return 0
   
7.     elif N == k:
   
8.         return (jiIndexArr[0] + 1)*(M - jiIndexArr[N - 1])
   
9.     else:
   
10.         res = 0
    
11.         res += (jiIndexArr[0] + 1)*(jiIndexArr[k] - jiIndexArr[k - 1])
    
12.         for i in range(1,N - k):
    
13.             res += (jiIndexArr[i+k] - jiIndexArr[i+k-1])*(jiIndexArr[i] - jiIndexArr[i - 1])
    
14.         res += (jiIndexArr[N-k]-jiIndexArr[N-k-1])*(M - jiIndexArr[N - 1])
    
15.         return res

复制代码

跳转到最佳答案楼层

Croper

1. def func307(l:list,k):
   
2.     l.append(1)
   
3.     l2=[]
   
4.     ret=0
   
5.     v=1
   
6.     for i in l:
   
7.         if i % 2==0:
   
8.             v+=1
   
9.             continue
   
10.         l2.append(v)
    
11.         v=1
    
12.         if (len(l2)<=k):
    
13.             continue
    
14.         ret+=l2[-1]*l2[0]
    
15.         l2.pop(0)
    
16.     return ret
    
17. 
    

复制代码

塔利班

1. def f307(nums,k):
   
2.     res=0
   
3.     s=[-1]
   
4.     for i in range(len(nums)):
   
5.         if nums[i]%2:
   
6.             s.append(i)
   
7.     s+=[i+1]
   
8.     for i in range(1,len(s)-k):
   
9.         res += (s[i]-s[i-1])*(s[i+k]-s[i+k-1])
   
10.     return res

复制代码

爱尔兰咖啡

1. list1=[2,2,2,1,2,2,1,2,2,2]
   
2. k=2
   
3. def f(x):
   
4.         lst0=[]
   
5.         while len(x)>0:
   
6.                 for i in range(len(x)):
   
7.                         lst0.append(x[0:i+1])
   
8.                 x=x[1:]
   
9.         return lst0
   
10. def f1(x):
    
11.         n=0
    
12.         for i in x:
    
13.                 if i%2==1:
    
14.                         n+=1
    
15.         return n
    
16. def main():
    
17.         lst0=f(list1)
    
18.         lst1=[]
    
19.         for i in lst0:
    
20.                 if f1(i)==k:
    
21.                         lst1.append(i)
    
22.         print(lst1)
    
23.         print(len(lst1))
    
24.         return lst1,len(lst1)
    
25. if __name__=='__main__':
    
26.         main()

复制代码

TJBEST

子数组若出现多次 是不是只算一次？比如 nums = [1,1,2,2,1,1]，k = 2
是不是 只有 [1,1] [1,1,2][1,1,2,2][1,2,2,1][2,2,1,1][2,1,1]共6个？

阴阳神万物主

试探.jpg

1. def solve(nums:'list of int',k:int)->int:
   
2.     le = len(nums)
   
3.     pos = [i for i in range(le) if nums[i]%2]
   
4.     lt = len(pos)
   
5.     if lt < k:
   
6.         return 0
   
7.     res = (pos[0]+1)*((pos[k] if lt>k else le)-pos[k-1])
   
8.     #print('调试',res,pos)
   
9.     for i in range(1,lt-k):
   
10.         each = pos[i-1:i+k+1]
    
11.         #print('调试',each)
    
12.         res += (each[1]-each[0])*(each[-1]-each[-2])
    
13.     else:
    
14.         res += ((le-pos[-1])*(pos[-k]-pos[-k-1]))if lt>k else 0
    
15.     return res
    
16. if __name__ == '__main__':
    
17.     print('示例1 输出：',solve(nums = [1,1,2,1,1],k = 3))
    
18.     print('示例2 输出：',solve(nums = [2,4,6],k = 1))
    
19.     print('示例3 输出：',solve([2,2,2,1,2,2,1,2,2,2],k = 2))
    

复制代码

阴阳神万物主

塔利班 发表于 2020-1-16 21:35

咱俩想到一块儿去了，话说为啥不用列表推导式呢？

zltzlt

TJBEST 发表于 2020-1-16 22:26
子数组若出现多次 是不是只算一次？比如 nums = [1,1,2,2,1,1]，k = 2
是不是 只有 [1,1] [1,1,2][1,1,2,2 ...

不是。

TJBEST

1. def fun307(nums , k):
   
2.     M = len(nums)
   
3.     jiIndexArr = [i for i in range(0,len(nums)) if nums[i]%2 ]
   
4.     N = len(jiIndexArr)
   
5.     if N < k:
   
6.         return 0
   
7.     elif N == k:
   
8.         return (jiIndexArr[0] + 1)*(M - jiIndexArr[N - 1])
   
9.     else:
   
10.         res = 0
    
11.         res += (jiIndexArr[0] + 1)*(jiIndexArr[k] - jiIndexArr[k - 1])
    
12.         for i in range(1,N - k):
    
13.             res += (jiIndexArr[i+k] - jiIndexArr[i+k-1])*(jiIndexArr[i] - jiIndexArr[i - 1])
    
14.         res += (jiIndexArr[N-k]-jiIndexArr[N-k-1])*(M - jiIndexArr[N - 1])
    
15.         return res

复制代码

kinkon

不知道会不会超时

1. from itertools import combinations as ct
   
2. def f307(nums, k):
   
3.     if len(nums) < k or k == 0: return 0
   
4.     cout, res = 0, []     
   
5.     nums = list(enumerate(nums))        
   
6.     for num in range(len(nums)):
   
7.         res += [num for num in set(ct(nums, num + k))]
   
8.         if nums[num][1]%2 != 0:cout += 1
   
9.     if cout < k:return 0
   
10.     res = sorted(res)   
    
11.     t1, t2 = 0, 0
    
12.     for i in res:
    
13.         for j in range(len(i)-1):
    
14.             if i[j+1][0] - i[j][0] == 1:
    
15.                 if i[j][0]%2 != 0:
    
16.                     t1 += 1
    
17.             if t1 == k: t2 += 1
    
18.     return t2

复制代码

zltzlt

kinkon 发表于 2020-1-17 11:27
不知道会不会超时

解答错误

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：3
打印：

1. [((0, 2), (1, 2)), ((0, 2), (1, 2), (2, 2)), ((0, 2), (1, 2), (2, 2), (3, 1)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (7, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (7, 2), (8, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (7, 2), (8, 2), (9, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (7, 2), (9, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (8, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (8, 2), (9, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (6, 1), (9, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (7, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (7, 2), (8, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (7, 2), (8, 2), (9, 2)), ((0, 2), (1, 2), (2, 2), (3, 1), (4, 2), (5, 2), (7, 2), (9, 2)), ((0, ...（被和谐）

复制代码

预期结果：16

fan1993423

1. def fun307(lst,k):
   
2.     odd=[i for i in range(len(lst)) if lst[i]%2]
   
3.     new_odd=[-1]+odd+[len(lst)]
   
4.     result=0
   
5.     for i in range(len(odd)-k+1):
   
6.         start=new_odd[i+1]-new_odd[i]
   
7.         end=new_odd[i+k+1]-new_odd[i+k]
   
8.         result+=start*end
   
9.     return result

复制代码

wanting-for

1. def solve(A:'haha',k:int):
   
2.     first,count,end,result,c = 0,0,0,0,0
   
3.     end , m = first+k,k
   
4.     while True:
   
5.         for i in A[first:end]:
   
6.             if i%2 == 1:
   
7.                 count+=1
   
8.         if  count == m:
   
9.             result+=1
   
10.         if end - first == len(A) and c == 0:
    
11.             break
    
12.         if end == len(A):
    
13.             c+=1
    
14.             k+=1
    
15.             first = 0
    
16.             end = first+k
    
17.         if c==0:
    
18.             first+=1
    
19.             end = first+k
    
20.         c = 0
    
21.         count = 0
    
22.     return result
    
23. if __name__ == '__main__':
    
24.     print('示例1 输出：',solve(A = [1,1,2,1,1],k = 3))
    
25.     print('示例2 输出：',solve(A = [2,4,6],k = 1))
    
26.     print('示例2 输出：',solve(A = [2,2,2,1,2,2,1,2,2,2],k = 2))

复制代码

一杯茶一包烟，一个BUG改一天！

newbison

又是一个暴力破解法

1. def func307(arr, k):
   
2.     res = 0
   
3.     odd_or_even = [1 if i%2 != 0 else 0 for i in arr]
   
4.     for i in range(0, len(arr)):
   
5.         for j in range(len(arr), i+1, -1):
   
6.             if arr[i:j].count(1) == k:
   
7.                 res += 1
   
8.     return res
   
9. 
   
10. if __name__ == '__main__':
    
11.     print('示例一：', func307([1,1,2,1,1], 3))
    
12.     print('示例二：', func307([2,4,6], 1))
    
13.     print('示例三：', func307([2,2,2,1,2,2,1,2,2,2], 2))

复制代码

newbison

1. def func307(arr, k):
   
2.     res = 0
   
3.     odd_or_even = [1 if i%2 != 0 else 0 for i in arr]
   
4.     for i in range(0, len(arr)):
   
5.         for j in range(len(arr), i+1, -1):
   
6.             if arr[i:j].count(1) == k:
   
7.                 res += 1
   
8.     return res
   
9. 
   
10. if __name__ == '__main__':
    
11.     print('示例一：', func307([1,1,2,1,1], 3))
    
12.     print('示例二：', func307([2,4,6], 1))
    
13.     print('示例三：', func307([2,2,2,1,2,2,1,2,2,2], 2))

复制代码

ouyunfu

1. def f307(L:list,k:int)->int:
   
2.     count=0
   
3.     for i in range(len(L)-1):
   
4.         for j in range(i,len(L)+1):
   
5.             if len(L[i:j])-[i%2 for i in L[i:j]].count(0)==k:
   
6.                 count+=1
   
7.     return count
   
8. 
   
9. L = [2,2,2,1,2,2,1,2,2,2]
   
10. k = 2
    
11. print(f307(L,k))

复制代码

776667

1. def fun307(nums,k):
   
2. 
   
3.     def odd_count(x,k):
   
4.         count = 0
   
5.         for i in x:
   
6.             if i%2:
   
7.                 count += 1
   
8.             if count > k:
   
9.                 return 'over'
   
10.         if count < k:
    
11.             return 'less'
    
12.         return 'equals'
    
13. 
    
14.     result = []
    
15.     for i in range(len(nums)-k+1):
    
16.         for j in range(i+k,len(nums)+1):
    
17.             if odd_count(nums[i:j],k) == 'equals':
    
18.                 result.append(nums[i:j])
    
19.             if odd_count(nums[i:j],k) == 'over':
    
20.                 break
    
21.     return len(result)

复制代码

旅途Z

想问一下，每日一题是不再更新了嘛