亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

leetcode330. Patching Array

DesGemini / 2655人閱讀

摘要：如果當(dāng)前數(shù)組中存在一個(gè)數(shù)組位于這個(gè)范圍中，則我們的數(shù)組可以再次擴(kuò)展到。這里用型避免數(shù)組值的溢出。

題目要求 
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

假設(shè)有一個(gè)有序的正整數(shù)數(shù)組nums和一個(gè)整數(shù)n，最少添加幾個(gè)元素到這個(gè)數(shù)組中，使得從1-n的所有整數(shù)都可以由這個(gè)數(shù)組中的值的或是幾個(gè)值的和構(gòu)成。

思路和代碼

這里的核心思路在于如何找到一個(gè)規(guī)律，使得我們可以在前一個(gè)規(guī)律的基礎(chǔ)上添加一個(gè)數(shù)達(dá)到下一個(gè)范圍。假設(shè)當(dāng)前的數(shù)組可以組成從[1...k]的所有整數(shù)，那么我們下一步如果往數(shù)組中添加x，則數(shù)組就可以組成從[1...k+x]的所有整數(shù)。因此，為了只打最少的補(bǔ)丁，我們會(huì)希望每一次往數(shù)組中添加的元素所能夠到達(dá)的范圍越遠(yuǎn)越好，因此我們會(huì)patch一個(gè)k+1上去從而使得數(shù)組最遠(yuǎn)擴(kuò)展到[1...2k+1]。如果當(dāng)前數(shù)組中存在一個(gè)數(shù)組m位于[k+1, 2k+1]這個(gè)范圍中，則我們的數(shù)組可以再次擴(kuò)展到[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;
    }

這里需要注意的細(xì)節(jié)是數(shù)組的溢出。這里用long型避免數(shù)組值的溢出。


想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/72602.html

相關(guān)文章

  • 330. Patching Array

    330. Patching Array 題目鏈接：https://leetcode.com/problems... 想了半天沒(méi)想出來(lái)，參考discussion里的解法：https://discuss.leetcode.com/... public class Solution { public int minPatches(int[] nums, int n) { int ...

    李昌杰 評(píng)論0 收藏0

  • php上傳圖片到微博圖床

    摘要：今天就用來(lái)上傳圖片到微博，這也是來(lái)自的一個(gè)問(wèn)題里面還提到一個(gè)版本有種方式實(shí)現(xiàn)上傳圖片如果要用這個(gè)的話參數(shù)必須是，值為經(jīng)過(guò)編碼后的字符串。使用上傳登錄微博獲取就是微博圖片，訪問(wèn)即可打開圖片這里我上傳的是的廣告圖。 微博是個(gè)好圖床，上傳后就可以通過(guò)一個(gè)url來(lái)訪問(wèn)了。今天就用php來(lái)上傳圖片到微博，這也是來(lái)自sf的一個(gè)問(wèn)題, 里面還提到一個(gè)python版本. 有2種方式實(shí)現(xiàn)上傳圖片: 如...

    mudiyouyou 評(píng)論0 收藏0

  • 從一道面試題，到“我可能看了假源碼”

    摘要：返回的綁定函數(shù)也能使用操作符創(chuàng)建對(duì)象這種行為就像把原函數(shù)當(dāng)成構(gòu)造器。同時(shí)，將第一個(gè)參數(shù)以外的其他參數(shù)，作為提供給原函數(shù)的預(yù)設(shè)參數(shù)，這也是基本的顆粒化基礎(chǔ)。 今天想談?wù)勔坏狼岸嗣嬖囶}，我做面試官的時(shí)候經(jīng)常喜歡用它來(lái)考察面試者的基礎(chǔ)是否扎實(shí)，以及邏輯、思維能力和臨場(chǎng)表現(xiàn)，題目是：模擬實(shí)現(xiàn)ES5中原生bind函數(shù)。也許這道題目已經(jīng)不再新鮮，部分讀者也會(huì)有思路來(lái)解答。社區(qū)上關(guān)于原生bind的研...

    Carson 評(píng)論0 收藏0

  • 從一道面試題，到“我可能看了假源碼”

    摘要：返回的綁定函數(shù)也能使用操作符創(chuàng)建對(duì)象這種行為就像把原函數(shù)當(dāng)成構(gòu)造器。同時(shí)，將第一個(gè)參數(shù)以外的其他參數(shù)，作為提供給原函數(shù)的預(yù)設(shè)參數(shù)，這也是基本的顆?；A(chǔ)。 今天想談?wù)勔坏狼岸嗣嬖囶}，我做面試官的時(shí)候經(jīng)常喜歡用它來(lái)考察面試者的基礎(chǔ)是否扎實(shí)，以及邏輯、思維能力和臨場(chǎng)表現(xiàn)，題目是：模擬實(shí)現(xiàn)ES5中原生bind函數(shù)。也許這道題目已經(jīng)不再新鮮，部分讀者也會(huì)有思路來(lái)解答。社區(qū)上關(guān)于原生bind的研...

    rockswang 評(píng)論0 收藏0

  • 從一道面試題，到“我可能看了假源碼”

    摘要：返回的綁定函數(shù)也能使用操作符創(chuàng)建對(duì)象這種行為就像把原函數(shù)當(dāng)成構(gòu)造器。同時(shí)，將第一個(gè)參數(shù)以外的其他參數(shù)，作為提供給原函數(shù)的預(yù)設(shè)參數(shù)，這也是基本的顆粒化基礎(chǔ)。 今天想談?wù)勔坏狼岸嗣嬖囶}，我做面試官的時(shí)候經(jīng)常喜歡用它來(lái)考察面試者的基礎(chǔ)是否扎實(shí)，以及邏輯、思維能力和臨場(chǎng)表現(xiàn)，題目是：模擬實(shí)現(xiàn)ES5中原生bind函數(shù)。也許這道題目已經(jīng)不再新鮮，部分讀者也會(huì)有思路來(lái)解答。社區(qū)上關(guān)于原生bind的研...

    jlanglang 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<