leetcode 330. Patching Array 最小的添加/删除次数使sum为1到n + 一个很棒很值的做法-蒲公英云

leetcode 330. Patching Array 最小的添加/删除次数使sum为1到n + 一个很棒很值的做法

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 = [1, 3], n = 6
Return 1.

Combinations of nums are [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 = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Example 3:
nums = [1, 2, 2], n = 5
Return 0.

这里给定一个数组，问经过几次的添加/删除数组元素，从而可以满足1到n的某一个数组可以有数组元素相加得到。

我是想不到怎么做的，网上看到了一个做法，发现很棒，但是我肯定给自己想不到这个问题的做法，所以就先记住吧。

这道题十分的棒，解决方法也很棒，很值得学习

代码如下：

/*
 * 我们可以试着从1到n检查每个数（记为current）是否满足。
 * 对于每一个current，先从输入数组nums中查看是否有满足条件的数
 * （即是否nums[i] <= current，i表示nums数组中的数用到第几个，初始为0），
 * 若有则使用并进行i++、current += nums[i]（current至current + nums - 1可
 * 由current-nums[i]到current - 1分别加上nums[i]得到）操作；若无则添加新元素current
 * 并进行current = current * 2操作。具体的，扫描数组nums，更新原则如下：
 * 
 *     若nums[i] <= current , 则把nums[i]用掉（即 i++），同时current更新为current + nums[i];
 *     若nums[i] > current，则添加新的元素current，同时current更新为current * 2.
 * */
public class Solution 
{
    public int minPatches(int[] nums, int n) 
    {
        if(nums==null)
            return 0;
        long current=1;
        int i=0,count=0;
        while(current<=n)
        {
            if(i<nums.length && nums[i]<=current)
            {
                current+=nums[i];
                i++;
            }else 
            {
                count++;
                current*=2;
            }
        }
        return count;
    }
}

下面是C++的做法，注意加法可能越界，所以要使用long long 类型来处理
对于cur*=2这一步是这样考虑的：没有发现当前元素nums[i] <= cur，那么就添加cur这个元素，所以cur+=cur。

注意注意cur的类型，累加求和需要long long类型

代码如下：

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <climits>
#include <algorithm>
#include <sstream>
#include <functional>
#include <bitset>
#include <numeric>
#include <cmath>
#include <regex>
using namespace std;
class Solution 
{
public:
    int minPatches(vector<int>& nums, int n) 
    {
        long long current = 1, count = 0, i = 0;
        while (current <= n)
        {
            if (i < nums.size() && nums[i] <= current)
            {
                current += nums[i];
                i++;
            }
            else
            {
                count++;
                current = current * 2;
            }
        }
        return count;
    }
};