leetcode330. Patching Array

DesGemini 发布于2019-08-16 13:56 / 2614人阅读

摘要：如果当前数组中存在一个数组位于这个范围中，则我们的数组可以再次扩展到。这里用型避免数组值的溢出。

题目要求

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:

Input: nums = [1,3], n = 6
Output: 1 
Explanation:
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:

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].
Example 3:

Input: nums = [1,2,2], n = 5
Output: 0

假设有一个有序的正整数数组nums和一个整数n，最少添加几个元素到这个数组中，使得从1-n的所有整数都可以由这个数组中的值的或是几个值的和构成。

思路和代码

这里的核心思路在于如何找到一个规律，使得我们可以在前一个规律的基础上添加一个数达到下一个范围。假设当前的数组可以组成从[1...k]的所有整数，那么我们下一步如果往数组中添加x，则数组就可以组成从[1...k+x]的所有整数。因此，为了只打最少的补丁，我们会希望每一次往数组中添加的元素所能够到达的范围越远越好，因此我们会patch一个k+1上去从而使得数组最远扩展到[1...2k+1]。如果当前数组中存在一个数组m位于[k+1, 2k+1]这个范围中，则我们的数组可以再次扩展到[1...2k+m+1]。

    public int minPatches(int[] nums, int n) {
        int count = 0;
        long max = 0;
        int index = 0;
        while(max < n) {
            if(index= nums[index]) {
                max += nums[index++];
            } else {
                count++;
                max += max + 1;
            }
            
        }
        return count;
    }

这里需要注意的细节是数组的溢出。这里用long型避免数组值的溢出。

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

云服务器 GPU云服务器 Patching Leetcod LeetCode LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72602.html

330. Patching Array

330. Patching Array 题目链接：https://leetcode.com/problems... 想了半天没想出来，参考discussion里的解法：https://discuss.leetcode.com/... public class Solution { public int minPatches(int[] nums, int n) { int ...

李昌杰 2019-08-19 10:45 评论0 收藏0
php上传图片到微博图床

摘要：今天就用来上传图片到微博，这也是来自的一个问题里面还提到一个版本有种方式实现上传图片如果要用这个的话参数必须是，值为经过编码后的字符串。使用上传登录微博获取就是微博图片，访问即可打开图片这里我上传的是的广告图。微博是个好图床，上传后就可以通过一个url来访问了。今天就用php来上传图片到微博，这也是来自sf的一个问题, 里面还提到一个python版本. 有2种方式实现上传图片: 如...

mudiyouyou 2019-06-27 15:34 评论0 收藏0
从一道面试题，到“我可能看了假源码”

摘要：返回的绑定函数也能使用操作符创建对象这种行为就像把原函数当成构造器。同时，将第一个参数以外的其他参数，作为提供给原函数的预设参数，这也是基本的颗粒化基础。今天想谈谈一道前端面试题，我做面试官的时候经常喜欢用它来考察面试者的基础是否扎实，以及逻辑、思维能力和临场表现，题目是：模拟实现ES5中原生bind函数。也许这道题目已经不再新鲜，部分读者也会有思路来解答。社区上关于原生bind的研...

Carson 2019-08-20 14:23 评论0 收藏0
从一道面试题，到“我可能看了假源码”

摘要：返回的绑定函数也能使用操作符创建对象这种行为就像把原函数当成构造器。同时，将第一个参数以外的其他参数，作为提供给原函数的预设参数，这也是基本的颗粒化基础。今天想谈谈一道前端面试题，我做面试官的时候经常喜欢用它来考察面试者的基础是否扎实，以及逻辑、思维能力和临场表现，题目是：模拟实现ES5中原生bind函数。也许这道题目已经不再新鲜，部分读者也会有思路来解答。社区上关于原生bind的研...

rockswang 2019-08-30 15:52 评论0 收藏0
从一道面试题，到“我可能看了假源码”

摘要：返回的绑定函数也能使用操作符创建对象这种行为就像把原函数当成构造器。同时，将第一个参数以外的其他参数，作为提供给原函数的预设参数，这也是基本的颗粒化基础。今天想谈谈一道前端面试题，我做面试官的时候经常喜欢用它来考察面试者的基础是否扎实，以及逻辑、思维能力和临场表现，题目是：模拟实现ES5中原生bind函数。也许这道题目已经不再新鲜，部分读者也会有思路来解答。社区上关于原生bind的研...

jlanglang 2019-08-01 16:21 评论0 收藏0