LeetCode 330 Patching Array

Posted on | In | 阅读 
给定数组和一个整数n，问需要补多少数，使这个数组内数组合的和可以覆盖1~n

贪心，每次都补入当前（数组中的前i-1个数）不能组合成的最小的数m。

假设数组中前i-1个数以及已经补入的数已经可以覆盖[1, m)，这时候第i个数：

  1. <=m，那么与前面i-1个数的组合就可以覆盖[1, m+nums[i])，现在前i个数就可以达到m+nums[i]
  2. > m，那么补入m，前i-1个数可以达到2*m

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long long m = 1;
        int i = 0;
        int cnt = 0;
        int sz = nums.size();
        while(m <= n) {
            if(i < sz && nums[i] <= m) {
                m += nums[i++];
            }else {
                m <<= 1;
                ++cnt;
            }
        }
        return cnt;
    }
};