成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

321. Create Maximum Number

Cc_2011 / 2304人閱讀

摘要：題目鏈接這題就遍歷所有可能的切分點(diǎn)然后和求到最大值，和分別是有個(gè)數(shù)時(shí)候的最大值，和有個(gè)數(shù)時(shí)的最大值。部分比較簡(jiǎn)單，來看求最大值的部分。設(shè)產(chǎn)生的最大值是，的是，的是?，F(xiàn)在已經(jīng)選了了個(gè)，最大值是，用了個(gè)數(shù)，現(xiàn)在指向。

321. Create Maximum Number

題目鏈接：https://leetcode.com/problems...

這題就遍歷所有可能的切分點(diǎn)n然后mergenums1[n]和nums2[k-n]求到最大值，nums1[n]和nums2[k-n]分別是nums1有n個(gè)數(shù)時(shí)候的最大值，和nums2有k-n個(gè)數(shù)時(shí)的最大值。merge部分比較簡(jiǎn)單，來看求最大值的部分。
設(shè)產(chǎn)生的最大值是max，max的size是n，num的size是m?，F(xiàn)在已經(jīng)選了了i個(gè)digit，最大值是max[0:i]，num用了j個(gè)數(shù)，現(xiàn)在指向num[j]。那么這就是用stack可以解決的問題了，如果stack的top元素小于num[j]且剩下的digits還夠的話，那就一直pop，然后把num[j]放進(jìn)棧頂，剩下的digits夠的條件是：m - j >= n - i，所以可以pop的條件也就是：
while(i > 0 && m - j > n - i && num[j] > max[i])

現(xiàn)在來確定切分點(diǎn)n的范圍：0 <= n <= nums1.length并且0 <= k - n <= nums2.length，也就是k - num2.length <= n <= k，所以最后n的范圍是：max(0, k-num2.length) <= n <= min(nums1.length, k)

merge的時(shí)候注意，如果兩個(gè)array里面當(dāng)前int相同，要比較它們之后的數(shù)字，選大的。

參考：
https://discuss.leetcode.com/...

public class Solution {
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {
        int[] global = new int[k];
        if(k == 0) return global;
        
        for(int n = Math.max(0, k-nums2.length); n <= Math.min(nums1.length, k); n++) {
            int[] max1 = getLocalMax(nums1, n);
            int[] max2 = getLocalMax(nums2, k-n);
        
            int[] temp = merge(max1, max2);
            if(greater(temp, 0, global, 0)) global = temp;
        }
        
        return global;
    }
    
    private boolean greater(int[] a, int i, int[] b, int j) {
        while(i < a.length && j < b.length) {
            if(a[i] > b[j]) return true;
            else if(a[i] < b[j]) return false;
            i++; j++;
        }
        // equal is false
        return i < a.length;
    }
    
    private int[] getLocalMax(int[] num, int n) {
        int[] res = new int[n];
        int m = num.length;
        int i = 0;
        for(int j = 0; j < m; j++) {
            while(i > 0 && m - j > n - i && num[j] > res[i-1]) i--;
            if(i < n) res[i++] = num[j];
        }
        return res;
    }
    
    private int[] merge(int[] num1, int[] num2) {
        int n1 = num1.length, n2 = num2.length;
        int[] res = new int[n1+n2];
        
        int i = 0, j = 0;
        for(int k = 0; k < res.length; k++) {
            if(i >= n1) res[k] = num2[j++];
            else if(j >= n2) res[k] = num1[i++];
            else res[k] = greater(num1, i, num2, j) ? num1[i++] : num2[j++];
        }
        return res;
    }
}

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

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

相關(guān)文章

  • LeetCode[321] Create Maximum Number

    摘要：算法復(fù)雜度思路貪心算法，先能組成的數(shù)的組合，然后針對(duì)每一個(gè)組合，考慮每一個(gè)數(shù)組能夠組成的最大的位或者位數(shù)。對(duì)不同組合生成的最大數(shù)進(jìn)行比較，得到所能得到的最大的值。代碼的方法去找這個(gè)數(shù)。 LeetCode[321] Create Maximum Number Given two arrays of length m and n with digits 0-9 representing ...

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

  • leetcode 321. Create Maximum Number

    摘要：題目要求思路和代碼首先采用分治法的思路，我們知道這個(gè)數(shù)字中，必然有個(gè)數(shù)組來自，而剩下的個(gè)數(shù)字必然來自。那么問題變成從中獲取個(gè)數(shù)，這個(gè)數(shù)構(gòu)成的數(shù)字最大，且這個(gè)數(shù)字的相對(duì)位置不變。 題目要求 Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum numb...

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

  • [leetcode]321. Create Maximum Number

    摘要：題目意思從兩個(gè)數(shù)組中，保持元素相對(duì)位置不變的前提下，找到一個(gè)長度為的最大數(shù)組。我們每次取兩個(gè)數(shù)組中剩下的最靠前元素里較大的一個(gè)。合并之前結(jié)果，得到一個(gè)長度為的最大數(shù)組。三個(gè)不同的函數(shù)分別用于取，合并，比較。 Given two arrays of length m and n with digits 0-9 representing two numbers. Create the m...

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

  • 細(xì)節(jié)：js 對(duì)象繼承的幾種模式舉例

    摘要：原型鏈繼承借用構(gòu)造函數(shù)偽造對(duì)象，經(jīng)典繼承無參數(shù)有參數(shù)組合繼承偽經(jīng)典繼承無參數(shù)有參數(shù)寄生組合式繼承引用類型最理想的范式或者可以把函數(shù)寫成下面這樣原型式繼承用于共享引用類型的值，與寄生式類似傳統(tǒng)版先定義函數(shù)，再繼承版直接用，再繼承省略了定義函數(shù) 原型鏈繼承 function Person(){}; Person.prototype = { constructor: Person,...

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

  • ECMAScript6 新特性——“數(shù)值的擴(kuò)展”

    摘要：二進(jìn)制和八進(jìn)制表示法提供了二進(jìn)制和八進(jìn)制數(shù)值的新的寫法，分別用前綴或和或表示。用來檢查是否為有窮以及是否為這兩個(gè)新方法只對(duì)數(shù)值有效，非數(shù)值一律返回。引入了和這兩個(gè)常量，用來表示這個(gè)范圍的上下限。因?yàn)橛芯认拗?，超過的次方的值無法精確表示。 1 二進(jìn)制和八進(jìn)制表示法 ES6提供了二進(jìn)制和八進(jìn)制數(shù)值的新的寫法，分別用前綴0b（或0B）和0o（或0O）表示。 console.log(0b10...

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

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

0條評(píng)論

閱讀需要支付1元查看
<