siemaneczko
zadanie wygląda tak:
dostaje się dwie listy A i B
A reprezentuje wielkość danej rybki
B kierunek poruszania się rybki (0 - w górę strumienia, 1 - w dół)
jeżeli rybki się ze soba spotkają tzn. jedna wpłynie na drugą to większa pożera mniejszą.
ryby poruszaja się z ta samą predkością czyli jak jedna porusza się w dół strumienia i ta za nią też , to te rybki się nie spotkają.
program ma zwrócić ile rybek zostanie przy zyciu:
np dla:
A[0] = 4 B[0] = 0
A[1] = 3 B[1] = 1
A[2] = 2 B[2] = 0
A[3] = 1 B[3] = 0
A[4] = 5 B[4] = 0
program ma zwrócić 2 bo przeżyje rybka pierwsza i ostatnia
pomocy!
złożność O(N) N = len(A)
Co się dzieje gdy spotkają się rybki tej samej wielkości?
Jakie jest położenie początkowe rybek?
Początkowe położenie rybek jest takie same jak indeksy:
A[0] = 4 B[0] = 0 # Ta rybka płynie do góry więc jest bezpieczna
A[1] = 3 B[1] = 1 # Ta płynie w dół więc napotka te poniżej płynące do góry
A[2] = 2 B[2] = 0 # Zostanie zjedzona przez A[1]
A[3] = 1 B[3] = 0 # Zostanie zjedzona przez A[1]
A[4] = 5 B[4] = 0 # Jako że ta rybka jest większa zje rybkę A[1]
Każda rybka ma inną wielkość
mi chodzi o to aby rozwiązanie zapiać w pythonie tak aby działało dla dowolnych list A i B :)
Złożoności O(n) jesteś pewien?
bogdans napisał(a):
Złożoności O(n) jesteś pewien?
Intuicja mówi mi, że się da. :)
dostałem takie zadanko na portalu któremu ufam .... ale z tą złożonością to raczej z przymrueniem oka
To może poszukać największych ryb płynących w górę i w dół, i sprawdzić ile zjedzą tych co płyną w przeciwnym kierunku? Uwzględnij fakt że jedna z nich będzie większa, i zje tą drugą uniemożliwiając jej dalszą konsumpcję.
edit: no chyba że ta co płynie w górę będzie wyżej niż ta co płynie w dół, wtedy trzeba będzie powtórzyć wszystko dla rybek między nimi.
ale jak to zapisać?
O(n^2) Cię urządza?
dawaj jak masz :)
while True:
found = False
for i in range(len(B) - 1):
if B[i] == 1 and B[i + 1] == 0:
found = True
if A[i] > A[i + 1]:
to_delete = i + 1
else:
to_delete = i
A.pop(to_delete)
B.pop(to_delete)
break
if not found:
break
print(len(A))
100% poprawności
50 % szybkości
w sumie 75%
dzięki
jakby kto miał coś szybszego to niech mu klawiatura lekką bęźdie ;)
Dwie wersje czytelna i mniej czytelna
def f(a, b):
n = len(a)
max_fish = 0
r = 0
for i in xrange(n):
if b[i] == 0:
if a[i] > max_fish:
r += 1
else:
max_fish = max(max_fish, a[i])
max_fish = 0
for i in xrange(n - 1, -1, -1):
if b[i] == 1:
if a[i] > max_fish:
r += 1
else:
max_fish = max(max_fish, a[i])
return r
def process(x, y):
if y[1] == 0:
return (x[0] + (y[0] > x[1]), x[1])
else:
return (x[0], max(x[1], y[0]))
def f2(a, b):
r = 0
r += reduce(process, zip(a, b), (0, 0))[0]
r += reduce(process, zip(a, map(lambda x: x ^ 1, b))[::-1], (0, 0))[0]
return r
co to reduce??
python nie rozumi
wohnioh napisał(a):
co to reduce??
python nie rozumi
W Pythonie 3 jest w module functools
:
https://docs.python.org/3/library/functools.html#functools.reduce
rozwiązenie które napisałem po głębszym zamyśle i przeszło testy na 100%:
def solution(A,B):
if len(A)>0:
a = [A[0]]
b = [B[0]]
for i in range(1,len(A)):
l2 = len(b)
if (b[l2-1] == 0 and B[i] == 1 ) or b[l2-1] == B[i]:
a.append(A[i])
b.append(B[i])
elif b[l2-1] == 1 and B[i] == 0:
if a[l2-1] < A[i]:
a[l2-1] = A[i]
b[l2-1] = B[i]
if l2>1:
while a[len(a)-2] < a[len(a)-1] and (b[len(a)-2]==1 and b[len(a)-1] ==0):
l = len(a)
a[l-2] = a[l-1]
b[l-2] = b[l-1]
a.pop(l-1)
b.pop(l-1)
if l == 1:
break
while a[len(a)-2] > a[len(a)-1] and (b[len(a)-2]==1 and b[len(a)-1] ==0):
l = len(a)
a.pop(l-1)
b.pop(l-1)
if l == 1:
break
return len(b)