MyCodeSchool

Pasul 1 din 5

Java

Pasul 1 din 5 · Ce rezolvi

  • Java
  • Mediu
  • 15 minute

Exerciții cu colecții în Java, rezolvate

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.

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.

Pereche.java
void main() {    int[] v = {3, 8, 5, 2};    int tinta = 10;    Map<Integer, Integer> vazut =            new HashMap<>();    for (int i = 0; i < v.length; i++) {        int rest = tinta - v[i];        if (vazut.containsKey(rest)) {            IO.println(vazut.get(rest)                    + " și " + i);            return;        }        vazut.put(v[i], i);    }}

Variabile

Ce apare pe ecran


      

  1. Linia 4. Tabloul și ținta sunt gata. Map-ul vazut va lega fiecare număr de poziția lui. La început e gol.
  2. Linia 7. Pentru i = 0, numărul e 3. Ca să ajungi la 10 îți trebuie 7.
  3. Linia 8. 7 nu e cheie în map: condiția e falsă, se sare peste bloc.
  4. Linia 13. Notezi că 3 e pe poziția 0.
  5. Linia 7. Pentru i = 1, numărul e 8, iar restul e 2.
  6. Linia 13. 2 nu a apărut încă (condiția de la linia 8 e falsă). Notezi 8 pe poziția 1.
  7. Linia 7. Pentru i = 2, numărul e 5, iar restul e tot 5.
  8. 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.
  9. Linia 7. Pentru i = 3, numărul e 2, iar restul e 8.
  10. Linia 8. 8 e cheie în map: condiția e adevărată.
  11. Linia 9. vazut.get(8) dă poziția 1. Se afișează „1 și 3”.
  12. 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.

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.

Duplicate.java
List<Integer> faraDubluri(        List<Integer> lista) {    Set<Integer> vazut = new HashSet<>();    List<Integer> rez = new ArrayList<>();    for (int x : lista) {        if (vazut.add(x)) {            rez.add(x);        }    }    return rez;}void main() {    IO.println(faraDubluri(            List.of(4, 1, 4, 7, 1, 9)));}

Ce apare pe ecran

[4, 1, 7, 9]

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.

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
boolean echilibrat(String s) {    Deque<Character> st =            new ArrayDeque<>();    for (char c : s.toCharArray()) {        if (c == '(' || c == '[') {            st.push(c);        } else {            if (st.isEmpty()) {                return false;            }            char d = st.pop();            if (c == ')' && d != '('                    || c == ']' && d != '[') {                return false;            }        }    }    return st.isEmpty();}void main() {    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.

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.

Exemplu

sare, rase, lac, cal, ares
→ [lac, cal] și [sare, rase, ares]

Indiciu: anagramele au aceleași litere sortate. „sare” și „rase” devin amândouă „aers”: aceea e cheia.

Anagrame.java
Map<String, List<String>> grupeaza(        List<String> cuvinte) {    Map<String, List<String>> g =            new TreeMap<>();    for (String c : cuvinte) {        char[] lit = c.toCharArray();        Arrays.sort(lit);        String cheie = new String(lit);        g.computeIfAbsent(cheie,                k -> new ArrayList<>())         .add(c);    }    return g;}void main() {    IO.println(grupeaza(List.of("sare",            "rase", "lac", "cal", "ares")));}

Ce apare pe ecran

{acl=[lac, cal], aers=[sare, rase, ares]}

E tiparul de grupare din lecția despre Map: computeIfAbsent creează lista la prima întâlnire a cheii. TreeMap face afișarea previzibilă.

Cele mai mari k valori

Dintr-o listă de punctaje, întoarce cele mai mari k, în ordine descrescătoare, fără să sortezi toată lista.

Exemplu

[5, 1, 9, 3, 7, 2], k = 3 → [9, 7, 5]

Indiciu: ține o PriorityQueue cu cel mult k elemente. Când are prea multe, scoate-l pe cel mai mic.

TopK.java
List<Integer> celeMaiMari(        List<Integer> v, int k) {    Queue<Integer> pq =            new PriorityQueue<>();    for (int x : v) {        pq.offer(x);        if (pq.size() > k) {            pq.poll();        }    }    List<Integer> rez =            new ArrayList<>(pq);    rez.sort(Comparator.reverseOrder());    return rez;}void main() {    IO.println(celeMaiMari(            List.of(5, 1, 9, 3, 7, 2), 3));}

Ce apare pe ecran

[9, 7, 5]

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
void main() {    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
void main() {    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ă.

5 din 5 · Prezice ieșirea

Ce afișează programul?

Doi.java
void main() {    Queue<Integer> pq =            new PriorityQueue<>();    for (int x : List.of(6, 2, 8, 4)) {        pq.offer(x);        if (pq.size() > 2) {            pq.poll();        }    }    IO.println(pq.poll());}

Răspuns: 6.

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

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.

Continuă cu