数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找最具竞争力的子序列
假设我们有一个数组 nums 和另一个值 k，我们需要找到 nums 的大小为 k 的最具竞争力的子序列。这里，子序列 s1 比子序列 s2（大小相同）更具竞争力，如果在 s1 和 s2 不同的第一个位置，子序列 s1 的数字小于 s2 中对应的数字。
因此，如果输入类似于 nums = [4,6,3,7] k = 2，则输出将为 [3,7]，因为在所有大小为 2 的子序列中，{[4,6], [4,3], [4,7], [6,3], [6,7], [3,7]}，[3,7] 是最具竞争力的。
为了解决这个问题，我们将遵循以下步骤：
- attempts := nums 的大小 - k
- stack := 一个新的列表
- 对于 nums 中的每个 num，执行以下操作：
- 当 stack 不为空且 num < stack 的顶部元素且 attempts > 0 时，执行以下操作：
- 从 stack 中弹出元素
- attempts := attempts - 1
- 将 num 推入 stack
- 当 stack 不为空且 num < stack 的顶部元素且 attempts > 0 时，执行以下操作：
- 返回 stack 的前 k 个元素
示例
让我们看看以下实现以获得更好的理解：
def solve(nums, k):
attempts = len(nums) - k
stack = []
for num in nums:
while stack and num < stack[-1] and attempts > 0:
stack.pop()
attempts -= 1
stack.append(num)
return stack[:k]
nums = [4,6,3,7]
k = 2
print(solve(nums, k))输入
[4,6,3,7], 2
输出
[3,7]
更新于: 2021年10月5日
180 次浏览
广告