文章目录
前言
问题一解决思路
题目二题解
前言
给定一个正数数组arr，
返回arr的子集不能累加出的最小正数
1）正常怎么做？
2）如果arr中肯定有1这个值，怎么做？
问题一解决思路
arr所有值的累加和从一个负数到一个整数做出一张表,然后看最后一行
arr 0~N-1最后一行的值能不能搞定1, 2, 3…哪一个最早不行的,返回就是答案
public static int unformedSum2(int[] arr) {
if (arr == null || arr.length == 0) {
return 1;
}
int sum = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i != arr.length; i++) {
sum += arr[i];
min = Math.min(min, arr[i]);
}
// boolean[][] dp ...
int N = arr.length;
boolean[][] dp = new boolean[N][sum + 1];
for (int i = 0; i < N; i++) {// arr[0..i] 0
dp[i][0] = true;
}
dp[0][arr[0]] = true;
for (int i = 1; i < N; i++) {
for (int j = 1; j <= sum; j++) {
dp[i][j] = dp[i - 1][j] || ((j - arr[i] >= 0) ? dp[i - 1][j - arr[i]] : false);
}
}
for (int j = min; j <= sum; j++) {
if (!dp[N - 1][j]) {
return j;
}
}
return sum + 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
题目二题解
先把array排序,正数数组排完序，左边0位置肯定是1
定义变量range =1,表示从1~ 1范围上的正数都能累加出来
range=k,代表1~k上的所有正数都能搞出来
当arr 0位置是1的情况下，range=1,代表1~ 1范围的正数都可以搞出来
如果1位置也是1, range变成2,代表1 ~2范围的正数都可以搞出来
如果2位置也是2, range变成4,代表1 ~4范围的正数都可以搞出来
如果0~ i-1是0~100, range=100
i位置17,可以让range扩充到117
如果0~ i-1能搞定的数是1~100,此时i位置是102,那么101不可以搞定
如果0~ i搞定1~a,如果位置上是b:
1如果b<=a+1,能扩充范围到1~a+b
2咖如果b> a+1. a+1就是搞定不了的最小正整数
public static int unformedSum3(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
Arrays.sort(arr); // O (N * logN)
int range = 1;
// arr[0] == 1
for (int i = 1; i != arr.length; i++) {
if (arr[i] > range + 1) {
return range + 1;
} else {
range += arr[i];
}
}
return range + 1;
}
