Python程式：查詢最小和子序列（至少選擇連續三個元素中的一個）

Python 伺服器端程式設計程式設計

假設我們有一個名為nums的數字列表，我們需要從給定列表中找到一個最小和子序列，條件是必須至少選擇所有連續三個數字組中的一個數字。如果給定列表的長度小於3，則仍然應該選擇一個數字。

例如，如果輸入為nums = [2, 3, 4, 5, 6, 7]，則輸出為7，因為我們可以選擇2和5。

為了解決這個問題，我們將遵循以下步驟：

n := nums的長度
如果n等於0，則
- 返回0
如果n等於1，則
- 返回nums[0]
如果n等於2，則
- 返回nums[0]和nums[1]中的最小值
table := 一個長度為n的列表，並用0填充
table[0] := nums[0]
table[1] := nums[1]
table[2] := nums[2]
對於從3到n的i，執行：
- table[i] := nums[i] + table[i - 3]，table[i - 2]和table[i - 1]中的最小值
res := table[n - 1]，table[n - 2]和table[n - 3]中的最小值
返回res

讓我們看看下面的實現來更好地理解。

示例程式碼

線上演示

class Solution:
   def solve(self, nums):
      n = len(nums)
      if n == 0:
         return 0
      if n == 1:
         return nums[0]
      if n == 2:
         return min(nums[0], nums[1])
      table = [0] * n

      table[0] = nums[0]
      table[1] = nums[1]
      table[2] = nums[2]

      for i in range(3, n):
         table[i] = nums[i] + min(table[i - 3], table[i - 2], table[i - 1])

         res = min(table[n - 1], table[n - 2], table[n - 3])
      return res

ob = Solution()
nums = [2, 3, 4, 5, 6, 7]
print(ob.solve(nums))

輸入

[2, 3, 4, 5, 6, 7]

輸出

Arnab Chakraborty

更新於：2020年11月25日

807 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習