leetcode330-- Patching Array (Hard)(这个题目的想法非常精妙!)

leetcode330-- Patching Array (Hard)(这个题目的想法非常精妙!)

题目的意思是给定一个数组A,里面都是正整数,从小到大是排好顺序的,然后给定一个整数n, 然后现在往数组里面加元素,问最少加多少个元素使得这个数组中的数字的组合的和可以遍历1到n. 注意不能够重复使用,不然无论A什么样,把1放进去就可以了。

这个题目挺难的,直接看的网上的解答,思路是

定义一个变量miss,它代表当前能表示的数字的范围[1,miss),所以应该把它初始化为1.然后会和数组里面的元素进行比较,

如果数组中的第i个元素nums[i]<=miss, 那么说明这之后,能表示的数字的范围变成了[1, miss+nums[i]), 即把miss更新成miss+nums[i], 然后如果nums[i]>miss的话,说明目前的这个元素 nums[i] 是我们表示不了的,为了扩大表示范围,那么就需要往里面加入元素了,比如说当前的表示范围是[1,7),数组是[1,2,3,10] n为20, 当前的i是3,nums[i]=10>7,

在7和10之间有一个gap,这时候我们需要加元素,应该加什么呢?加小于等于7的没有必要,加大于7的,比如加8,那么这时候7没有表示,所以应该加7进去,也就是说这时候应该加入miss,从而表示范围就变成了,[1,miss+miss), 即这时候将miss += miss进行更新,这时候表示范围变成了[1,14),然后因为10<14,所以表示范围变成了[1,24) 24这时候已经超过了20,所以停止,也就是说最终只是加入了一个7就可以了。

整个代码如下

class Solution(object):
    def minPatches(self, nums, n):
        """
        :type nums: List[int]
        :type n: int
        :rtype: int
        """
        miss = 1
        add = 0
        k = 0
          
        while(miss<=n):
            if(k<len(nums) and nums[k]<=miss):
                miss += nums[k]
                k += 1
            else:   # 注意在这种情况下不需要更新k的值. 
                    # 但是这时候因为 miss <nums[k], 需要往里面加入miss这个元素了,所以add += 1.
                miss += miss
                add += 1
        return add
        

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