? 优质资源分享 ?
学习路线指引(点击解锁) | 知识定位 | 人群定位 |
---|---|---|
? Python实战微信订餐小程序 ? | 进阶级 | 本课程是python flask+微信小程序的完美结合,从项目搭建到腾讯云部署上线,打造一个全栈订餐系统。 |
?Python量化交易实战? | 入门级 | 手把手带你打造一个易扩展、更安全、效率更高的量化交易系统 |
作者:Grey
原文地址:数组的最小不可组成和问题
题目说明
链接:https://www.nowcoder.com/questionTerminal/296c2c18037843a7b719cf4c9c0144e4
来源:牛客网给定一个全是正数的数组arr,定义一下arr的最小不可组成和的概念:
1,arr的所有非空子集中,把每个子集内的所有元素加起来会出现很多的值,其中最小的记为min,最大的记为max;
2,在区间[min,max]上,如果有一些正数不可以被arr某一个子集相加得到,那么这些正数中最小的那个,就是arr的最小不可组成和;
3,在区间[min,max]上,如果所有的数都可以被arr的某一个子集相加得到,那么max+1是arr的最小不可组成和;
举例: arr = {3,2,5}
arr的min为2,max为10,
在区间[2,10]上,4是不能被任何一个子集相加得到的值中最小的,所以4是arr的最小不可组成和;
arr = {3,2,4}
arr的min为2,max为9,
在区间[2,9]上,8是不能被任何一个子集相加得到的值中最小的,所以8是arr的最小不可组成和;
arr = {3,1,2} arr的min为1,max为6,
在区间[2,6]上,任何数都可以被某一个子集相加得到,所以7是arr的最小不可组成和;
请写函数返回arr的最小不可组成和。
思路
首先我们设置两个变量,max
和min
用于记录数组累加得到的最大值,和当数组不为空累加得到的最小值。那么在数组非空状态下,累加和一定在[min, max]
区间内。我们设置
boolean[][] dp = new boolean[arr.length][max + 1];
其中dp[i][j]
表示[0....i]
范围内的元素任意累加,能否组成j这个累加和。
显然有
// 0元素可以组成arr[0]这个累加和
dp[0][arr[0]] = true;
for (int i = 0; i < dp.length; i++) {
// 0..i上一个元素都不用,可以组成0这个累加和
dp[i][0] = true;
}
这样我们得到dp
这个数组第一行和第一列的情况。
然后我们可以推导普遍位置
dp[i][j] = dp[i - 1][j] || (j - arr[i] >= 0 && dp[i - 1][j - arr[i]]);
其含义为:
[0...i]
范围内,任意选择,能否组成j
这个累加和,其实包括了两种情况:
情况1:[0...i-1]
范围内,任意选择,能否组成j
这个累加和,如果可以,说明dp[i][j]=true
情况2:[0...i-1]
范围内,任意选择,能否组成j-arr[i]
这个累加和(注意不能越界),如果可以,说明dp[i][j] = true
所以,普遍位置的求法如下
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < max + 1; j++) {
dp[i][j] = dp[i - 1][j] || (j - arr[i] >= 0 && dp[i - 1][j - arr[i]]);
}
}
经过上述处理,dp
已全部填好,接下来就是判断dp
中第一个为false
的位置,即为答案
for (int i = min; i <= max; i++) {
if (!dp[arr.length - 1][i]) {
return i;
}
}
如果上述过程没有找到,则返回max+1
,完整代码如下
public static int getFirstUnFormedNum(int[] arr) {
int min = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
max += arr[i];
min = Math.min(min, arr[i]);
}
// 可以到的范围是[min,max]
// dp[i][j] 0....i能否组成j
boolean[][] dp = new boolean[arr.length][max + 1];
// 第0行 除了下述位置,其他位置都是false
dp[0][arr[0]] = true;
for (int i = 0; i < dp.length; i++) {
// 0..i上一个元素都不用,可以组成0这个累加和
dp[i][0] = true;
}
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < max + 1; j++) {
dp[i][j] = dp[i - 1][j] || (j - arr[i] >= 0 && dp[i - 1][j - arr[i]]);
}
}
for (int i = min; i <= max; i++) {
if (!dp[arr.length - 1][i]) {
return i;
}
}
return max + 1;
}
进阶
链接:https://www.nowcoder.com/questionTerminal/a689a05f75ff4caaa129b1f971aeb71e
来源:牛客网给定一个正数数组arr,其中所有的值都为整数,以下是最小不可组成和的概念
- 把arr每个子集内的所有元素加起来会出现很多值,其中最小的记为min,最大的记为max
- 在区间[min, max]上,如果有数不可以被arr某一个子集相加得到,那么其中最小的那个数是arr的最小不可组成和
- 在区间[min, max]上,如果所有的数都可以被arr的某一个子集相加得到,那么max+1是arr的最小不可组成和
请写函数返回正数数组arr的最小不可组成和
保证1一定出现过!
时间复杂度为O(n),额外空间复杂度为O(1)
主要思路:
如果一定有1这个数,那么如果将这个正数数组排序后,0位置上的值一定是1,设置一个变量range
,初始值为1,表示当前可以搞定的最小正整数的范围,
接下来我们要通过遍历整个数组来扩充range
的范围,假设[0.....i-1]
上可以让range扩充到b
这个值,i
位置上的值假设是a
,如果
a <= b + 1
则遍历到i
位置,可以让range
的值扩充到a + b
,
如果
a > b + 1
则b + 1
就是整个数组的最小不可组成和,可以直接返回。完整代码如下:
public static long unformedSum(long[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
Arrays.sort(arr);
long range = 1;
for (int i = 1; i != arr.length; i++) {
if (arr[i] > range + 1) {
return range + 1;
} else {
range += arr[i];
}
}
return range + 1;
}
更多
转载请注明:xuhss » 数组的最小不可组成和问题