Python에서 좋은 하위 배열의 수를 계산하는 프로그램

<시간/>

nums라는 배열과 다른 값 k가 있다고 가정합니다. 우리는 좋은 하위 배열의 수를 찾아야 합니다. k 개의 홀수가 있는 하위 배열은 좋은 하위 배열이라고 합니다.

따라서 입력이 nums =[1,1,2,1,1], k =3과 같으면 두 개의 하위 배열 [1,1,2,1]과 [1,2]가 있기 때문에 출력은 2가 됩니다. ,1,1].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

odd_i :=새 목록
범위 0에서 숫자 - 1까지의 i에 대해 수행
- nums[i] mod 2가 1과 같으면
  - odd_i의 끝에 i 삽입
시작 :=0, 종료 :=k - 1
나는 :=0
개수 :=0
동안 <홀수_i의 크기, 수행
- 끝이 odd_i - 1의 크기와 같으면
  - j :=숫자 크기 - 1
- 그렇지 않으면
  - j :=홀수_i[end + 1] - 1
- 개수 :=개수 +(홀수_i[시작] - i + 1) *(j - 홀수_i[끝] + 1)
- 나는 :=홀수_i[시작] + 1
- 시작 :=시작 + 1
- 끝 :=끝 + 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]