Leetcode September Day1 ICSP: Chcę się skonsultować. Walczyłem przez 3h z niby prostym problemem z wrześniowego wyzwania Leetcode. Problem jest następujący: Rozważamy system czasu 24h tzn. zamiast godziny 5:54 PM mamy godzinę 17:54. Dostajemy jako argument tablicę 4 złożoną z 4 cyfr. Mamy zwrócić (String) najpóźniejszą możliwą godzinę którą można utworzyć z tych cyfr w formacie: \\d{2}:\\d{2} a jeżeli taka nie istnieje to należy zwrócić pusty String. Czy widzi ktoś jakiś sensowny sposób rozwiązania poza tworzeniem wszystkich 24 permutacji −> odsiewania błędnych −> wybrania największej z nich? Problem rozwiązałem w Javie ale jakoś nie jestem usatysfakcjonowany moim rozwiązaniem.

student: Na pierwsze miejsce weź największą z czterech cyfr ale nie większą niż 2. Jeśli cyfra na pierwszym miejscu jest równa 2: Na drugie miejsce weź największą z pozostałych trzech cyfr ale nie większą niż 3. W przeciwnym przypadku: Na drugie miejsce weź największą z pozostałych trzech cyfr. Na trzecie miejsce weź największą z pozostałych dwóch cyfr ale nie większą niż 5. Na czwarte miejsce weź pozostałą cyfrę.

ICSP: Nie zadziała: [2,0,6,6] Też chciałem to rozwiązać w ten sposób.

jc: przesuń na pierwszą pozycję największą cyfrę nie większą niż 2 jeśli to 2 to na drugim miejscu postaw największą cyfrę nie większą niż 3 posortuj pozostałe 2 lub 3 cyfry.

ICSP: jc również nie zadziała. Ten sam kontrprzykład.

student: No tak, bo tutaj się nie da nie ułożyć poprawnej godziny. Wystarczy jeszcze sprawdzać na każdej próbie wzięcia cyfry czy właśnie coś wzięło czy nie

jc: Faktycznie pisząc nie widziałem innych tekstów Podoba mi się zadanie.

ICSP: [2,0,6,6] −> 06:26 jest jak najbardziej poprawną godziną.

jc: Odpowiedź jest jasna, tylko jak maszyna ma ją znaleźć, bo my po prostu widzimy.

jc: Czy problem nie pojawia się tylko, kiedy mamy dwie cyfry większe od 5?

ICSP: Też mi się tak wydaję. Jeżeli na pierwszym miejscu stoi 1 to problemu nie ma Jeżeli na pierwszym miejscu stoi 2 i dodatkowo w pozostałych cyfrach mamy przynajmniej dwie większe od 5 to pojawia się problem. Przynajmniej tak mi się wydaje ( obserwacje )

student: Musi to być w Javie czy może być C++?

ICSP: Leetcode dopuszcza wiele języków Java, C++, Python i jeszcze inne. Ja piszę w Javie bo najlepiej się w niej czuję.

Dziadek Mróz: 23:59 jest największa, ogranicz się do niej cyfry: [2, 0, 6, 4] Stwórz permutację liczb dwucyfrowych nie większych niż 23 dla godziny [20, 26, 24, 02, 04, 06, 62, 60, 64, 42, 40, 46] → max: 20, usuwamy ze zbioru cyfry 2 i 0 cyfry: [6, 4] Dla minuty nie większe niż 59: [ 64, 46] → max: 46 Maksymalna godzina: 20:46 Jeżeli w permutacjach będzie pusty zbiór liczb to nie ma takiej godziny, np: [2, 4, 5, 6]

Blee: 0) jeżeli wszystkie cyfry większe od 2 − > pusty string 1) jeżeli 2 występuje to na pierwsze miejsce 1.1) jeżeli liczba cyfr większą od 5 jest większa o jeden − > pusty string 1.2) jeżeli liczba cyfr większą od 3 jest większa od 2 − > pusty string 1.3) jeżeli jest cyfra większą od 5 to na ostatnie miejsce 1.4) największa (ale mniejsza od 4) cyfra na drugie miejsce 1.5) największa (ale mniejsza od 6) cyfra na trzecie miejsce 1.6) jeżeli została cyfra − na ostatnie miejsce 2) jeżeli występuje 1 to na pierwsze miejsce (w przeciwnym razie 0) 2.1) jeżeli liczba cyfr większą od 5 jest większa od dwa − > pusty string 2.2) największa cyfra na drugie miejsce 2.3) największa (ale mniejsza od 6) na trzecie miejsce 2.4) ostatnia na ostatnie miejsce

znak: Już na 1.1 można znaleźć kontrprzykład, a w zasadzie, to wystarczy wziąć to samo, co ICSP o 14.54, mianowicie tablica [2, 0, 6, 6]. Spełnia (1), ale nie spełnia (1.1), bo mamy dwie szóstki. Ale 06:26 to prawidłowa godzina. To, co napisał Dziadek wydaje się być najlepszym rozwiązaniem.

