Bonusviikko

TMC bonusviikko

Tehtävät ovat bonusta, eli tavoitepistemäärä on 0. Tehtävillä voi joko korvata tekemättä jääneitä tehtäviä, tai sitten hankkia yli 100% tavoitepistemäärästä.

Tehtävien deadline: sunnuntaina 29.10. kello 23:59

Bonusviikolla on aiempien viikkojen aiheisiin liittyviä tehtäviä.

Tehtävä 1

Tehtäväpohjan mukana tulee luokka Node, joka esittää yhteen suuntaan linkitetyn listan solmua.

Toteuta luokkaan Operaatioita seuraavat metodit:

Node reverse(Node root) kääntää listan, jonka juurisolmu annetaan ja palauttaa käännetyn listan juurialkion.
Node cut(Node root, int i) katkaisee linkin listan (i-1):nnen ja i:nnen solmujen väliltä. Metodi palauttaa i:nnen solmun, joka on juuri katkaisussa syntyvälle alkuperäisen listan loppuosalle. Jos i=0, niin metodin on palautettava alkuperäinen lista muuttumattomana. Esimerkki:

  // Rakennetaan lista [6,7,8,9,10]
  Node root = new Node(6,new Node(7, new Node(8, new Node(9, new Node(10)))));
  // Katkaistaan indeksistä 2
  Node loppu_root = Operaatioita.cut(root, 2);
  // Nyt loppu_root on [8,9,10] ja root on [6,7]

Huom! Kummankaan metodin ei tule allokoida uusia solmuja, vaan annetun listan solmut tulee uudelleenkäyttää! Kummassakaan metodissa ei siis tarvitse olla yhtään new Node -kutsua!

Huom! Testit testaavat että pitkänkin listan kääntämiseen menee alle 20ms.

Tehtävä 2

Sinulle on annettu merkkijono, joka muodostuu merkeistä A ja B. Saat poistaa merkkijonosta merkkipareja, joissa on kaksi samaa merkkiä peräkkäin, ja jatkaa tätä niin kauan kuin mahdollista. Pystytkö tyhjentämään merkkijonon poistamalla sen kaikki merkit?

Esimerkiksi jos merkkijono on ABBABB, tyhjentäminen on mahdollista. Voit poistaa ensin ensimmäisen merkkiparin BB, jolloin tuloksena on AABB. Tämän jälkeen voit poistaa merkkiparin AA, jolloin tuloksena on BB, ja lopulta merkkiparin BB, jolloin olet saanut tyhjennettyä merkkijonon.

Vastaavasti merkkijonon ABABAB tyhjentäminen ei ole mahdollista, koska siitä ei pysty poistamaan edes yhtä merkkiparia.

Toteutus

Toteuta seuraava metodi:

bool tyhjennys(String mjono)

Parametri mjono on merkkijono, joka koostuu merkeistä A ja B. Merkkijonon pituus on välillä 1..10⁵.

Metodin tulee palauttaa true, jos merkkijono on mahdollista tyhjentää, ja muuten false.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`tyhjennys("ABBABB")`	`true`
2	`tyhjennys("ABBBBB")`	`false`
3	`tyhjennys("AAAAAA")`	`true`
4	`tyhjennys("ABABAB")`	`false`

Tehtävä 3

Sinulle on annettu taulukko sanoja, ja tehtäväsi on etsiä siitä suurin mahdollinen ryhmä anagrammeja eli sanoja, joissa on jokaista kirjainta yhtä monta.

Esimerkiksi jos sanat ovat {"talo", "katu", "lato"}, suurin ryhmä on {"talo", "lato"} ja siinä on kaksi sanaa.

Toteutus

Toteuta seuraava metodi:

int suurinRyhma(String[] sanat)

Sanojen määrä on 1..10⁵, ja jokaisessa sanassa on 1..10 kirjainta väliltä a..z.

Metodin tulee palauttaa suurimman ryhmän koko.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`suurinRyhma(new String[] {"apina", "banaani", "cembalo"}`	`1`
2	`suurinRyhma(new String[] {"talo", "katu", "lato"}`	`2`
3	`suurinRyhma(new String[] {"ab", "ab", "ba", "ba"}`	`4`
4	`suurinRyhma(new String[] {"iines", "otto", "sieni", "toto"}`	`2`

