[a.....e]

Poprawcie mój algorytm, bo na codility performance wyszedł 0%, ech.

Ma zwracać maksymalną długość ścieżki drzewa, z tym, że w ścieżce nie może się powtórzyć żaden element.
Dla przykładu z rysunku najdłuższą ścieżką będzie 1,7,6,5 lub 1,7,6,5,11. Scieżka po prawej będzie 1,9, bo dalej 9 się powtarza, więc nie mozemy tam iść.

Mój algorytm w komentarzu.
#programowanie #java

[a.....e]

public class DistincMaxPathFinder {

int find(BTree bTree) {
return findMax(bTree, new HashSet<>()) - 1;
}

private

[a.....e]

testy:

class DistincMaxPathFinderTest extends Specification {

def "Find"() {
given:

[Saly]

@aczutuse: na pewno nie musisz robić kopii HashSet, niech każda funkcja odpowiednio dodaje i usuwa element w przekazanym secie

[93michu93]

1,7,6,5 lub 1,7,6,5,11

@aczutuse: no ale jak z 6 do 5 zejdziesz i będziesz chciał wrócić to znów masz 6. Ten przypadek się nie liczy?
Ścieżka ma być najdłuższa pod względem wag, tak?

[a.....e]

@93michu93: nie, bez wracania. Najdłuższa pod względem poziomu drzewa, jeden node waży 1.

[63274682374]

@93michu93: pomylił się

[a.....e]

@93michu93: @63274682374: ta sorry, miało być:

1,7,6,5 lub 1,7,6,11.

[Sachees]

@aczutuse: wydaje mi się że niepotrzebnie dajesz to -1 na początku, bo sobie przejdź po tym przykładzie:
węzły 11 i 5 zwrócą oba 0, więc węzeł 6 zwróci 1
potem w węźle 7 mamy 0 vs 1 więc zwróci 2
i na końcu w korzeniu mamy 3, a ty odejmujesz jeszcze 1 od tego

w sytuacji gdy obecny węzeł już jest w secie, zwracaj -1, a gdy ma obu synów

[a.....e]

@Sachees: możliwe, starałem się to odtworzyć... tylko, że to nie wpływa na peformance, a miałem 0% performancu i 100% corectness, ech

[Sachees]

@aczutuse: performance masz z-----y przez to, że za każdym razem tworzysz nowe sety zamiast korzystać z istniejącego

[a.....e]

@Sachees: no domyslam się, ech... @Saly poradził usuwać, ale nie wiem jak ech

[Sachees]

@aczutuse: W Javie wszystko jest przekazywane przez referencję, więc wystarczy że dasz ten set jako argument i oprócz tego:
1. Przy wejściu do węzła dodajesz obecną liczbę (tak jak tutaj)
2. Przy wyjściu ją usuwasz metodą remove

[a.....e]

@Sachees: @Saly: chyba tak

[a.....e]

@Sachees: w javie argumenty są przekazywane przez wartość zawsze tylko wartośćią tutaj jest referencja

[Saly]

@aczutuse: wygląda ok.

: w javie argumenty są przekazywane przez wartość zawsze tylko wartośćią tutaj jest referencja

@aczutuse: po prostu kopiujesz wskaźnik/referencję do tej samej instancji HashSet, którą utworzyłeś w find.
Jak umiesz w C/C++ to jest tak samo jakby wszystko było przekazywane przez wskaźnik by default (oprócz prymitywów, które są kopiowane jak w C)