class Solution {
public:
int numberOfGoodSubarraySplits(vector<int>& nums) {
}
};
6910. 将数组划分成若干好子数组的方式
给你一个二元数组 nums 。
如果数组中的某个子数组 恰好 只存在 一 个值为 1 的元素，则认为该子数组是一个 好子数组 。
请你统计将数组 nums 划分成若干 好子数组 的方法数，并以整数形式返回。由于数字可能很大，返回其对 109 + 7 取余 之后的结果。
子数组是数组中的一个连续 非空 元素序列。
示例 1：
输入：nums = [0,1,0,0,1] 输出：3 解释：存在 3 种可以将 nums 划分成若干好子数组的方式： - [0,1] [0,0,1] - [0,1,0] [0,1] - [0,1,0,0] [1]
示例 2：
输入：nums = [0,1,0] 输出：1 解释：存在 1 种可以将 nums 划分成若干好子数组的方式： - [0,1,0]
提示：
1 <= nums.length <= 1050 <= nums[i] <= 1原站题解
golang 解法, 执行用时: 240 ms, 内存消耗: 7.9 MB, 提交时间: 2023-06-26 09:11:56
func numberOfGoodSubarraySplits(nums []int) int {
const mod int = 1e9 + 7
ans, pre := 1, -1
for i, x := range nums {
if x > 0 {
if pre >= 0 {
ans = ans * (i - pre) % mod
}
pre = i
}
}
if pre < 0 { // 整个数组都是 0，没有好子数组
return 0
}
return ans
}
cpp 解法, 执行用时: 220 ms, 内存消耗: 229.6 MB, 提交时间: 2023-06-26 09:11:44
class Solution {
public:
int numberOfGoodSubarraySplits(vector<int> &nums) {
const int MOD = 1e9 + 7;
int ans = 1, pre = -1, n = nums.size();
for (int i = 0; i < n; i++) {
if (nums[i] == 0) continue;
if (pre >= 0) ans = (long) ans * (i - pre) % MOD;
pre = i;
}
return pre < 0 ? 0 : ans;
}
};
java 解法, 执行用时: 9 ms, 内存消耗: 58.5 MB, 提交时间: 2023-06-26 09:11:26
class Solution {
public int numberOfGoodSubarraySplits(int[] nums) {
final long MOD = (long) 1e9 + 7;
long ans = 1;
int pre = -1, n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] == 0) continue;
if (pre >= 0) ans = ans * (i - pre) % MOD;
pre = i;
}
return pre < 0 ? 0 : (int) ans;
}
}
python3 解法, 执行用时: 172 ms, 内存消耗: 20.8 MB, 提交时间: 2023-06-26 09:11:05
'''
根据题意，需要在每两个 1 之间画一条分割线，有 x 个 0 就可以画 x+1 条分割线。
根据乘法原理，答案为所有分割线的方案数的乘积。
特别地，如果数组中没有 1，那么答案为 0。如果数组只有一个 1，那么答案为 1。
'''
class Solution:
def numberOfGoodSubarraySplits(self, nums: List[int]) -> int:
MOD = 10 ** 9 + 7
ans, pre = 1, -1
for i, x in enumerate(nums):
if x == 0: continue
if pre >= 0:
ans = ans * (i - pre) % MOD
pre = i
return 0 if pre < 0 else ans