x*****0
发帖数: 452 | 1 给你一个int N，然后给你一个int[]，数组里每个元素只能用一次，要求通过加法得到
从1到N的所有数字，返回最少需要添加元素的个数
比如：N = 6，arr = [1, 3]。最少需要添加的元素个数就是1，因为我们只用添加2就
可以了, arr = [1,2,3]。这样所有1到6的元素都能被arr这个数组的subset相加得到。
注意不能使用产生的元素啊。比如说：arr = [1,3] 咱们可以产生4=1+3。 但是不能产
生5（5=4+1），这是非法的。
大家有什么想法吗，最没有效率的方法都想不出来。sad！ | l******s
发帖数: 3045 | 2 try this. The idea is from that for each N, the minimum set of nums are from
1 to x, where x is to make sure Sigma(1,x) == N or just greater than N.
public int minAddition(int N, int[] nums)
{
int i = 1, sum = 0, result = 0;
for(i = 0; sum < N; i++) sum += (result = i + 1);
Array.Sort(nums);
for(int j = 0; j < nums.Length; j++)
if((j == 0 || (j > 0 && nums[j] != nums[j-1])) && nums[j] <= i &&
nums[j] > 0)
result--;
return result;
} | b******b
发帖数: 713 | 3 don't think it's correct, e.g. for N=7, and nums=[1,4], the correct answer
is 1, you just need to add 2 to the array: [1, 2, 4] which can form any
number 1-7.
from
【在 l******s 的大作中提到】
: try this. The idea is from that for each N, the minimum set of nums are from
: 1 to x, where x is to make sure Sigma(1,x) == N or just greater than N.
: public int minAddition(int N, int[] nums)
: {
: int i = 1, sum = 0, result = 0;
: for(i = 0; sum < N; i++) sum += (result = i + 1);
: Array.Sort(nums);
: for(int j = 0; j < nums.Length; j++)
: if((j == 0 || (j > 0 && nums[j] != nums[j-1])) && nums[j] <= i &&
: nums[j] > 0)
| b******b
发帖数: 713 | 4 I feel this is a searching algorithm, so first you generate all the possible
combinations of with the given array, e.g. for [1,4], the possible numbers
can generate is 1, 4, 5 (4+1). now we go through it in order, let's say
number i is missing, then we add number i to the array, and add all existing
numbers +i to the possible values, e.g. in that example, we add 2, and add
3 (1+2), 6 (4+2), 7 (5+2) to the list, then check what's the next missing
number.
use the bitvector to check what's the next missing number should make it
more space efficient.
【在 b******b 的大作中提到】
: don't think it's correct, e.g. for N=7, and nums=[1,4], the correct answer
: is 1, you just need to add 2 to the array: [1, 2, 4] which can form any
: number 1-7.
:
: from
| l******s
发帖数: 3045 | 5 Great catch. I guess just need small modification to handle the case of "
Right Sum + 1". "Right Sum" means 6 (1-3), 10(1-4), 55(1-10), etc.
【在 b******b 的大作中提到】
: don't think it's correct, e.g. for N=7, and nums=[1,4], the correct answer
: is 1, you just need to add 2 to the array: [1, 2, 4] which can form any
: number 1-7.
:
: from
| x*****0
发帖数: 452 | 6 seems that this is a correct solution. Let me think about it.
possible
numbers
existing
add
【在 b******b 的大作中提到】
: I feel this is a searching algorithm, so first you generate all the possible
: combinations of with the given array, e.g. for [1,4], the possible numbers
: can generate is 1, 4, 5 (4+1). now we go through it in order, let's say
: number i is missing, then we add number i to the array, and add all existing
: numbers +i to the possible values, e.g. in that example, we add 2, and add
: 3 (1+2), 6 (4+2), 7 (5+2) to the list, then check what's the next missing
: number.
: use the bitvector to check what's the next missing number should make it
: more space efficient.
| x*****0
发帖数: 452 | 7 seems that this is a correct solution. Let me think about it.
possible
numbers
existing
add
【在 b******b 的大作中提到】
: I feel this is a searching algorithm, so first you generate all the possible
: combinations of with the given array, e.g. for [1,4], the possible numbers
: can generate is 1, 4, 5 (4+1). now we go through it in order, let's say
: number i is missing, then we add number i to the array, and add all existing
: numbers +i to the possible values, e.g. in that example, we add 2, and add
: 3 (1+2), 6 (4+2), 7 (5+2) to the list, then check what's the next missing
: number.
: use the bitvector to check what's the next missing number should make it
: more space efficient.
| x*****0
发帖数: 452 | 8 Let me think about this algorithm. Seems pretty ingenious
from
【在 l******s 的大作中提到】
: try this. The idea is from that for each N, the minimum set of nums are from
: 1 to x, where x is to make sure Sigma(1,x) == N or just greater than N.
: public int minAddition(int N, int[] nums)
: {
: int i = 1, sum = 0, result = 0;
: for(i = 0; sum < N; i++) sum += (result = i + 1);
: Array.Sort(nums);
: for(int j = 0; j < nums.Length; j++)
: if((j == 0 || (j > 0 && nums[j] != nums[j-1])) && nums[j] <= i &&
: nums[j] > 0)
| b***e
发帖数: 1419 | 9 var missing = function(n, a) {
var output = [];
var sum = 0;
var i = 0;
while(true) {
if (i >= a.length || a[i] > sum + 1) {
output.push(sum + 1);
sum += sum + 1;
} else {
sum += a[i];
i++;
}
if (sum >= n) {
break;
}
}
return output;
};
【在 x*****0 的大作中提到】
: 给你一个int N，然后给你一个int[]，数组里每个元素只能用一次，要求通过加法得到
: 从1到N的所有数字，返回最少需要添加元素的个数
: 比如：N = 6，arr = [1, 3]。最少需要添加的元素个数就是1，因为我们只用添加2就
: 可以了, arr = [1,2,3]。这样所有1到6的元素都能被arr这个数组的subset相加得到。
: 注意不能使用产生的元素啊。比如说：arr = [1,3] 咱们可以产生4=1+3。 但是不能产
: 生5（5=4+1），这是非法的。
: 大家有什么想法吗，最没有效率的方法都想不出来。sad！
| b******b
发帖数: 713 | 10 very good solution, nice!
【在 b***e 的大作中提到】
: var missing = function(n, a) {
: var output = [];
: var sum = 0;
: var i = 0;
: while(true) {
: if (i >= a.length || a[i] > sum + 1) {
: output.push(sum + 1);
: sum += sum + 1;
: } else {
: sum += a[i];
| | | h***l
发帖数: 6 | 11 i think it should match 1 2 4 8 16 ....
【在 x*****0 的大作中提到】
: 给你一个int N，然后给你一个int[]，数组里每个元素只能用一次，要求通过加法得到
: 从1到N的所有数字，返回最少需要添加元素的个数
: 比如：N = 6，arr = [1, 3]。最少需要添加的元素个数就是1，因为我们只用添加2就
: 可以了, arr = [1,2,3]。这样所有1到6的元素都能被arr这个数组的subset相加得到。
: 注意不能使用产生的元素啊。比如说：arr = [1,3] 咱们可以产生4=1+3。 但是不能产
: 生5（5=4+1），这是非法的。
: 大家有什么想法吗，最没有效率的方法都想不出来。sad！
| x*****0
发帖数: 452 | 12 can you give me a little bit description about this algorithm?
Seems pretty smart,but without comment, I did not understand.
【在 b******b 的大作中提到】
: very good solution, nice!
| x*****0
发帖数: 452 | 13 can you give me a little bit description about this algorithm?
Seems pretty smart,but without comment, I did not understand.
【在 b***e 的大作中提到】
: var missing = function(n, a) {
: var output = [];
: var sum = 0;
: var i = 0;
: while(true) {
: if (i >= a.length || a[i] > sum + 1) {
: output.push(sum + 1);
: sum += sum + 1;
: } else {
: sum += a[i];
| x*****0
发帖数: 452 | 14 not exactly.
【在 h***l 的大作中提到】
: i think it should match 1 2 4 8 16 ....
| x*****0
发帖数: 452 | 15 How about this case:
arr = [10, 28], N = 33.
Output: 5 ([1, 2, 4, 8, 26])?
from
【在 l******s 的大作中提到】
: try this. The idea is from that for each N, the minimum set of nums are from
: 1 to x, where x is to make sure Sigma(1,x) == N or just greater than N.
: public int minAddition(int N, int[] nums)
: {
: int i = 1, sum = 0, result = 0;
: for(i = 0; sum < N; i++) sum += (result = i + 1);
: Array.Sort(nums);
: for(int j = 0; j < nums.Length; j++)
: if((j == 0 || (j > 0 && nums[j] != nums[j-1])) && nums[j] <= i &&
: nums[j] > 0)
|
|
