321. Create Maximum Number

Cc_2011 发布于2019-08-14 17:36 / 2275人阅读

摘要：题目链接这题就遍历所有可能的切分点然后和求到最大值，和分别是有个数时候的最大值，和有个数时的最大值。部分比较简单，来看求最大值的部分。设产生的最大值是，的是，的是。现在已经选了了个，最大值是，用了个数，现在指向。

321. Create Maximum Number

题目链接：https://leetcode.com/problems...

这题就遍历所有可能的切分点n然后mergenums1[n]和nums2[k-n]求到最大值，nums1[n]和nums2[k-n]分别是nums1有n个数时候的最大值，和nums2有k-n个数时的最大值。merge部分比较简单，来看求最大值的部分。
设产生的最大值是max，max的size是n，num的size是m。现在已经选了了i个digit，最大值是max[0:i]，num用了j个数，现在指向num[j]。那么这就是用stack可以解决的问题了，如果stack的top元素小于num[j]且剩下的digits还够的话，那就一直pop，然后把num[j]放进栈顶，剩下的digits够的条件是：m - j >= n - i，所以可以pop的条件也就是：
while(i > 0 && m - j > n - i && num[j] > max[i])

现在来确定切分点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的时候注意，如果两个array里面当前int相同，要比较它们之后的数字，选大的。

参考：
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;
    }
}

云服务器 GPU云服务器 Maximum create timerfd_create create_function

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

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

LeetCode[321] Create Maximum Number

摘要：算法复杂度思路贪心算法，先能组成的数的组合，然后针对每一个组合，考虑每一个数组能够组成的最大的位或者位数。对不同组合生成的最大数进行比较，得到所能得到的最大的值。代码的方法去找这个数。 LeetCode[321] Create Maximum Number Given two arrays of length m and n with digits 0-9 representing ...

UsherChen 2019-08-14 16:38 评论0 收藏0
leetcode 321. Create Maximum Number

摘要：题目要求思路和代码首先采用分治法的思路，我们知道这个数字中，必然有个数组来自，而剩下的个数字必然来自。那么问题变成从中获取个数，这个数构成的数字最大，且这个数字的相对位置不变。题目要求 Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum numb...

iamyoung001 2019-08-16 11:06 评论0 收藏0
[leetcode]321. Create Maximum Number

摘要：题目意思从两个数组中，保持元素相对位置不变的前提下，找到一个长度为的最大数组。我们每次取两个数组中剩下的最靠前元素里较大的一个。合并之前结果，得到一个长度为的最大数组。三个不同的函数分别用于取，合并，比较。 Given two arrays of length m and n with digits 0-9 representing two numbers. Create the m...

codeGoogle 2019-08-14 16:52 评论0 收藏0
细节：js 对象继承的几种模式举例

摘要：原型链继承借用构造函数伪造对象，经典继承无参数有参数组合继承伪经典继承无参数有参数寄生组合式继承引用类型最理想的范式或者可以把函数写成下面这样原型式继承用于共享引用类型的值，与寄生式类似传统版先定义函数，再继承版直接用，再继承省略了定义函数原型链继承 function Person(){}; Person.prototype = { constructor: Person,...

Backache 2019-08-21 10:49 评论0 收藏0
ECMAScript6 新特性——“数值的扩展”

摘要：二进制和八进制表示法提供了二进制和八进制数值的新的写法，分别用前缀或和或表示。用来检查是否为有穷以及是否为这两个新方法只对数值有效，非数值一律返回。引入了和这两个常量，用来表示这个范围的上下限。因为有精度限制，超过的次方的值无法精确表示。 1 二进制和八进制表示法 ES6提供了二进制和八进制数值的新的写法，分别用前缀0b（或0B）和0o（或0O）表示。 console.log(0b10...

Dean 2019-08-19 18:02 评论0 收藏0