ICSP: Jakoś dzisiejszy problem był prostszy. Blee jak wyzej. Dziadek nie zawsze wybranie maksimum będzie dobrym rozwiązaniem. Należy te godziny wpisać do jakiejś listy i sprawdzać kolejno po maksymalnych godzinach. Jeżeli przelecimy przez całą listę permutacji dwuargumentowych (odpowiadających godzinom) i nie znajdziemy dobrej kombinacji minut to wtedy dopiero zwracamy pusty string. Jadnak postaram się twoja wersję zaimplementować.

student: A zależy Ci na szybkości działania czy nie?

wredulus_pospolitus: Uwaga do rozwiązania dziadka: [2,0,6,6] wybierze 20: ... i teraz problem Zaraz siądę i pomyślę jeszcze nad tym

ICSP: student niezbyt rozumiem. Tablica ma ustalony rozmiar, więc złożoność czasowa to O(1). Jeśli chodzi o miejsce to również O(1). Tak czy tak będzie szybko. wredulus wystarczy iterować po powstałej liście zaczynając od elementu największego.

student: Sprawdź czy Ci działa i czy rozumiesz public static void main(String[] args) { String str = ""; ArrayList<Integer> cyfry = new ArrayList<Integer>(); cyfry.add(2); cyfry.add(0); cyfry.add(6); cyfry.add(6); Collections.sort(cyfry); for(int godz=23;godz>=0;godz−−) { for(int min=59;min>=0;min−−) { ArrayList<Integer> tab = new ArrayList<Integer>(); int c1 = (godz/10)%10; // pierwsza cyfra godziny tab.add(c1); int c2 = godz%10; // druga cyfra godziny tab.add(c2); int c3 = (min/10)%10; tab.add(c3); int c4 = min%10; tab.add(c4); Collections.sort(tab); if(cyfry.equals(tab)) { str=c1+""+c2+":"+c3+""+c4; } } } System.out.print(str); }

student: Na odwrót musi być w pętlach... for(int godz=0;godz<=23;godz++) { for(int min=0;min<=59;min++) { . . . } }

Mariusz: Nie jestem pewny czy powyższy algorytm jest optymalny jeśli chodzi o złożoność czasową Ten algorytm wykonuje 1440 iteracji

wredulus_pospolitus: na pewno nie jest optymalny, chociażby dlatego że bez względu na to jakie są dane wejściowe, będzie robił wszystkie 1440 iteracji,

student: Nie jest optymalny, ale za to jest bardzo prosty

znak : Operacja modulo dla c1 oraz c3 całkowicie zbędna, to są wartości int, więc dzielenie przez 10 i tak da liczbę int mniejszą od 10.

ICSP: 1440 iteracji + sortowanie w każdej nich do tego (co prawda tylko 4 elementów ale zawsze) Chodziło mi o jakiś ciekawy pomysł a nie brutalną siłę. Lepiej jest zrobić z tego oddzielną metodę zwracającą typ String. Następnie w tej zagnieżdżonej pętli zamiast przypisywać do zmiennej (za pętlami wyświetlać) po prostu zwrócić zmienną.

fil: probowales uzywac std::next_permutation()? Wydaje sie dobrym pomyslem

fil: Dlaczego twoje rozwiazanie cie nie satysfakcjonuje? Zlozonosc czasowa algorytmu bedzie O(1)

fil: Drugie podejscie jest wytlumaczone tutaj: https://leetcode.com/problems/largest-time-for-given-digits/solution/

ICSP: W Javie nie ma klasy która może wygenerować permutacje dla tablicy/stringa. Trzeba samemu napisać kod który to wykona. Nie jest zadowolony bo wygląda brzydko i jest dość długie. To co zaproponował Dziadek Mróż wygląda dużo lepiej. Masz inny przykład. Poniżej wstawiam dwie wersje rozwiązania innego prostego problemu. https://pastebin.pl/view/54a60198 Obie wykonują się w O(n) ale druga jest zdecydowanie czytelniejsza (czyli moim zdaniem lepsza)

student: Pierwsza jest dużo bardziej czytelniejsza

fil: No tak, tutaj druga jest czytelniejsza, dobrze znany problem z "Single number"

fil: A pokazesz swoj kod w Javie do rozwiazanie pierwszego problemu?

fil: ICSP a podchodziles na leetcode do problemu o nazwie "LRU Cache"?

ICSP: w poniedziałek zrobię refactoring i wrzucę. Aktualna wersja jest zrozumiała głównie dla autora a nie o to chodzi. Nie podchodziłem. Dopiero zaczynam przygodę z leetcode.

fil: Polecam jeszcze Codeforces

fil: I jak?

fil: Przy okazji − rozwiazales juz dzisiejszy problem?

ICSP: może jutro

ICSP: https://pastebin.pl/view/65093640 zgodnie z obietnicą wstawiam wersję bez refactoringu.

ICSP: a tutaj po zmianach: https://pastebin.pl/view/dd4bc2c4

student: No to zrób dla n liczb