当前位置：首页 > news >正文

Python每日一练(20230311)

news 2025/9/4 13:54:15

1. 合并两个有序数组

2. 二叉树的右视图

3. 拼接最大数

🌟 每日一练刷题专栏

C/C++ 每日一练专栏

Python 每日一练专栏

1. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[i] <= 10^9

代码：

class Solution(object):def merge(self, nums1, m, nums2, n):""":type nums1: List[int]:type m: int:type nums2: List[int]:type n: int:rtype: void Do not return anything, modify nums1 in-place instead."""p1, p2 = m - 1, n - 1pos = m + n - 1while p1 >= 0 and p2 >= 0:if nums1[p1] >= nums2[p2]:nums1[pos] = nums1[p1]p1 -= 1else:nums1[pos] = nums2[p2]p2 -= 1pos -= 1while p2 >= 0:nums1[pos] = nums2[p2]p2 -= 1pos -= 1return nums1# %%
s = Solution()
print(s.merge(nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3))

输出：

[1, 2, 2, 3, 5, 6]

2. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

提示:

二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

代码：

class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def rightSideView(self, root: TreeNode) -> list:if not root:return []res = []curnode = [root]nexnode = []res.append(curnode[0].val)while curnode:for s in curnode:if s.right:nexnode.append(s.right)if s.left:nexnode.append(s.left)if nexnode:res.append(nexnode[0].val)curnode = nexnodenexnode = []return resdef listToTree(lst: list) -> TreeNode:if not lst:return Noneroot = TreeNode(lst[0])queue = [root]i = 1while i < len(lst):node = queue.pop(0)if lst[i] is not None:node.left = TreeNode(lst[i])queue.append(node.left)i += 1if i < len(lst) and lst[i] is not None:node.right = TreeNode(lst[i])queue.append(node.right)i += 1return rootdef inorderTraversal(root: TreeNode) -> list:if not root:return []res = []res += inorderTraversal(root.left)res.append(root.val)res += inorderTraversal(root.right)return res# %%
s = Solution()
null = Nonenums = [1,2,3,null,5,null,4]
root = listToTree(nums)
print(s.rightSideView(root))
print(inorderTraversal(root))  #testnums = [1,null,3]
root = listToTree(nums)
print(s.rightSideView(root))
print(inorderTraversal(root))  #test

输出：

[1, 3, 4]
[2, 5, 1, 3, 4]
[1, 3]
[1, 3]

3. 拼接最大数

给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度。

示例 1:

输入:
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
输出:[9, 8, 6, 5, 3]

示例 2:

输入:
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
输出:[6, 7, 6, 0, 4]

示例 3:

输入:
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
输出:[9, 8, 9]

代码：

class Solution:def maxNumber(self, nums1: list, nums2: list, k: int) -> list:def pick_max(nums, k):stack = []drop = len(nums) - kfor num in nums:while drop and stack and stack[-1] < num:stack.pop()drop -= 1stack.append(num)return stack[:k]def merge(A, B):lst = []while A or B:bigger = A if A > B else Blst.append(bigger[0])bigger.pop(0)return lstreturn max(merge(pick_max(nums1, i), pick_max(nums2, k - i))for i in range(k + 1)if i <= len(nums1) and k - i <= len(nums2))
# %%
s = Solution()
print(s.maxNumber(nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5))
print(s.maxNumber(nums1 = [6,7], nums2 = [6,0,4], k = 5))
print(s.maxNumber(nums1 = [3,9], nums2 = [8,9], k = 3))

输出：

[9, 8, 6, 5, 3]
[6, 7, 6, 0, 4]
[9, 8, 9]

注：max(迭代推导式) --> max(i for i in [3,6,4,5] if i%2)