Tehtävä 4

Sinulla on tiedossa kaikki ravintolassa päivän aikana käyneet henkilöt sekä heidän tulo- ja lähtöaikansa. Tehtäväsi on laskea, montako asiakasta ravintolassa oli enimmillään.

Voit olettaa, että yhtenä ajanhetkenä vain yksi asiakas voi tulla tai lähteä.

Tarkastellaan esimerkiksi seuraavaa tilannetta:

Asiakas A tuli hetkellä 3 ja lähti hetkellä 8.
Asiakas B tuli hetkellä 4 ja lähti hetkellä 6.
Asiakas C tuli hetkellä 5 ja lähti hetkellä 10.
Asiakas D tuli hetkellä 9 ja lähti hetkellä 12.

Nyt ravintolassa oli enimmillään 3 asiakasta (A, B ja C) hetkien 5 ja 6 välissä.

Toteutus

Toteuta seuraava metodi

int ennatys(int[] tulot, int[] lahdot)

Parametri tulot on taulukko, joka sisältää jokaisen asiakkaan tuloajan. Jokainen aika on kokonaisluku välillä 0..10⁹.

Parametri lahdot on taulukko, joka sisältää jokaisen asiakkaan lähtöajan. Jokainen aika on kokonaisluku välillä 0..10⁹.

Taulukot tulot ja lahdot sisältävät yhtä monta lukua, ja asiakkaiden määrä on välillä 1..10⁵. Luonnollisesti asiakas ei koskaan lähde ravintolasta ennen kuin hän on tullut sinne.

Metodin tulee palauttaa suurin asiakkaiden määrä ravintolassa.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`ennatys(new int[] {3, 4, 5, 9}, new int[] {8, 6, 10, 12})`	`3`
2	`ennatys(new int[] {3, 2, 10, 1}, new int[] {8, 9, 20, 5})`	`3`
3	`ennatys(new int[] {1, 3, 5}, new int[] {2, 4, 6})`	`1`
4	`ennatys(new int[] {100, 999}, new int[] {1000, 1001})`	`2`

Tehtävä 5

Sinulle on annettu taulukko kokonaislukuja ja tehtäväsi on järjestää se pienimmästä suurimpaan. Ainoa sallittu operaatio on kahden vierekkäisen luvun järjestyksen kääntäminen. Kuinka monta kääntöä tarvitset vähintään taulukon järjestämiseksi?

Esimerkiksi jos taulukko on {1, 5, 2, 4, 3}, riittää tehdä 4 kääntöä:

kääntö 5<->2, tulos {1, 2, 5, 4, 3}
kääntö 4<->3, tulos {1, 2, 5, 3, 4}
kääntö 5<->3, tulos {1, 2, 3, 5, 4}
kääntö 5<->4, tulos {1, 2, 3, 4, 5}

Toteutus

Toteuta seuraava metodi:

long laskeKaannot(int[] luvut)

Taulukko luvut sisältää 1..10⁵ kokonaislukua väliltä 1..10⁹.

Huomaathan että vastaus voi olla niin suuri, ettei se mahdu int -muuttujaan. Käytä siis longeja!

# metodin kutsu haluttu palautusarvo

1 laskeKaannot(new int[] {1, 2, 3, 4, 5}) 0

2 laskeKaannot(new int[] {5, 1, 2, 3, 4}) 4

3 laskeKaannot(new int[] {5, 4, 3, 2, 1}) 10

4 laskeKaannot(new int[] {1, 1, 1, 1, 1}) 0

5 laskeKaannot(new int[] {1, 5, 2, 4, 3}) 4

#	metodin kutsu	haluttu palautusarvo
1	`laskeKaannot(new int[] {1, 2, 3, 4, 5})`	`0`
2	`laskeKaannot(new int[] {5, 1, 2, 3, 4})`	`4`
3	`laskeKaannot(new int[] {5, 4, 3, 2, 1})`	`10`
4	`laskeKaannot(new int[] {1, 1, 1, 1, 1})`	`0`
5	`laskeKaannot(new int[] {1, 5, 2, 4, 3})`	`4`

Vinkki (valkoista tekstiä valkoisella taustalla): lomitusjärjestäminen.