🧑🧒 2750.将数组划分成若干好子数组的方式
给你一个二元数组 nums 。
如果数组中的某个子数组 恰好 只存在 一 个值为 1 的元素，则认为该子数组是一个 好子数组 。
请你统计将数组 nums 划分成若干 好子数组 的方法数，并以整数形式返回。由于数字可能很大，返回其对 109 + 7 取余 之后的结果。
子数组是数组中的一个连续 非空 元素序列。
思路
基本思想
看到本题的第一思路就是类似于字符串的分割一样，使用回溯法进行分割，只有当前子数组只有一个1时才能继续向下分割，就这样一直向下，然后分割完成就可以形成一个结果，统计所有的合法划分结果即可，代码为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
//要将当前数组划分成很多段
//考虑使用回溯法，当前子数组符合要求才继续划分
int res=0;
public int numberOfGoodSubarraySplits(int[] nums) {
backtrack(nums,0);
return res;
}
private void backtrack(int[] nums,int index){
if(index==nums.length){
res=(res+1)%1000000007;
}
//开始划分，当前子数组没有1就继续，只存在一个1就向下，多余一个1就break
int count=0;//统计当前层中1的个数
for(int i=index;i<nums.length;++i){
if(nums[i]==1){
++count;
}
//break
if(count>1){
break;
}
//向下
if(count==1){
backtrack(nums,i+1);
}
}
}
}
|
但是这样会造成超时，因为数组的长度过长，所以想到用数学的办法解决
当前一个数组可以划分的前提是划分的两部分各存在一个0，此时划分方案数取决于两个1之间有多少个0，从不同的0划分就可以形成不同的划分方案，这里的1就是划分边界，不同的边界与下一个边界之间的组合使用乘法法则来统计出所有的方案数，所以核心就是：找到所有的1，每两个1之间有多少0就有多少方案数，将这些方案数相乘即可
执行流程
- 从头到尾找到没两个1之间的0的个数，可以得到当前的划分方案数
- 将所有的划分方案数相乘即可得到所有的划分方案数
代码
根据以上分析，得出以下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int numberOfGoodSubarraySplits(int[] nums) {
int res=1;
//这个记录上一个1存在的位置
int index=-1;
for(int i=0;i<nums.length;++i){
if(nums[i]==0)
continue;
//到这里就是找到了1，并且这个1并不是开头第一个1
if(index>=0)
res=(res*(i-index))%1000000007;
//记录当前1的位置
index=i;
}
return res;
}
}
|
总结
核心就是从回溯法转换到数学求解，每个片段可以有多少种划分方案取决于当前两个1之间的0的个数