Leetcode 321. Create Maximum Number

| |
Leetcode 321. Create Maximum Number

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

Create Maximum Number

2. Solution

解析：

  1. 首先将问题分解为两个子问题，即分别求两个序列的最大值，得到两个子序列（保留顺序），两个子序列的长度和为k。
  2. 合并两个子序列
  3. 比较所有合并后的序列，返回值最大的序列
  • Version 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution:
    def maxNumber(self, nums1, nums2, k):
        result = []
        m = len(nums1)
        n = len(nums2)
        for i in range(k + 1):
            if i > m or k - i > n:
                continue
            candidate = self.merge(self.getMaxNumber(nums1, i), self.getMaxNumber(nums2, k - i))
            result = max(result, candidate)
        return result
    def merge(self, nums1, nums2):
        result = []
        while nums1 or nums2:
            if self.compare(nums1, nums2):
                result.append(nums1.pop(0))
            else:
                result.append(nums2.pop(0))
        return result
    def compare(self, nums1, nums2):
        m = len(nums1)
        n = len(nums2)
        min_value = min(m, n)
        for i in range(min_value):
            if nums1[i] > nums2[i]:
                return True
            if nums1[i] < nums2[i]:
                return False
        if m >= n:
            return True
        return False
    def getMaxNumber(self, nums, k):
        nums = nums[:]
        if len(nums) == k:
            return nums
        result = []
        while k > 0:
            length = len(nums)
            max_value = nums[0]
            max_index = 0
            for index, num in enumerate(nums):
                if length - index < k:
                    break
                if num > max_value:
                    max_value = num
                    max_index = index
            nums = nums[max_index + 1:]
            result.append(max_value)
            k -= 1
        return result
  • Version 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution:
    def maxNumber(self, nums1, nums2, k):
        result = []
        m = len(nums1)
        n = len(nums2)
        for i in range(k + 1):
            if i > m or k - i > n:
                continue
            candidate = self.merge(self.getMaxNumber(nums1, i), self.getMaxNumber(nums2, k - i))
            result = max(result, candidate)
        return result
    def merge(self, a, b):
        result = []
        while a or b:
            if self.compare(a, b):
                result.append(a.pop(0))
            else:
                result.append(b.pop(0))
        return result
    def compare(self, a, b):
        if max(a, b) == a:
            return True
        else:
            return False
    def getMaxNumber(self, nums, k):
        nums = nums[:]
        if len(nums) == k:
            return nums
        result = []
        while k > 0:
            length = len(nums)
            max_value = nums[0]
            max_index = 0
            for index, num in enumerate(nums):
                if length - index < k:
                    break
                if num > max_value:
                    max_value = num
                    max_index = index
            nums = nums[max_index + 1:]
            result.append(max_value)
            k -= 1
        return result
  • Version 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def maxNumber(self, nums1, nums2, k):
        result = []
        m = len(nums1)
        n = len(nums2)
        for i in range(k + 1):
            if i > m or k - i > n:
                continue
            candidate = self.merge(self.getMaxNumber(nums1, i), self.getMaxNumber(nums2, k - i))
            result = max(result, candidate)
        return result
    def merge(self, a, b):
        return [max(a, b).pop(0) for i in range(len(a) + len(b))]
    def getMaxNumber(self, nums, k):
        nums = nums[:]
        if len(nums) == k:
            return nums
        result = []
        while k > 0:
            length = len(nums)
            max_value = nums[0]
            max_index = 0
            for index, num in enumerate(nums):
                if length - index < k:
                    break
                if num > max_value:
                    max_value = num
                    max_index = index
            nums = nums[max_index + 1:]
            result.append(max_value)
            k -= 1
        return result

Reference

  1. https://leetcode.com/problems/create-maximum-number/
如果有收获，可以请我喝杯咖啡！