Cinci probleme care apar des la teme și la interviuri. Toate devin scurte când alegi colecția potrivită. Prima, rezolvată pas cu pas, caută în tabloul {3, 8, 5, 2} două numere care dau împreună suma 10:
Pereche.java, în terminal
1 și 3
Răspunsul sunt pozițiile: 8 e pe poziția 1, 2 e pe poziția 3. Pentru fiecare problemă ai enunțul, un exemplu și un indiciu. Încearcă singur înainte să citești soluția.
Te ajută să fi parcurs lecțiile despre List, Set și Queue și despre Map. Soluțiile folosesc Java 25, cu metode și void main() direct în fișier.
să înlocuiești o căutare repetată cu un HashMap
să recunoști duplicatele cu valoarea întoarsă de Set.add
să folosești o stivă pentru perechi care se închid
să grupezi cu un map de liste și să păstrezi doar cele mai mari k valori
Pasul 2 din 5
Perechea cu suma dată, pas cu pas
Varianta naivă ia fiecare pereche cu două bucle. Ideea mai bună: pentru fiecare număr, întrebi dacă ai văzut deja „restul” până la 10. Un map ține minte fiecare număr văzut și poziția lui.
Linia 4. Tabloul și ținta sunt gata. Map-ul vazut va lega fiecare număr de poziția lui. La început e gol.
Linia 7. Pentru i = 0, numărul e 3. Ca să ajungi la 10 îți trebuie 7.
Linia 8. 7 nu e cheie în map: condiția e falsă, se sare peste bloc.
Linia 13. Notezi că 3 e pe poziția 0.
Linia 7. Pentru i = 1, numărul e 8, iar restul e 2.
Linia 13. 2 nu a apărut încă (condiția de la linia 8 e falsă). Notezi 8 pe poziția 1.
Linia 7. Pentru i = 2, numărul e 5, iar restul e tot 5.
Linia 13. 5 nu e încă în map, pentru că verificarea se face înainte de adăugare. Așa un număr nu face pereche cu el însuși. Notezi 5 pe poziția 2.
Linia 7. Pentru i = 3, numărul e 2, iar restul e 8.
Linia 8. 8 e cheie în map: condiția e adevărată.
Linia 9.vazut.get(8) dă poziția 1. Se afișează „1 și 3”.
Linia 11.return oprește main: perechea a fost găsită, nu mai e nevoie de restul buclei. O singură trecere prin tablou a fost suficientă.
Prezice ieșirea
Același program, cu tabloul {5, 5} și o linie IO.println("Nicio pereche") după buclă. Ce afișează?
Răspuns: 0 și 1.
La i = 0, restul 5 nu e încă în map, deci primul 5 e doar notat. La i = 1, restul 5 există, pe poziția 0. Sunt două elemente diferite cu aceeași valoare, deci perechea e corectă.
Pasul 3 din 5
Patru probleme de rezolvat
Fiecare card are enunțul, un exemplu, un indiciu și o soluție rulată. Scrie-ți varianta, apoi compar-o cu soluția.
1
Elimină duplicatele, păstrând ordinea
Primești o listă de numere. Întoarce o listă nouă în care fiecare număr apare o singură dată, în ordinea primei apariții.
Exemplu
[4, 1, 4, 7, 1, 9] → [4, 1, 7, 9]
Indiciu:Set.add întoarce true doar dacă valoarea nu era deja în mulțime.
Mulțimea răspunde rapid la „am mai văzut?”, iar lista păstrează ordinea. Varianta scurtă, new ArrayList<>(new LinkedHashSet<>(lista)), dă același rezultat.
2
Paranteze echilibrate
Un text conține doar ( ) [ ]. Spune dacă fiecare paranteză se închide cu perechea ei, în ordinea corectă.
Exemplu
([()]) → true
([)] → false
(( → false
Indiciu: ultima paranteză deschisă e prima care trebuie închisă. Asta e regula unei stive.
Paranteze.java
booleanechilibrat(String s) { Deque<Character> st =new ArrayDeque<>();for (char c : s.toCharArray()) {if (c == '(' || c == '[') { st.push(c); } else {if (st.isEmpty()) {returnfalse; }char d = st.pop();if (c == ')' && d != '(' || c == ']' && d != '[') {returnfalse; } } }return st.isEmpty();}voidmain() { IO.println(echilibrat("([()])")); IO.println(echilibrat("([)]")); IO.println(echilibrat("(("));}
Ce apare pe ecran
true
false
false
Trei moduri de a greși: o închidere fără deschidere (stiva e goală), o pereche nepotrivită și deschideri rămase la final. Ultimul return le prinde pe cele rămase.
3
Grupează anagramele
Două cuvinte sunt anagrame dacă au aceleași litere, în altă ordine. Pune cuvintele care sunt anagrame unele ale altora în același grup.
Coada scoate mereu minimul, așa că în ea rămân doar cele mai mari k. La final le copiezi într-o listă și o sortezi descrescător, cu Comparator.reverseOrder(): o sortare de doar k elemente.
Pasul 4 din 5
Verifică-te
Cinci întrebări despre ideile din soluții. După fiecare răspuns vezi imediat de ce e așa.
1 din 5 · Prezice ieșirea
Ce afișează programul?
Adauga.java
voidmain() { Set<Integer> vazut = new HashSet<>(); IO.println(vazut.add(3)); IO.println(vazut.add(3));}
Răspuns: true, apoi false.
Primul add pune 3 și răspunde true. Al doilea găsește valoarea deja acolo: nu schimbă nimic și răspunde false, fără excepție. Pe asta se bazează problema 1.
2 din 5 · Alege varianta
Pentru perechea cu suma dată, de ce e mai rapid map-ul decât două bucle una în alta?
Răspuns: căutarea în HashMap e directă.
Cu două bucle, pentru fiecare număr le verifici pe toate celelalte. HashMap găsește o cheie după hashCode, într-un timp care nu crește cu mărimea map-ului. Prețul e memoria în plus.
3 din 5 · Prezice ieșirea
Ce afișează programul?
Invers.java
voidmain() { Deque<Character> st =new ArrayDeque<>();for (char c : "abc".toCharArray()) { st.push(c); } String r = "";while (!st.isEmpty()) { r += st.pop(); } IO.println(r);}
Răspuns: cba.
Într-o stivă, ultimul pus iese primul. „c” a fost pus ultimul, deci e scos primul. O stivă inversează ordinea.
4 din 5 · Alege varianta
Ce cheie are „ares” în soluția cu anagrame?
Răspuns: "aers".
Arrays.sort aranjează literele alfabetic: a, e, r, s. Toate anagramele lui „sare” ajung la aceeași cheie, deci în aceeași listă.
Coada păstrează cele mai mari 2 valori: 6 și 8. Minimul lor, 6, e cel scos de poll. E chiar al doilea cel mai mare număr din listă.
Pasul 5 din 5
Ce ai exersat
„Am mai văzut valoarea asta?” se rezolvă cu HashSet sau HashMap, nu cu o a doua buclă.
Ce se deschide ultimul se închide primul: e o problemă de stivă, cu ArrayDeque.
Pentru grupări alegi o cheie comună și un Map de liste.
O PriorityQueue limitată la k elemente păstrează cele mai mari k valori.
Provocare pentru acasă
Scrie o metodă care primește un text și întoarce primul caracter care apare o singură dată. Pentru „ananas” răspunsul e „s”. Indiciu: un LinkedHashMap de frecvențe, apoi o parcurgere cu entrySet.