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

สมมติว่ามีอาร์เรย์ nums และค่า k เราต้องหาจำนวนซับอาร์เรย์ที่เป็น "nice" โดยซับอาร์เรย์จะเป็น nice ถ้ามีจำนวนเลขคี่อยู่ในซับอาร์เรย์นั้นเท่ากับ k ตรงๆ

ตัวอย่าง: nums = [1,1,2,1,1], k = 3 ผลลัพธ์คือ 2 เพราะมีซับอาร์เรย์ 2 ตัวคือ [1,1,2,1] และ [1,2,1,1]

วิธีแก้ปัญหา

1. odd_i := รายการใหม่
2. วน i จาก 0 ถึง ขนาดของ nums - 1:
   • ถ้า nums[i] % 2 == 1 ให้เพิ่ม i เข้า odd_i
3. start := 0, end := k - 1
4. i := 0
5. count := 0
6. วนลูป while end < len(odd_i):
   • ถ้า end == len(odd_i) - 1: j := len(nums) - 1
   • มิฉะนั้น: 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
7. คืนค่า count

ตัวอย่างโค้ด

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,1,2,1,1], 3

เอาต์พุต

2