Leetcode 321. Create Maximum Num
2021-02-02 本文已影响0人
SnailTyan
文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Create Maximum Number
2. Solution
解析：
- 首先将问题分解为两个子问题，即分别求两个序列的最大值，得到两个子序列（保留顺序），两个子序列的长度和为
k。 - 合并两个子序列
- 比较所有合并后的序列，返回值最大的序列
- Version 1
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
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
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
