Annettuna on merkkijono, jossa jokainen merkki on 0
tai 1
. Tehtäväsi on muuttaa osa biteistä vastakkaisiksi niin, että muutosten jälkeen missään kohdassa ei ole vierekkäin kahta samaa bittiä. Mikä on pienin määrä muutoksia?
Esimerkiksi merkkijonossa 10010001
tarvitaan vähintään kolme muutosta. Optimaalinen ratkaisu on muuttaa kohdissa 0, 1 ja 5 olevat bitit, jolloin tuloksena on merkkijono 01010101
.
Voit olettaa, että merkkijonon pituus on enintään 10^5.
Python
Toteuta tiedostoon bitstring.py
funktio calculate
, joka ilmoittaa pienimmän muutosten määrän.
def calculate(s): # TODO if __name__ == "__main__": print(calculate("1010")) # 0 print(calculate("1111")) # 2 print(calculate("10010001")) # 3
Java
Toteuta tiedostoon BitString.java
metodi calculate
, joka ilmoittaa pienimmän muutosten määrän.
public class BitString { public int calculate(String s) { // TODO } public static void main(String[] args) { BitString b = new BitString(); System.out.println(b.calculate("1010")); // 0 System.out.println(b.calculate("1111")); // 2 System.out.println(b.calculate("10010001")); // 3 } }