Luo luokka Lista. Määrittele sen sisälle taulukko (array), jossa säilytät listan alkiota, sekä kokonaislukumuuttuja, joka pitää kirjaa listan nykyisestä alkiomäärästä. Toteuta metodit

• add(T element): lisää alkion listan loppuun.

Tietorakenteen kokoa ei tarvitse tässä vaiheessa kasvattaa, eli taulukko voi tulla täyteen. Tutki debuggerin avulla, että alkio on lisätty oikein. Älä toteuta vielä get- tai toString-metodeja; tarkastele listan tilaa nimen omaan debuggerin avulla.

Muokkaa add-metodia siten, että se lisää alkion listan loppuun, ja tarvittaessa luo uuden isomman taulukon (1,5x tai 2x kokoisen) ja kopioi vanhan taulukon alkiot uuteen taulukkoon. Muista huolehtia myös listan koosta asianmukaisesti.

Toteuta myös size()-metodi, joka palauttaa listan nykyisen alkiomäärän.

Käytä get- ja size-metodeja apuna testataksesi, että add-metodi toimii oikein myös kun taulukko on täynnä ja uusi taulukko on luotu.

Toteuta remove(int index)-metodi, joka poistaa listasta alkion halutusta indeksistä. Metodin tulee palauttaa poistettu alkio.

• Poistettua alkiota seuraavat alkiot siirtyvät vasemmalle, jotta taulukkoon ei jää "aukkoja".
• Taulukkoon ei saa jäädä ylimääräisiä sisältöjä poistamisen jälkeen.
• Muista päivittää listan koko asianmukaisesti.

Tarkista debuggerissa ja/tai get- ja size-metodeilla, että poisto on onnistunut oikein.

Jatka Lista-luokkaa toteuttamalla remove(T element)-metodi, joka poistaa ensimmäisen esiintymän annetusta alkiosta.

• Jos alkio löytyy ja poistetaan, palauta true.
• Jos alkiota ei löydy, lista pysyy ennallaan ja palautetaan false.

Vinkki: Voit käyttää jo toteuttamaasi remove(int index)-metodia apuna; älä kopioi siirto-logiikkaa tähän metodiin.

Tee funktio laskeSanat, joka ottaa parametrina vastaan merkkijonon ja tekee seuraavat asiat:

• Tulostaa kaikki uniikit sanat ja sen, kuinka monta kertaa kyseinen sana esiintyy merkkijonossa.
• Tulostaa vielä erikseen yleisimmän sanan ja sen, kuinka monta kertaa se esiintyy merkkijonossa.
• Tulostaa uniikkien sanojen lukumäärän.

Voit testata ohjelmasi toimintaa valmiilla pääohjelmalla, jossa on myös esimerkkituloste.

Tee luokka Varaukset, joka tallentaa varauksia. Yhdelle päivämäärälle voi olla vain yksi varaus ja varauksen tekijän nimi täytyy myös tallentaa.

Päivämääränä voit tässä tehtävässä käyttää merkkijonoa, jonka muoto on YYYY-MM-DD eli vuodet, kuukaudet ja päivät. Voit myös olettaa, että päivämäärät ovat aina oikeassa muodossa.

Toteuta luokkaan seuraavat metodit:

• lisaaVaraus ottaa parametrina päivämäärän ja varaajan nimen merkkijonona ja lisää varauksen tietorakenteeseen. Jos päivämäärälle on jo varaus, uusi varaus ei saa korvata sitä. Metodi palauttaa true, jos uusi varaus lisätään tietorakenteeseen , muuten false.

• poistaVaraus ottaa parametrina päivämäärän ja poistaa sille päivälle sijoittuvan varauksen. Metodi palauttaa true, jos varaus poistetaan tietorakenteesta, muuten false.

• tulostaVaraukset ottaa parametrina alku- ja loppupäivämäärän ja tulostaa kaikki näiden väliin sijoittuvat varaukset varauksen päivämäärän mukaan järjestettynä.

Voit testata luokan toimintaa valmiin pääohjelman avulla.

Toteuta oma yksinkertainen hajautustaulu.

Käytä hajautustaulun päätietorakenteena taulukkoa. Voit käyttää törmäysten käsittelyyn esimerkiksi listaa, eli samaan indeksiin osuvat alkiot laitetaan siinä indeksissä sijaitsevaan listaan alkioista. Alkioita ei saa kadota törmäysten yhteydessä.

Hajautustaulun kapasiteetilla voi olla oletusarvona 10 tai se voi ottaa arvon parametrina muodostajassa. Kapasiteetin ei tarvitse muuttua missään vaiheessa ohjelman suorituksen aikana, eli taulun käyttöastetta ei tarvitse huomioida tai toteuttaa.

Javan hashCode voi palauttaa negatiivisen arvon, joten kannattaa käyttää itseisarvoa negatiivisen indeksin välttämiseksi.

Lisää metodi hae, joka hakee alkion hajautustaulusta sen avaimen perusteella. Lisää myös metodit lisaa ja poista alkioiden lisäämistä ja poistamista varten.

Saat tehtävässä kaksi duplikaatteja sisältävää listaa luvuista.

Muodosta näistä luvuista seuraavat joukot:

• Yhdiste: Sisältää kaikki luvut, jotka kuuluvat joko ensimmäiseen joukkoon, toiseen joukkoon tai molempiin.

• Leikkaus: Sisältää vain ne luvut, jotka löytyvät molemmista joukoista samanaikaisesti.

• Erotus: Sisältää ne luvut, jotka kuuluvat ensimmäiseen joukkoon, mutta eivät kuulu toiseen joukkoon.

