Kiểm tra xem tổng mảng có thể được tạo thành K bằng ba phép toán trên nó trong Python hay không

Giả sử chúng ta có một danh sách các số được gọi là num và cũng có giá trị dương K. Chúng ta có thể thực hiện bất kỳ thao tác nào trong ba thao tác này trên nums -

• Đặt một số âm,
• Thêm chỉ mục (bắt đầu từ chỉ mục 1) của số vào chính số đó
• Trừ chỉ số của số khỏi chính số đó.

Cuối cùng, chúng ta phải kiểm tra xem mảng đã cho có thể được chuyển đổi khi tổng của mảng trở thành k hay không, bằng cách thực hiện các phép toán này chỉ một lần trên mỗi phần tử.

Vì vậy, nếu đầu vào giống như nums =[1,2,3,7] k =8, thì đầu ra sẽ là True vì chúng ta có thể trừ chỉ số của 2 và 3 từ 2 và 3 để tạo mảng như [1, 0, 0, 7], vì vậy bây giờ tổng là 8 =k.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• kích thước:=100
• Xác định một hàm is_ok (). Điều này sẽ lấy i, tổng, k, số, bảng
• n:=kích thước của nums
• nếu tổng số <=0, thì
  • trả về Sai
• nếu tôi> =n, thì
  • nếu tổng bằng k, thì
    • trả về True
• trả về Sai
• nếu bảng [i, total] không phải là -1, thì
  • bảng trả về [i, tổng số]
• table [i, total]:=1 khi (is_ok (i + 1, total - 2 * nums [i], k, nums, table) khác 0 hoặc is_ok (i + 1, total, k, nums, table) khác 0), ngược lại là 0
• table [i, total]:=1 khi (is_ok (i + 1, total - (i + 1), k, nums, table) hoặc table [i, total]), nếu không thì 0
• table [i, total]:=1 khi (is_ok (i + 1, total + i + 1, k, nums, table) hoặc table [i, total]), nếu không thì 0
• bảng trả về [i, tổng số]
• Từ phương thức chính, hãy làm như sau -
• total:=tổng của tất cả các phần tử tính bằng nums
• table:=một mảng có độ dài bằng với kích thước và điền bằng -1
• đối với tôi trong phạm vi từ 0 đến kích thước, hãy thực hiện
  • table [i]:=một mảng có độ dài bằng với kích thước và điền bằng -1
• return is_ok (0, tổng, k, nums, bảng)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

[1,2,3,7], 8

Đầu ra

True