檢查Python中陣列和能否透過三種操作變為K

假設我們有一個名為nums的數字列表和一個正值K。我們可以在nums上執行以下三種操作中的任何一種：

  • 將一個數字取負；
  • 將數字本身加上其索引（從索引1開始）；
  • 從數字本身減去其索引。

最後，我們必須檢查是否可以透過僅對每個元素執行一次這些操作來轉換給定陣列，使其陣列的和變為k。

因此，如果輸入類似於nums = [1,2,3,7] k = 8，則輸出將為True，因為我們可以從2和3中減去2和3的索引，以使陣列類似於[1, 0, 0, 7]，因此現在的和是8 = k。

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

  • size := 100
  • 定義一個函式is_ok()。這將接收i、total、k、nums和table。
  • n := nums的大小
  • 如果total <= 0，則
    • 返回False
  • 如果i >= n，則
    • 如果total等於k，則
      • 返回True
  • 返回False
  • 如果table[i, total]不等於-1，則
    • 返回table[i, total]
  • table[i, total] := 當(is_ok(i+1, total - 2 * nums[i], k, nums, table) 非零 或 is_ok(i+1, total, k, nums, table) 非零)時為1，否則為0
  • table[i, total] := 當(is_ok(i+1, total -(i+1) , k, nums, table) 或 table[i, total])時為1，否則為0
  • table[i, total] := 當(is_ok(i+1, total + i + 1, k, nums, table) 或 table[i, total])時為1，否則為0
  • 返回table[i, total]
  • 在主方法中執行以下操作：
  • total := nums中所有元素的和
  • table := 一個與size長度相同的陣列，並填充-1
  • 對於i從0到size的範圍，執行
    • table[i] := 一個與size長度相同的陣列，並填充-1
  • 返回is_ok(0, total, k, nums, table)

讓我們看看下面的實現，以便更好地理解：

示例

線上演示

size = 100
def is_ok(i, total, k, nums, table):
   n = len(nums)
   if total <= 0:
      return False
   if i >= n:
      if total == k:
         return True
      return False
   if table[i][total] != -1:
      return table[i][total]
   table[i][total] = is_ok(i+1, total - 2 * nums[i], k, nums, table) or is_ok(i+1, total, k, nums, table)
   table[i][total] = is_ok(i+1, total - (i+1), k, nums, table) or table[i][total] table[i][total] = is_ok(i+1, total + i + 1, k, nums, table) or table[i][total]
   return table[i][total]
def solve(nums, k):
   total = sum(nums)
   table = [-1]*size
   for i in range(size):
      table[i] = [-1]*size
   return is_ok(0, total, k, nums, table)
nums = [1,2,3,7]
k = 8
print(solve(nums, k))

輸入

[1,2,3,7], 8

輸出

True

更新於：2020-12-30

87 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告