Tehtävien deadline: ma-su yö 8.2. 1:59.
Tällä ja kaikilla muillakin viikoilla on algoritmien pystyttävä
tuottamaan oikea vastaus alle yhdessä sekunnissa, ellei erikseen muuta
mainita. Viikon aiheena on järjestämisalgoritmien soveltaminen. Javan valmiita järjestämisalgoritmeja kuten Arrays.sort ja Collections.sort saa käyttää.
Uolevi on saanut syntymäpäivälahjaksi k euroa, jotka hän on päättänyt käyttää kirjakokoelmansa laajentamiseen. Uolevi ei kuitenkaan välitä kirjojen sisällöistä, sillä hän ei osaa lukea – ainoastaan kirjojen lukumäärällä on väliä. Läheinen kirjakauppa on lähettänyt hänelle tiedon siellä myytävien kirjojen hinnoista. Kuinka monta kirjaa Uolevi voi enimmillään ostaa?
Toteuta seuraava metodi:
int montakoKirjaa(int[] kirjat, int k)
Taulukko kirjat sisältää tiedot kaupassa myytävien kirjojen hinnoista. Jokaisen kirjan hinta, samoin kuin luku k, on kokonaisluku väliltä 1..109. Kirjakaupassa myytävien kirjojen lukumäärä on korkeintaan 100000.
Metodin tulee palauttaa kuinka monta kirjaa Uolevi voi ostaa rahoillaan.
| # | metodin kutsu | haluttu palautusarvo |
|---|---|---|
| 1 | montakoKirjaa(new int[] {2, 1, 4, 3}, 3) | 2 |
| 2 | montakoKirjaa(new int[] {1, 15, 5, 1}, 6) | 2 |
| 3 | montakoKirjaa(new int[] {3, 1, 2, 1}, 5) | 3 |
Tehtävänäsi on toteuttaa metodi int montakoErilaista(String[] taulukko), joka kertoo kuinka monta erilaista merkkijonoa syötteenä annetussa taulukossa on. Syötteenä annetun taulukon pituus on korkeintaan 100000 ja yksittäisen merkkijonon pituus on korkeintaan 10.
| # | metodin kutsu | haluttu palautusarvo |
|---|---|---|
| 1 | montakoErilaista(new String[] {"apina", "banaani", "cembalo"} | 3 |
| 2 | montakoErilaista(new String[] {"a", "b", "c", "d", "a"}) | 4 |
| 3 | montakoErilaista(new String[] {"abba", "abbb", "bbba", "babb", "bbab"}) | 5 |
| 4 | montakoErilaista(new String[] {"babb", "abbb", "bbba", "babb", "bbab"}) | 4 |
Tehtävänäsi on toteuttaa metodi boolean onkoSummaa(int[] taulukko, int k), joka kertoo löytyykö syötteenä annetusta taulukosta kahta lukua, joiden summa on tasan k. Syötteenä annetun taulukon pituus on korkeintaan 100000 ja sen sisältämät luvut ovat välillä -109..109
| # | metodin kutsu | haluttu palautusarvo |
|---|---|---|
| 1 | onkoSummaa(new int[] {1, 2, 3}, 5) | true |
| 2 | onkoSummaa(new int[] {1, 2, 3}, 6) | false |
| 3 | onkoSummaa(new int[] {1, 3, 3}, 6) | true |
| 4 | onkoSummaa(new int[] {1, 2, 3}, 6) | false |
Taulukko sisältää luvut 1..n
(jokaisen tasan kerran)
ja olet päättänyt kerätä ne järjestyksessä
pienimmästä suurimpaan.
Keräämisen aikana kuljet toistuvasti taulukon läpi
vasemmalta oikealle ja poimit joka kierroksella
seuraavana järjestykseen kuuluvat luvut.
Esimerkiksi lukujen kerääminen taulukosta
{1, 5, 2, 4, 3} vaatii 3 kierrosta:
ensimmäisellä kierroksella saat luvut
1, 2 ja 3, toisella luvun 4 ja
kolmannella luvun 5.
Tehtäväsi on laskea annetusta taulukosta, montako kierrosta tarvitset lukujen keräämiseen.
Toteuta seuraava metodi:
int keraaLuvut(int[] luvut)
Taulukko luvut sisältää luvut
1..n jossakin järjestyksessä.
Luku n on välillä 1..105.
Metodin tulee palauttaa lukujen keräämiseen tarvittava kierrosten määrä.
| # | metodin kutsu | haluttu palautusarvo |
|---|---|---|
| 1 | keraaLuvut(new int[] {1, 2, 3, 4, 5} | 1 |
| 2 | keraaLuvut(new int[] {5, 1, 2, 3, 4} | 2 |
| 3 | keraaLuvut(new int[] {5, 4, 3, 2, 1} | 5 |
| 4 | keraaLuvut(new int[] {1, 5, 2, 4, 3} | 3 |
Olet päättänyt osallistua tikanheittokilpailuun. Kilpailun säännöt ovat kuitenkin hyvin erikoiset: kilpailussa on joukko maalitauluja ja tarkoituksena on osua mahdollisimman moneen näistä. Ennen jokaista heittoa on kuitenkin valittava tasan yksi maalitaulu, johon yrittää heittää tikkaansa, jolloin kaikki muut maalitaulut siirretään syrjään siten, että niihin on mahdotonta osua. Sinulla on kuitenkin yksi etu: tiedät etukäteen mihin heittosi tulevat osumaan. Kuinka moneen eri tauluun voit osua?
Heittorata koostuu pisteistä [0, 109] ja heittokilpailun maalitaulut ovat sen osavälejä [ai, ai+w], missä ai saadaan parametrina tulevista taulukoista ja w on leveysparametri, joka on kaikilla maalitauluilla sama. Maalitaulujen päätepisteet ovat kokonaislukuja. Tiedot heittojesi osumakohdista löytyvät syötteenä tulevasta taulukosta heitot. Kohtaan x osuva heitto osuu tauluun [a, b] mikäli a≤x≤b. Huomaathan että radan maalitaulut voivat mennä päällekkäin.
Toteuta seuraava metodi:
int parasTulos(int[] a, int w, int[] heitot)
Taulukot a ja luku w sisältävät tiedot maalitauluista. Voit olettaa, että a[i]+w≤109. Sekä a, että heitot sisältävät lukuja väliltä 0..109. Kunkin taulukon pituus on enintään 100000.
Metodin tulee palauttaa kuinka moneen eri maalitauluun voit osua heitoillasi.
| # | metodin kutsu | haluttu palautusarvo |
|---|---|---|
| 1 | parasTulos(new int[] {3, 1, 4, 2}, 1, new int[] {2, 2, 2, 2}) | 2 |
| 2 | parasTulos(new int[] {1, 1, 1, 1}, 2, new int[] {1, 4, 2, 3}) | 3 |
| 3 | parasTulos(new int[] {1, 4, 1, 4}, 2, new int[] {4, 1, 4, 1}) | 4 |
| 4 | parasTulos(new int[] {0, 1, 2, 3, 4}, 3, new int[] {4, 3, 2, 1, 0}) | 5 |