Bonusviikko

TMC bonusviikko

Tehtävien deadline: su-ma yö 21.3. kello 01:59.

Bonusviikolla on aiempien viikkojen aiheisiin liittyviä tehtäviä. Tehtävistä saa pisteitä täysin samalla tavalla kuin normaaleista TMC-tehtävistä, mutta ne eivät kasvata virallista TMC-pistemaksimia. Kurssilla on siis mahdollisuus tehdä enemmän TMC-tehtäviä kuin "maksimimäärä".

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(lista, 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 DNA-ketju, ja tehtäväsi on etsiä siitä pisin osajono, jossa on yhtä monta jokaista merkkiä A, C, G ja T.

Esimerkiksi ketjussa ACGTACGT pisin osajono on koko ketju, jossa on 2 kertaa jokaista merkkiä. Vastaavasti ketjussa TTATCGTT pisin osajono on ATCG, jossa on kerran jokaista merkkiä.

Toteutus

Toteuta seuraava metodi:

int pisinTasainen(String mjono)

Merkkijono mjono sisältää DNA-ketjun, jonka pituus on 1..10⁵ merkkiä.

Metodin tulee palauttaa pisimmän osajonon pituus, jossa on jokaista merkkiä yhtä monta. Jos mitään tällaista osajonoa ei ole, metodin tulee palauttaa 0.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`pisinTasainen("ACGTACGT")`	`8`
2	`pisinTasainen("CAATGTCG")`	`8`
3	`pisinTasainen("TTATCGTT")`	`4`
4	`pisinTasainen("AAAAAAAA")`	`0`