pydata

Keep Looking, Don't Settle

leetcode 321. Create Maximum Number

321. Create Maximum Number

题目大意 给定长度为m和n的两个数组，数组里面数字为0到9.要求从这两个数组里面去k个数字构成的数字的最大值。k<=m+n。题目要求新的数字的顺序跟原来数组的数字顺序保持一致。

比如数组1为：nums1 = [3, 4, 6, 5]，数组2为nums2 = [9, 1, 2, 5, 8, 3]，给定k = 5，那么结果应该为 [9, 8, 6, 5, 3]

解题思路：这个问题可以转化为两个子问题

  1. 从数组nums1中找出k个元素的子数组，保持顺序不变，并且使得子数组的值最大 (getK)

  2. 合并从nums1和nums2按上面方法取得的子数组(长度分别为k1和k-k1)，使得合并以后的数组最大

最后对k1进行迭代就可以了

动态规划

class Solution(object):
    def maxNumber(self, nums1, nums2, k):

        def getK(nums, k):
            n = len(nums)
            to_pop = n - k
            ans = []
            for num in nums:
                while len(ans) > 0 and num > ans[-1] and to_pop > 0:
                    to_pop -= 1
                    ans.pop()
                ans.append(num)
            return ans[:k]

        def getMax(nums1, nums2):
            ans = []
            while nums1 and nums2:
                if nums1 > nums2:
                    ans.append(nums1.pop(0))
                else:
                    ans.append(nums2.pop(0))
            if nums1:
                ans += nums1
            else:
                ans += nums2
            return ans

        n1 = len(nums1)
        n2 = len(nums2)
        ans = []
        for k1 in range(k+1):
            k2 = k - k1
            if k1 > n1 or k2 > n2:
                continue
            ans = max(ans, getMax(getK(nums1, k1), getK(nums2, k2)))
        return ans

getK和getMax还可以这么写：

getK函数还可以这么写：

def getK(nums, k):
    n = len(nums)
    ans = [0 for _ in range(k)]
    j = 0
    for i in range(n):
        while(j > 0 and ans[j-1] < nums[i] and n - i > k - j):
            j -= 1
        if j < k:
            ans[j] = nums[i]
            j += 1
    return ans

getMax，从两个数组里面优先取较大的元素合并的方程:

def getMax(nums1, nums2):
    ans = []
    while nums1 or nums2:
        if nums1 > nums2:
            ans += nums1[0],
            nums1 = nums1[1:]
        else:
            ans += nums2[0],
            nums2 = nums2[1:]
    return ans

getMax还可以这么写：

def getMax(nums1, nums2):
    return [max(nums1, nums2).pop(0) for _ in nums1 + nums2]