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

深碍√TFBOYSˉ_ 2022-06-07 01:10 62阅读 0赞

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;
        }
    };