Отдельный подмассив с не более k нечетными элементами - PullRequest
Новая
       5

Отдельный подмассив с не более k нечетными элементами

0 голосов
/ 05 февраля 2020

Я знаю, что эта проблема похожа на подсчет количества подмассивов с k разными целыми числами. Более того, два подмассива различны, если они имеют хотя бы один другой элемент. Например, если input равен [3,2,3,4], тогда output будет содержать [3], [2], [4], [3,2], [2,3], [3,4], [2 , 3,4]. поэтому я решил расширить это, чтобы принять во внимание тот факт, что элемент может быть нечетным. Однако при выполнении и самоанализе я обнаружил, что результат всегда был 0 для всех тестовых случаев. Это потому, что переменные, от которых зависит результат, всегда остаются то же самое после каждой итерации. Скажем, на итерации 1 два указателя равны 1 и 1 Затем на итерации 2 два указателя равны 2 и 2 и т. Д. Я перечислил свой код. Может кто-нибудь сказать мне, что не так с моим подходом здесь. 

import collections
class Window:
    def __init__(self):
        self.count=collections.Counter()
        self.odd_elem=0
    def add(self,x):
        if x%2!=0:
            self.count[x]+=1
            #Increase the number of times odd element appears by 1
        if self.count[x]==1:
            self.odd_elem+=1
            #Increase the total number of odd eleemnts
    def remove(self,x):
        if x%2==0:
            self.count[x]-=1
        if self.count[x]==0:
            self.odd_elem-=1
def subarraywithkodd(A,k):
    window1=Window()
    window2=Window()
    ans=left1=left2=0
    for right,x in enumerate(A):
        window1.add(x)
        window2.add(x)
        while window1.odd_elem>k:
            window1.remove(A[left1])
            left1+=1
        while window2.odd_elem>=k:
            window2.remove(A[left2])
            left2+=1
        ans+=left2-left1
    return ans
...