Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range
[1, n]
inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.
Example 1:
nums =
Return
nums =
[1, 3]
, n = 6
Return
1
.
Combinations of nums are
Now if we add/patch
Possible sums are
So we only need
[1], [3], [1,3]
, which form possible sums of: 1, 3, 4
.Now if we add/patch
2
to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3]
.Possible sums are
1, 2, 3, 4, 5, 6
, which now covers the range [1, 6]
.So we only need
1
patch.
Example 2:
nums =
Return
The two patches can be
nums =
[1, 5, 10]
, n = 20
Return
2
.The two patches can be
[2, 4]
.
Example 3:
nums =
Return
nums =
[1, 2, 2]
, n = 5
Return
0
.
A:
Sol 1 : 挨个找,如果找不到,就加入。但是这样不能保证最优。Sol 2: 保持found list,和non-found list, 找出加入一个数字,可以保证满足最多的(可是这样
但是这样,一是麻烦,而是不保证正确,三是LTE
Sol 3:
public class Solution { public int minPatches(int[] nums, int n) { int count = 0, i = 0; long findMaxRight = 1;// this maxRight has not been found yet while(findMaxRight <= n){ if( i<nums.length && nums[i] <= findMaxRight ){ findMaxRight += nums[i++]; }else{ findMaxRight = 2*findMaxRight; count++; } } return count; } }
Mistakes:
1: findMaxRight is exclusive. thus its initial value can be set to 1. WTF
2: use long , instead of int , to avoid overflow.
No comments:
Post a Comment