1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」—— 1248. 统计「优美子数组」

flypython • • leetcode题解

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

赞 (0)
flypythonflypython
0 0 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
« 上一篇 20/04/2020 11:00
下一篇 » 23/04/2020 11:02

相关推荐