leetcode330. Patching Array

DesGemini 發布于2019-08-16 13:56 / 2602人閱讀

摘要：如果當前數組中存在一個數組位于這個范圍中，則我們的數組可以再次擴展到。這里用型避免數組值的溢出。

題目要求

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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
從一道面試題，到“我可能看了假源碼”

摘要：返回的綁定函數也能使用操作符創建對象這種行為就像把原函數當成構造器。同時，將第一個參數以外的其他參數，作為提供給原函數的預設參數，這也是基本的顆?；A。今天想談談一道前端面試題，我做面試官的時候經常喜歡用它來考察面試者的基礎是否扎實，以及邏輯、思維能力和臨場表現，題目是：模擬實現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