Chương trình tìm kích thước của danh sách con nhỏ nhất có tổng ít nhất mục tiêu trong Python

Giả sử chúng ta có một danh sách các số được gọi là num và một đầu vào khác được gọi là target, chúng ta phải tìm kích thước của danh sách con ngắn nhất sao cho giá trị tổng của nó giống với target hoặc lớn hơn. Nếu không có danh sách con nào như vậy thì trả về -1.

Vì vậy, nếu đầu vào là nums =[2, 11, -4, 17, 4] target =19, thì đầu ra sẽ là 2, vì chúng ta có thể chọn [17, 4] để nhận tổng ít nhất là 19.

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

• ps:=danh sách chỉ có một phần tử 0

• đối với mỗi số trong số, thực hiện

  • insert (phần tử cuối cùng của ps + num) sau ps

  • nếu num> =target, thì

    • trả lại 1

• min_size:=inf

• q:=[0]

• j:=0

• đối với tôi trong phạm vi từ 1 đến kích thước của ps, thực hiện

  • j:=tối thiểu của j, kích thước của q - 1

    • while j =target, do

      • min_size:=tối thiểu của min_size và (i - q [j])

      • j:=j + 1

    • trong khi q và ps [i] <=ps [phần tử cuối cùng của q], thực hiện

      • xóa phần tử cuối cùng khỏi q

    • chèn tôi vào cuối q

• trả về min_size nếu min_size

Ví dụ

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

class Solution:
   def solve(self, nums, target):
      ps = [0]
      for num in nums:
         ps += [ps[-1] + num]
         if num >= target:
            return 1
         min_size = float("inf")
         q = [0]
         j = 0
         for i in range(1, len(ps)):
            j = min(j, len(q) - 1)
            while j < len(q) and ps[i] - ps[q[j]] >= target:
               min_size = min(min_size, i - q[j])
               j += 1
            while q and ps[i] <= ps[q[-1]]:
               q.pop()
            q.append(i)
         return min_size if min_size < float("inf") else -1
ob = Solution()
nums = [2, 11, -4, 17, 4]
target = 19
print(ob.solve(nums, target))

Đầu vào

[2, 11, -4, 17, 4], 19

Đầu ra

2