leetcode1248. 统计「优美子数组」

leetcode1248. 统计「优美子数组」

五月 23, 2020

leetcode1248. 统计「优美子数组」

给你一个整数数组 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

读完题我第一反应是动态规划，写了一个二维的，空间不够，压缩成一维，又超时。
然后我想到了滑动窗口，但是这道题窗口不是固定大小，肯定也不好算。
接着我想出了最后一种：

维护一个固定大小的队列

维护一个大小固定的队列，队列里面存的是这个奇数的index，把两边的空隙的选法相乘。
比如k=2，，假设现在队列是1,3,17,25，要算13和17这两个奇数能组合成的情况，应该用1-3的情况乘17-25的情况。
可以类比：一条道路上有k棵连续的树，在第一颗树左面可以放n个花，在最后一棵树右边也可以放n个花，这样的方法有(n+1)*(n+1)种，n+1是可以不放花。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int numberOfSubarrays(int[] nums, int k) {
        if (nums.length == 0) return 0;
        //中间是必须选的，所以只用计算两边就行
        //只需要知道出去是多少，进来是多少就行
        int count = 0;
        int ans = 0;
        LinkedList<Integer> list = new LinkedList<>();
        list.add(-1);
        for (int i = 0; i <= nums.length; i++) {
            //方便处理边界，把两边都加进去
            if (i == nums.length || (nums[i] & 1) == 1) {
                int last = list.getLast();
                list.add(count);
                if (list.size() == k + 2) {
                    int first = list.removeFirst();
                    ans +=((list.getFirst() - first) * (count - last));
                }
            }
            count++;
        }
        return ans;

    }

动态规划

虽然动态规划超时，但是写一写也挺有意思。有点类似于背包的想法。
二维的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int numberOfSubarrays(int[] nums, int k) {
        if (nums.length == 0) return 0;
        int[][] dp = new int[nums.length][nums.length];
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            dp[i][i] = (nums[i] & 1);
            if (dp[i][i] == k) {
                count++;
            }
        }
        
        for (int i = nums.length - 2; i >= 0; i--) {
            for (int j = i + 1; j < nums.length; j++) {
                dp[i][j] = Math.max(dp[i][j - 1] + (nums[j] & 1), dp[i + 1][j]);
                //选第j个数和不选第j个数
                if (dp[i][j] == k) {
                    count++;
                }
            }
        }
        return count;
    }

压缩成一维:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int numberOfSubarrays(int[] nums, int k) {
        if (nums.length == 0) return 0;
        int count = 0;
        int[] dp2 = new int[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = i; j < nums.length; j++) {
                if (j == i) {
                    dp2[j] = (nums[j] & 1);
                    if (dp2[j] == k) {
                        count++;
                    }
                    continue;
                }
                dp2[j] = Math.max(dp2[j - 1] + (nums[j] & 1), dp2[j]);
                if (dp2[j] == k) {
                    count++;
                }
            }
        }
        return count;
    }

我花了十几分钟研究怎么压缩，没想到这道题不用dp，可惜了。
leetcode 84/100