資料結構
網路
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 次瀏覽
廣告