โปรแกรมนับจำนวนอาร์เรย์ย่อยที่ดีใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องหาจำนวนอาร์เรย์ย่อยที่ดี กล่าวกันว่า subarray เป็น subarray ที่ดีถ้ามี k เลขคี่

ดังนั้น หากอินพุตเท่ากับ nums =[1,1,2,1,1], k =3 เอาต์พุตจะเป็น 2 เนื่องจากมีอาร์เรย์ย่อยสองชุด [1,1,2,1] และ [1,2 ,1,1].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• odd_i :=รายการใหม่

• สำหรับฉันในช่วง 0 ถึงขนาดของ nums - 1 ทำ

  • ถ้า nums[i] mod 2 เหมือนกับ 1 แล้ว

    • ใส่ i ต่อท้าย odd_i

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

• ผม :=0

• นับ :=0

• ในขณะที่สิ้นสุด <ขนาดของ odd_i ทำ

  • ถ้าท้ายเท่ากับขนาด odd_i - 1 แล้ว

    • j :=ขนาดของ nums - 1

  • มิฉะนั้น

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

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

  • ผม :=odd_i[start] + 1

  • start :=start + 1

  • end :=end + 1

• จำนวนคืน

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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

อินพุต

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

ผลลัพธ์

2