正数数组的最小不可组成和问题
程序员文章站
2024-02-03 11:21:28
...
问题描述:
- 给定一个正数数组arr, 其中所有的值都为整数, 以下是最小不可组成和的概念:把arr每个子集内的所有元素加起来会出现很多值, 其中最小的记为
min, 最大的记为max。在区间[min,max]上, 如果有数不可以被arr某一个子集相加得到, 那么其中最小的那个数是arr的最小不可组成和。在区间[min,max]上, 如果所有的数都可以被arr的某一个子集相加得到, 那么max+1是arr的最小不可组成和。请写函数返回正数数组arr的最小不可组成和。 - 例子:arr=[3,2,5]。 子集{2}相加产生2为min, 子集{3,2,5}相加产生10 max。 在区间[2,10]上, 4、 6和9不能被任何子集相加得到, 其中4是arr的最小不可组成和。arr=[1,2,4]。 子集{1}相加产生1为min, 子集{1,2,4}相加产生7为max。 在区间[1,7]上, 任何数都可以被子集相加得到, 所以8是arr的最小不可组成和。
- 牛客链接
- 进阶问题:
- 如果已知正数数组arr中肯定有1这个数, 是否能更快地得到最小不可组成和?
解题思路
- 第一时间看到这个题,想到了一个经典的DP问题,用某个数组中的数是否能累加成target。该题与那题类似,只不过对从min到max每次都执行一遍该函数,看能否累加出来,显然复杂度过高。
- 该题有三种解法(具体细节参考代码注释):
- 递归
- 动态规划(二维数组)
- 动态规划(压缩矩阵,一维数组)
- 对于进阶问题,可以先对该数组排序,然后用变量range表示用(0~i)位置能累加出的范围。即(1~range)范围内的数全部可以用(0~i)位置上的数累加出来,如数组[1,2,5],起初对于1而言,range为1,向后遍历,对于2而言,2<=range+1,则2对应的range更新为range+arr[i],为3,说明用[1,2]能加出1~3范围上的数。然而对于5,5>range+1,说明用[1,2,5]累加不出(1~range+arr[i] = 8)内的全部元素,因为出现了断层,断点便是range+1(4)处,所以该值便是最小不可组成和。若遍历数组到最后,也没有出现断点,那么此时range便是该数组的累加和,最小不可组成和便是range+1。
经验教训
- dp问题的压缩矩阵问题(具体看代码实现)
代码实现
- 递归方法
/*
* 法1: 递归方法:
* 0~i位置上已经完成决策,和为 preSum,决定i位置上的元素要还是不要。
* 每次面临两个选择,向下不断分支(类似二叉树),最终决策完成。将最终的和加入set中。set中便存储了所有可能的子序列累加和。
* 然后找到min与max,从中遍历,查找是否在set中。
*/
public static int unformedSum1(int[] arr) {
if (arr == null || arr.length == 0) {
return 1;
}
HashSet<Integer> set = new HashSet<>();
int min = Integer.MAX_VALUE;
int max = 0;
for (int i = 0;i < arr.length;i++) {
min = Math.min(min, arr[i]);
max += arr[i];
}
process(arr,0,0,set);
for (int num = min + 1; num <= max; num++) {
if (! set.contains(num)) {
return num;
}
}
return max + 1;
}
public static void process(int[] arr,int i,int preSum,HashSet<Integer> set) {
//决策结束,把决策累加的和加入set中
if (i == arr.length) {
set.add(preSum);
return;
}
//不要当前元素
process(arr,i+1,preSum,set);
//要当前元素
process(arr,i+1,preSum + arr[i],set);
}
- 动态规划(二维数组)
/*
* 法2:动态规划(未压缩矩阵,二维数组):
* dp[i][j]表示arr[0~i]*选择,看能否累加出j,所以i的取值范围为0~arr.length-1,j取值范围为0~max
* 注意和str1有多少个字序列等于str2那一道题的dp方法区分,因为那一道题要考虑空串的情况,该题不用,当然,也可以考虑。
* 依赖关系:dp[row][col] = dp[row-1][col]||dp[row-1][col-arr[row]]
* 注意这种依赖关系,先填好第一行,第一列,然后从上到下,从左到右填满整个数组
*/
public static int unformedSum2(int[] arr) {
if (arr == null || arr.length == 0) {
return 1;
}
int min = Integer.MAX_VALUE;
int max = 0;
for (int i = 0;i < arr.length;i++) {
min = Math.min(min, arr[i]);
max += arr[i];
}
boolean[][] dp = new boolean[arr.length][max+1];
//初始化第一行,第一行除了dp[0][0],dp[0][arr[0]],其他都是false,
dp[0][arr[0]] = true;
//初始化第一列,当然,第一列不初始化也可以
for (int row = 0; row < dp.length; row++) {
dp[row][0] = true;
}
//根据依赖关系,填好其他位置,并注意判断越界问题
for (int row = 1; row < dp.length; row++) {
for (int col = 1; col < dp[0].length; col++) {
if (col - arr[row] >= 0) {
dp[row][col] = dp[row-1][col]||dp[row-1][col-arr[row]];
}else {
dp[row][col] = dp[row-1][col];
}
}
}
for (int num = min + 1; num <= max; num++) {
if (! dp[dp.length - 1][num]) {
return num;
}
}
return max + 1;
}
- 动态规划(一维数组)
/*
* 法3:动态规划(压缩矩阵,一维数组)
* 观察依赖关系,只是上下行的关系,第i行元素的值只依赖上一行的值,并且最终要求的是最后一行的值,此时前面所有的行便没有作用。
* 所以可以只用一行来保存当前值,即假设上一行元素为dp[],那么计算当前行时,直接用该数组,但是这样会引起一个问题,以怎么的顺序
* 更新该行,原则便是如果旧的dp[i]还有用,一定不能用新值覆盖旧值,填入新的dp[i]时,一定确保旧的dp[i]已经没有用处了。
*
*/
public static int unformedSum3(int[] arr) {
if (arr == null || arr.length == 0) {
return 1;
}
int min = Integer.MAX_VALUE;
int max = 0;
for (int i = 0;i < arr.length;i++) {
min = Math.min(min, arr[i]);
max += arr[i];
}
boolean[] dp = new boolean[max + 1];
//初始化
dp[0] = true;
dp[arr[0]] = true;
//还需要决策 arr.length - 1 次
for (int i = 1;i < arr.length; i++) {
//对于第i个字符,选择要还是不要
for (int col = dp.length - 1; col-arr[i] >= 0; col--) {
dp[col] = dp[col - arr[i]] ? true : dp[col];
}
//等同于下列代码
/*for (int col = dp.length; col >= 0;col--) {
if (col - arr[i] >= 0) {
dp[col] = dp[col - arr[i]]||dp[col];
}else {
dp[col] = dp[col];
}
}*/
}
for (int num = min + 1; num <= max; num++) {
if(! dp[num]) {
return num;
}
}
return max + 1;
}
- 进阶问题
/*
* 解决进阶问题:
*/
public static int unformedSum4(int[] arr) {
if (arr == null || arr.length == 0) {
return 1;
}
Arrays.sort(arr);
int range = 1;
for (int i = 1; i < arr.length; i++) {
if (arr[i] <= range + 1) {
range = range + arr[i];
}else {
return range + 1;
}
}
return range + 1;
}