Python程式檢查能否透過插入運算子得到24

假設我們有一個包含四個數字的列表，每個數字都在 1 到 9 的範圍內，並且按照固定的順序排列。現在，如果我們在這些數字之間放置運算子 +、-、* 和 /（/ 表示整數除法），並用括號對它們進行分組，我們必須檢查是否可以得到值 24。

因此，如果輸入類似於 nums = [5, 3, 6, 8, 7]，則輸出將為 True，因為 (5 * 3) - 6 + (8 + 7) = 24。

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

• 定義一個函式 recur()。它將接收 arr 作為輸入。
• answer := 一個新的列表
• 對於範圍從 0 到 arr 大小 - 1 的 i，執行以下操作：
  • pre := recur(arr[從索引 0 到 i])
  • suf := recur(arr[從索引 i + 1 到結尾])
  • 對於 pre 中的每個 k，執行以下操作：
    • 對於 suf 中的每個 j，執行以下操作：
      • 在 answer 的末尾插入 (k + j)
      • 在 answer 的末尾插入 (k - j)
      • 在 answer 的末尾插入 (k * j)
      • 如果 j 不為 0，則
        • 在 answer 的末尾插入 (k / j 的商)
• 如果 answer 的大小為 0 且 arr 的大小為 1，則
  • 在 answer 的末尾插入 arr[0]
• 返回 answer
• 在主方法中檢查 24 是否在 recur(nums) 中，如果是，則返回 True，否則返回 False。

讓我們看看以下實現以更好地理解：

示例

線上演示

class Solution:
   def solve(self, nums):
      def recur(arr):
         answer = []
         for i in range(len(arr) - 1):
            pre, suf = recur(arr[: i + 1]), recur(arr[i + 1 :])
            for k in pre:
               for j in suf:
                  answer.append(k + j)
                  answer.append(k - j)
                  answer.append(k * j)
                  if j != 0:
                     answer.append(k // j)
         if len(answer) == 0 and len(arr) == 1:
            answer.append(arr[0])
         return answer
      return 24 in recur(nums)
ob = Solution()
nums = [5, 3, 6, 8, 7]
print(ob.solve(nums))

輸入

[5, 3, 6, 8, 7]

輸出

True

Arnab Chakraborty

更新於: 2020-12-02

79 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習