Viikko 1: TMC-tehtävät

Tehtävien deadline: 19.01.2015 01:59.

Huom! Kaikissa tehtävissä tällä ja tulevilla viikoilla aikaraja on 1 sekunti. Tämä tarkoittaa, että ratkaisun tulee olla tehokas, jotta se hyväksytään.

Tehtävä 1

Tehtäväsi on tarkistaa, onko merkkijonossa jossain kohdassa kaksi samaa merkkiä peräkkäin.

Toteutus

Toteuta seuraava metodi:

boolean kaksiSamaa(String mjono)

Parametri mjono on merkkijono, joka muodostuu merkeistä A..Z ja jossa on 1..10⁵ merkkiä.

Metodin tulee palauttaa true, jos merkkijonossa on kaksi samaa merkkiä peräkkäin, ja muuten false.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`kaksiSamaa("ABAABA")`	`true`
2	`kaksiSamaa("XXXXX")`	`true`
3	`kaksiSamaa("ABCABC")`	`false`
3	`kaksiSamaa("ABABA")`	`false`

Tehtävä 2

Tehtäväsi on etsiä merkkijonosta pisin samaa merkkiä toistava osuus ja laskea sen pituus.

Esimerkiksi merkkijonossa ABBACCCCAAA samaa merkkiä toistavat osuudet ovat A, BB, A, CCCC ja AAA, ja näistä pisin on osuus CCCC, johon kuuluu 4 merkkiä.

Toteutus

Toteuta seuraava metodi:

int pisinOsuus(String mjono)

Parametri mjono on merkkijono, joka muodostuu merkeistä A..Z ja jossa on 1..10⁵ merkkiä.

Metodin tulee palauttaa merkkijonon pisimmän samaa merkkiä toistavan osuuden pituus.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`pisinOsuus("AABBBCC")`	`3`
2	`pisinOsuus("AABBCC")`	`2`
3	`pisinOsuus("XXXXXXX")`	`7`
4	`pisinOsuus("AAABBBB")`	`4`
5	`pisinOsuus("AAAABBB")`	`4`
6	`pisinOsuus("ABBABBBA")`	`3`

Tehtävä 3

Merkkijono on palindromi, jos se on sama takaperin luettuna.

Sinulle on annettu merkkijono ja tehtäväsi on muodostaa palindromi siinä olevista merkeistä. Saat järjestää merkit mihin tahansa järjestykseen. Onko tehtäväsi mahdollinen?

Esimerkiksi jos merkkijono on AABACAB, voit muuttaa sen merkit järjestykseen AABCBAA, jolloin tuloksena on palindromi. Mutta merkkijonosta AABBCAB ei saa mitenkään tehtyä palindromia.

Toteutus

Toteuta seuraava metodi:

boolean melkeinPalindromi(String mjono)

Parametri mjono on merkkijono, joka muodostuu merkeistä A..Z ja jossa on 1..10⁵ merkkiä.

Metodin tulee palauttaa true, jos merkkijonon merkeistä saa palindromin järjestämällä ne sopivasti, ja muuten false.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`melkeinPalindromi("AABB")`	`true`
2	`melkeinPalindromi("ABBBB")`	`true`
3	`melkeinPalindromi("ABCBA")`	`true`
4	`melkeinPalindromi("ABBB")`	`false`
5	`melkeinPalindromi("AABCD")`	`false`

Tehtävä 4

Sinulle on annettu merkkijono ja tehtäväsi on muuttaa se palindromiksi poistamalla siitä tasan yksi merkki. Onko tehtäväsi mahdollinen?

Esimerkiksi jos merkkijono on AABCCBAXA, voit poistaa siitä merkin X, jolloin tuloksena on palindromi. Mutta merkkijonosta AXABCCBAYA ei saa mitenkään tehtyä palindromia.

Toteutus

Toteuta seuraava metodi:

boolean melkeinPalindromi(String mjono)

Parametri mjono on merkkijono, joka muodostuu merkeistä A..Z ja jossa on 2..10⁵ merkkiä.

Metodin tulee palauttaa true, jos merkkijonosta saa palindromin poistamalla tasan yhden merkin, ja muuten false.

asd

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`melkeinPalindromi("ABCBXA")`	`true`
2	`melkeinPalindromi("ABCBAX")`	`true`
3	`melkeinPalindromi("ABCXBA")`	`true`
4	`melkeinPalindromi("ABCDE")`	`false`
5	`melkeinPalindromi("BAAAAC")`	`false`

Tehtävä 5

Sinulle on annettu merkkijono ja tehtäväsi on järjestää merkit niin, että missään kohdassa ei ole kahta samaa merkkiä peräkkäin. Jos ratkaisuja on useita, valitse aakkosjärjestyksessä ensimmäinen ratkaisu.

Esimerkiksi merkit AAABBB voi järjestää kahdella tavalla: ABABAB ja BABABA. Näistä ABABAB on ensin aakkosissa, joten tämä on oikea ratkaisu.

Toteutus

Toteuta seuraava metodi:

String jarjestaMerkit(String mjono)

Parametri mjono on merkkijono, joka muodostuu merkeistä A..Z ja jossa on 1..10⁵ merkkiä.

Metodin tulee palauttaa merkkijono, jossa on samat merkit kuin merkkijonossa mjono, mutta missään kohdassa ei ole kahta samaa merkkiä peräkkäin.

Jos ratkaisuja on useita, metodin tulee palauttaa aakkosjärjestyksessä ensimmäinen ratkaisu. Voit olettaa, että kaikissa testeissä ratkaisu on olemassa.

Esimerkit

#	metodin kutsu	haluttu palautusarvo
1	`jarjestaMerkit("AAABBB")`	`ABABAB`
2	`jarjestaMerkit("CBAED")`	`ABCDE`
3	`jarjestaMerkit("AXAXA")`	`AXAXA`
4	`jarjestaMerkit("CBAXXXX")`	`XAXBXCX`

HUOMAUTUS! Jos rakennat merkkijonon merkki kerrallaan, käytä joko StringBuilder:ia tai char-taulukkoa. Merkkijonon kasvattaminen yhdellä merkillä on erittäin hidasta Javassa, eikä pelkkää Stringiä käyttävä ratkaisu todennäköisesti läpäise testejä!