Viikko 5: TMC-tehtävät

Tehtävien deadline: ma 12.10. klo 04:01

Viikon teemana on hajautusrakenteiden ja yleisemmin hajautuksen soveltaminen, sekä binääripuut.

Tehtävä 1

Sinulle on annettu taulukko kokonaislukuja, ja tehtäväsi on selvittää, onko taulukossa kahta lukua, joiden summa on x.

Esimerkiksi jos taulukko on {3, 4, 2, 8} ja x on 5, voidaan valita luvut 3 ja 2.

Toteutus

Toteuta seuraava metodi:

boolean etsiSumma(int[] luvut, int x)

Taulukko luvut sisältää 1..10⁵ kokonaislukua väliltä –10⁹..10⁹. Luku x on kokonaisluku väliltä –10⁹..10⁹.

Metodin tulee palauttaa true, jos summan saa kahdesta luvusta, ja muuten false.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`etsiSumma(new int[] {1, 2, 3}, 5)`	`true`
2	`etsiSumma(new int[] {1, 2, 3}, 6)`	`false`
3	`etsiSumma(new int[] {1, 3, 3}, 6)`	`true`
4	`etsiSumma(new int[] {1, 2, 3}, 6)`	`false`

Tehtävä 2

Uolevi on äärettömässä ruudukossa ja lähtee liikkeelle ruudusta (0, 0). Hän kulkee joka askeleella yhden ruudun vasemmalle, oikealle, ylöspäin tai alaspäin. Milloin Uolevi palaa ruutuun, jossa hän on ollut aiemmin (mihin tahansa matkan varrella olleeseen ruutuun)?

Toteutus

Toteuta seuraava metodi:

int reitinPituus(String reitti)

Parametri reitti kuvaa Uolevin reitin. Se sisältää järjestyksessä suunnat, joihin Uolevi liikkuu. Jokainen suunta on yksi merkeistä V, O, Y ja A. Merkkijonon pituus on 1..10⁵ merkkiä.

Metodin tulee palauttaa, montako askelta Uolevi liikkuu, ennen kuin hän palaa uudestaan samaan ruutuun. Jos Uolevi ei palaa koskaan samaan ruutuun reitin aikana, metodin tulee palauttaa 0.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`reitinPituus("YYVVAAOO")`	`8`
2	`reitinPituus("YVAOYVAO")`	`4`
3	`reitinPituus("YYYYYYYY")`	`0`
4	`reitinPituus("OYVVAOOO")`	`6`

Tehtävä 3

Sinulle on annettu binääripuu ja tehtäväsi on tutkia, onko puu täydellinen, eli onko jokainen polku juuresta alaspäin yhtä pitkä.

Toteutus

Toteuta seuraava metodi:

boolean taydellinen(Puu puu)

Parametri puu on binääripuu, jossa on 1..10⁵ solmua.

Metodin tulee palauttaa true, jos puu on täydellinen, ja muuten false.

Esimerkki

Seuraava koodi testaa metodia:

    Puu puu = new Puu(1,
                      new Puu(3,
                              new Puu(2, null, null),
                              new Puu(1, null, null)),
                      new Puu(3,
                              new Puu(3, null, null),
                              new Puu(2, null, null)));

    System.out.println(taydellinen(puu));

Koodin tulostuksen tulisi olla seuraava:

    true

Tehtävä 4

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ä 5

Sinulle on annettu DNA-ketju, joka muodostuu merkeistä A, C, G ja T. Tehtäväsi on selvittää, kuinka pitkä on lyhin DNA-ketju, joka ei ole annetun ketjun osajonona.

Esimerkiksi DNA-ketju ACGTACGT sisältää osajonona kaikki 1:n pituiset DNA-ketjut eli A, C, G ja T. Kahden pituiset osajonot ovat järjestyksessä AC, CG, GT, TA, AC, CG ja GT, eli esimerkiksi ketju AA puuttuu osajonoista. Niinpä lyhimmän ketjun pituus on 2.

Toteutus

Toteuta seuraava metodi:

int lyhinPuuttuva(String mjono)

Merkkijono mjono on DNA-ketju, jonka pituus on 1..10⁵ merkkiä.

Metodin tulee palauttaa lyhimmän ketjun pituus, joka ei ole osajonona annetussa ketjussa.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`lyhinPuuttuva("CCCCCCCC")`	`1`
2	`lyhinPuuttuva("ACGTACGT")`	`2`
3	`lyhinPuuttuva("ACAAGCAG")`	`1`
4	`lyhinPuuttuva("ACACACGT")`	`2`

VINKKI: javan String.substring(beginIndex, endIndex) metodista saattaa olla hyötyä.