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/
如果有收获,可以请我喝杯咖啡!