Chương trình đếm số mảng con đẹp trong Python

Giả sử chúng ta có một mảng gọi là nums và một giá trị khác k. Chúng ta phải tìm số mảng con đẹp. Một mảng con được cho là mảng con đẹp nếu có k số lẻ trên đó.

Vì vậy, nếu đầu vào giống như nums =[1,1,2,1,1], k =3, thì đầu ra sẽ là 2 vì có hai mảng con [1,1,2,1] và [1,2 , 1,1].

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

• Od_i:=một danh sách mới

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

  • nếu nums [i] mod 2 giống với 1 thì

    • chèn tôi vào cuối lẻ_i

• start:=0, end:=k - 1

• i:=0

• đếm:=0

• trong khi end

  • nếu end giống với kích thước của lẻ_i - 1, thì

    • j:=kích thước của nums - 1

  • nếu không,

    • j:=retail_i [end + 1] - 1

  • count:=count + (retail_i [start] - i + 1) * (j - retail_i [end] + 1)

  • i:=retail_i [start] + 1

  • start:=start + 1

  • end:=end + 1

• số lần trả lại

Ví dụ

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

def solve(nums, k):
   odd_i = []
   for i in range(len(nums)):
      if nums[i] % 2 == 1:
         odd_i.append(i)
   start = 0
   end = k - 1
   i = 0
   count = 0
   while end < len(odd_i):
      if end == len(odd_i) - 1:
         j = len(nums) - 1
      else:
         j = odd_i[end + 1] - 1
      count = count + (odd_i[start] - i + 1) * (j - odd_i[end] + 1)
      i = odd_i[start] + 1
      start = start + 1
      end = end + 1
   return count

nums = [1,1,2,1,1]
k = 3
print(solve(nums, k))

Đầu vào

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

Đầu ra

2