「LeetCode每日一题」—— 1248. 统计「优美子数组」
1248. 统计「优美子数组」
链接:https://leetcode-cn.com/problems/count-number-of-nice-subarrays/
难度:中等
题目
给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字,我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
输入:nums = [1,1,2,1,1], k = 3
输出:2
解释:包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
思路
优美子数组的定义是连续子数组中恰好有K个奇数数字。注意这里是连续字数组。
我们可以先对数组中的奇数位置进行记录
以例子为示:
nums = [1,1,2,1,1], k = 3
我们遍历数组中的奇数:
[] [0] 0为标志位
[1] [0,1]
[1,1] [0,1,2]
[1,1,2] [0,1,2]
[1,1,2,1] [0,1,2,4]
[1,1,2,1,1] [0,1,2,4,5]
[1,1,2,1,1] [0,1,2,4,5,6] 把长度+1加在后面做标志位
然后我们来数优美子数组的个数。
因为k=3,所有其实我们需要找到连续的两个边界,如果找到第 i 个奇数的位置,找到第i+k-1个奇数的位置,这就确定了两个边界,再看这两个边界的活动范围有多大就知道有几种组合了。
左边界的活动范围在当前第 i 个奇数到上一个奇数(即 i-1)之间,右边界的活动范围在当前第 i+k-1 到下一个边界(即 i+k)之间,左边范围 * 右边活动范围累加就是结果。
在这个例子中,
count = (1-0)*(5-4)+(2-1)*(6-5) = 2
代码见解决方案
方案代码
解决方案:
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
odd_positions = [0]
for i in range(len(nums)):
if nums[i] % 2 == 1:
odd_positions.append(i + 1)
odd_positions.append(len(nums) + 1)
count = 0
for i in range(1, len(odd_positions) - k):
count += ((odd_positions[i] - odd_positions[i - 1]) *
(odd_positions[i + k] - odd_positions[i + k - 1])) # 组合数
return count
原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/342.html
您必须登录才能发表评论。