viikko1.html

---
layout: material
title: Viikko 1
redirect_from:
  - /
---
<section id="huomautus_lukijalle">
	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.
</section>
<div class="exercise"  id="t1">

	<header>
		<h1>Tehtävä 1</h1>
	</header>

	<div>
		<p>
			Tehtäväsi on tarkistaa, onko merkkijonossa jossain kohdassa kaksi samaa merkkiä peräkkäin.
		</p>

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>boolean kaksiSamaa(String mjono)</code>
		</p>

		<p>
			Parametri
			<code>mjono</code>
			on merkkijono, joka muodostuu merkeistä <em>A..Z</em>
			ja jossa on 1..10 <sup>5</sup>
			merkkiä.
		</p>

		<p>
			Metodin tulee palauttaa
			<code>true</code>
			, jos merkkijonossa on kaksi samaa merkkiä peräkkäin, ja muuten
			<code>false</code>
			.
		</p>

		<h2>Esimerkit</h2>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>kaksiSamaa("ABAABA")</code>
					</td>
					<td>
						<code>true</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>kaksiSamaa("XXXXX")</code>
					</td>
					<td>
						<code>true</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>kaksiSamaa("ABCABC")</code>
					</td>
					<td>
						<code>false</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>kaksiSamaa("ABABA")</code>
					</td>
					<td>
						<code>false</code>
					</td>
				</tr>
			</tbody>
		</table>

	</div>

</div>

<div class="exercise"  id="t2">

	<header>
		<h1>Tehtävä 2</h1>
	</header>

	<div>
		<p>
			Tehtäväsi on etsiä merkkijonosta pisin samaa merkkiä toistava osuus ja laskea sen pituus.
		</p>

		<p>
			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ä.
		</p>

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>int pisinOsuus(String mjono)</code>
		</p>
		<p>
			Parametri
			<code>mjono</code>
			on merkkijono, joka muodostuu merkeistä <em>A..Z</em>
			ja jossa on 1..10 <sup>5</sup>
			merkkiä.
		</p>

		<p>
			Metodin tulee palauttaa merkkijonon pisimmän samaa merkkiä toistavan osuuden pituus.
		</p>

		<h2>Esimerkit</h2>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>pisinOsuus("AABBBCC")</code>
					</td>
					<td>
						<code>3</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>pisinOsuus("AABBCC")</code>
					</td>
					<td>
						<code>2</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>pisinOsuus("XXXXXXX")</code>
					</td>
					<td>
						<code>7</code>
					</td>
				</tr>
				<tr>
					<td>4</td>
					<td>
						<code>pisinOsuus("AAABBBB")</code>
					</td>
					<td>
						<code>4</code>
					</td>
				</tr>
				<tr>
					<td>5</td>
					<td>
						<code>pisinOsuus("AAAABBB")</code>
					</td>
					<td>
						<code>4</code>
					</td>
				</tr>
				<tr>
					<td>6</td>
					<td>
						<code>pisinOsuus("ABBABBBA")</code>
					</td>
					<td>
						<code>3</code>
					</td>
				</tr>
			</tbody>
		</table>

	</div>

</div>

<div class="exercise"  id="t3">

	<header>
		<h1>Tehtävä 3</h1>
	</header>

	<div>
		<p>Merkkijono on palindromi, jos se on sama takaperin luettuna.</p>

		<p>
			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?
		</p>

		<p>
			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.
		</p>

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>boolean melkeinPalindromi(String mjono)</code>
		</p>

		<p>
			Parametri
			<code>mjono</code>
			on merkkijono, joka muodostuu merkeistä
			<em>A..Z</em>
			ja jossa on 1..10
			<sup>5</sup>
			merkkiä.
		</p>

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

		<h2>Esimerkit</h2>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>melkeinPalindromi("AABB")</code>
					</td>
					<td>
						<code>true</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>melkeinPalindromi("ABBBB")</code>
					</td>
					<td>
						<code>true</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>melkeinPalindromi("ABCBA")</code>
					</td>
					<td>
						<code>true</code>
					</td>
				</tr>
				<tr>
					<td>4</td>
					<td>
						<code>melkeinPalindromi("ABBB")</code>
					</td>
					<td>
						<code>false</code>
					</td>
				</tr>
				<tr>
					<td>5</td>
					<td>
						<code>melkeinPalindromi("AABCD")</code>
					</td>
					<td>
						<code>false</code>
					</td>
				</tr>
			</tbody>
		</table>

	</div>

</div>

<div class="exercise"  id="t4">

	<header>
		<h1>Tehtävä 4</h1>
	</header>

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

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

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>boolean melkeinPalindromi(String mjono)</code>
		</p>

		<p>
			Parametri mjono on merkkijono, joka muodostuu merkeistä
			<em>A..Z</em>
			ja jossa on 2..10
			<sup>5</sup>
			merkkiä.
		</p>

		<p>
			Metodin tulee palauttaa
			<code>true</code>
			, jos merkkijonosta saa palindromin poistamalla tasan yhden merkin, ja muuten
			<code>false</code>
			.
		</p>

		<h2>Esimerkit</h2>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>melkeinPalindromi("ABCBXA")</code>
					</td>
					<td>
						<code>true</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>melkeinPalindromi("ABCBAX")</code>
					</td>
					<td>
						<code>true</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>melkeinPalindromi("ABCXBA")</code>
					</td>
					<td>
						<code>true</code>
					</td>
				</tr>
				<tr>
					<td>4</td>
					<td>
						<code>melkeinPalindromi("ABCDE")</code>
					</td>
					<td>
						<code>false</code>
					</td>
				</tr>
				<tr>
					<td>5</td>
					<td>
						<code>melkeinPalindromi("BAAAAC")</code>
					</td>
					<td>
						<code>false</code>
					</td>
				</tr>
			</tbody>
		</table>

	</div>

</div>

<div class="exercise"  id="t5">

	<header>
		<h1>Tehtävä 5</h1>
	</header>

	<div>
		<p>
			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.
		</p>

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

		<h2>Toteutus</h2>

		<p>
			Toteuta metodi:
			<code>String jarjestaMerkit(String mjono)</code>
		</p>

		<p>
			Parametri
			<code>mjono</code>
			on merkkijono, joka muodostuu merkeistä
			<em>A..Z</em>
			ja jossa on 1..10
			<sup>5</sup>
			merkkiä.
		</p>

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

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

		<h2>Esimerkit</h2>

		<table>
			<thead>
				<tr>
					<th>#</th>
					<th>metodin kutsu</th>
					<th>haluttu palautusarvo</th>
				</tr>
			</thead>
			<tbody>
				<tr>
					<td>1</td>
					<td>
						<code>jarjestaMerkit("AAABBB")</code>
					</td>
					<td>
						<code>ABABAB</code>
					</td>
				</tr>
				<tr>
					<td>2</td>
					<td>
						<code>jarjestaMerkit("CBAED")</code>
					</td>
					<td>
						<code>ABCDE</code>
					</td>
				</tr>
				<tr>
					<td>3</td>
					<td>
						<code>jarjestaMerkit("AXAXA")</code>
					</td>
					<td>
						<code>AXAXA</code>
					</td>
				</tr>
				<tr>
					<td>4</td>
					<td>
						<code>jarjestaMerkit("CBAXXXX")</code>
					</td>
					<td>
						<code>XAXBXCX</code>
					</td>
				</tr>
			</tbody>
		</table>

		<p> <strong>HUOMAUTUS!</strong>
			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ä!
		</p>
	</div>

</div>