Python | Leetcode Python题解之第321题拼接最大数
标题：https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNGM1MDVmOGI0MDY3NDJkYTgxMjc2ZjVhNGZlMTIyM2MucG5n
题解：
class Solution:
def maxNumber(self, nums1: List, nums2: List, k: int) -> List:
m, n = len(nums1), len(nums2)
maxSubsequence = * k
start, end = max(0, k - n), min(k, m)
for i in range(start, end + 1):
subsequence1 = self.getMaxSubsequence(nums1, i)
subsequence2 = self.getMaxSubsequence(nums2, k - i)
curMaxSubsequence = self.merge(subsequence1, subsequence2)
if self.compare(curMaxSubsequence, 0, maxSubsequence, 0) > 0:
maxSubsequence = curMaxSubsequence
return maxSubsequence
def getMaxSubsequence(self, nums: List, k: int) -> int:
stack = * k
top = -1
remain = len(nums) - k
for i, num in enumerate(nums):
while top >= 0 and stack < num and remain > 0:
top -= 1
remain -= 1
if top < k - 1:
top += 1
stack = num
else:
remain -= 1
return stack
def merge(self, subsequence1: List, subsequence2: List) -> List:
x, y = len(subsequence1), len(subsequence2)
if x == 0:
return subsequence2
if y == 0:
return subsequence1
mergeLength = x + y
merged = list()
index1 = index2 = 0
for _ in range(mergeLength):
if self.compare(subsequence1, index1, subsequence2, index2) > 0:
merged.append(subsequence1)
index1 += 1
else:
merged.append(subsequence2)
index2 += 1
return merged
def compare(self, subsequence1: List, index1: int, subsequence2: List, index2: int) -> int:
x, y = len(subsequence1), len(subsequence2)
while index1 < x and index2 < y:
difference = subsequence1 - subsequence2
if difference != 0:
return difference
index1 += 1
index2 += 1
return (x - index1) - (y - index2)
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金
页:
[1]