• Symmetrinen erotus: Sisältää ne luvut, jotka kuuluvat vain jompaankumpaan joukkoon, mutta eivät molempiin.

Joukot eivät saa sisältää duplikaatteja.

Joukkojen muodostaminen onnistuu Set-rajapinnan määrittelemien metodien avulla niin, että tietorakenteita ei tarvitse selata läpi silmukoiden avulla.

Valmis pääohjelma sisältää esimerkit, mitä näiden joukkojen pitäisi sisältää.

Tee luokka Tehtavalista, joka toimii todo-listana. Tehtävät voivat olla yksinkertaisia merkkijonoja.

Tehtävälista pitää kirjaa sekä tekemättömistä että tehdyistä tehtävistä. Tehtävät suoritetaan siinä järjestyksessä, missä ne ovat tehtävälistaan lisätty. Poikkeustapauksia varten tulee olla mahdollista lisätä kiireellisiä tehtäviä heti tehtävälistan alkuun.

Ohjelmassa pitää olla myös mahdollisuus kumota tehtävän merkitseminen suoritetuksi siltä varalta, että tehtävän merkitsee vahingossa tehdyksi liian aikaisin. Kumoaminen palauttaa suoritetuksi merkityn tehtävän takaisin tehtävälistan alkuun.

Lisää luokkaan seuraavat metodit:

• lisaaTehtava, joka lisää tehtävän tehtävälistaan. Uusi tehtävä menee tehtävälistan viimeiseksi.

• lisaaTarkeaTehtava, joka lisää kiireellisen tehtävän tehtävälistaan. Kiireellinen tehtävä menee aina tehtävälistan ensimmäiseksi.

• merkitseTehdyksi, joka merkitsee seuraavana tehtävälistalla olevan tehtävän suoritetuksi.

• kumoaTehty, joka palauttaa viimeksi tehdyn tehtävän suoritettujen tehtävienlistalta takaisin tehtävälistan alkuun.

• tulosta, joka tulostaa tekemättömät ja tehdyt tehtävät omina listoinaan. Tulostusmuoto ei ole hirveän tärkeä, kunhan tulosteesta näkee selvästi eri listat.

Voit testata luokan toimintaa valmiin pääohjelman avulla.

Kirjoita aliohjelma, joka tarkistaa merkkijonon sisältämien sulkujen oikeellisuuden. Aliohjelman tulee tunnistaa, sulkeutuvatko kaikki sulut oikeassa järjestyksessä ja onko jokaisella alkavalla sululla vastaava lopettava pari.

Tuetut sulkutyypit ovat kaarisulut ( ), hakasulut [ ] ja aaltosulut { }.

Toimintalogiikka ja säännöt:

• Sisäkkäisyys: Sulut voivat olla sisäkkäin (esim. ([])), mutta ne eivät saa mennä ristiin. Esimerkiksi ([)] on virheellinen, koska sulut menevät ristiin.
• Järjestys: Sulun on aina alettava ennen kuin se sulkeutuu.
• Muut merkit kuten kirjaimet tai numerot tulee jättää huomiotta.
• Tyhjä merkkijono katsotaan oikeelliseksi, ja siinä on 0 paria.

Paluuarvo:

• Jos sulutus on kunnossa, palauta löydettyjen sulkuparien lukumäärä (kokonaisluku).
• Jos sulutus on virheellinen (yksikin pari puuttuu tai järjestys on väärä), palauta luku -1.

Esimerkit:

Aliohjelma tulee toteuttaa niin, että jos sulkuihin lisättäisin uusia sulkutyyppejä, niin varsinaisessa logiikassa ei tarvitsisi tehdä muutoksia. Esimerkiksi merkkijonon a<(b)>c käsittelemiseen tulisi vain lisätä tuki kulmasuluille < >, mutta muuten logiikka pysyisi samana (lue: ei ylimääräisiä if-lauseita).

Laske lukujen 1 + 2 + ... + n summa ilman rekursiota käyttäen omaa pinoa.

Lähtökohtana on rekursiivinen määritelmä:

int summa(int n) {
    if (n == 0) return 0;
    return n + summa(n - 1);
}

Kirjoita metodi summaIteratiivisesti(int n), joka palauttaa saman tuloksen. Mallinna rekursiota pinon avulla: talleta pinoon luvut, jotka "odottavat" paluuvaiheessa. Käytä pinon toteutukseen ArrayDeque-toteutusta. Et tarvitse tässä vielä Kehys-olion kaltaista rakennetta.

Toteuta kokonaislukuja sisältävän binääripuun solmujen summan laskenta ilman rekursiota käyttäen omaa pinoa. Käytä oheista Solmu-luokkaa.

public class Solmu {
    int arvo;
    Solmu vasen;
    Solmu oikea;

    Solmu(int arvo) {
        this.arvo = arvo;
    }
}

Lähtökohtana on rekursiivinen määritelmä:

int summa(Solmu juuri) {
    if (juuri == null) return 0;
    return juuri.arvo + summa(juuri.vasen) + summa(juuri.oikea);
}

Mallinna rekursiota pinon avulla: jokainen pinon alkio vastaa rekursiivisen kutsun tilaa. Tätä varten tarvitset Kehys-luokan (esim. Solmu ja kayty), jolla ylläpidetään tilatietoa. Pinoa ei tarvitse toteuttaa, vaan voit käyttää ArrayDeque-toteutusta, kuten materiaalissakin.

Esimerkkipääohjelma on mukana TIM-tehtävässä.