Tüm 1'lere ikili sayı akışını dönüştürün

Question

"10101" gibi bir dizi ikili karaktere sahibim. Tüm 1'lere dönüştürmem gerekiyor. Bunu dönüştürmek için ihtiyacım olan yöntem, aşağıdaki diziyi 0'dan j'ye çeviren ve her karakterin 0'dan j indeksine çevrilmesini sağlayan yöntemdir.

void ReverseAndFlip(string &str, int j) 
{ 
    int i=0; 
    while(i<j) 
    { 
     char temp = str[i]; 
     str[i++]=str[j]; 
     str[j--]=temp; 
    } 
    for(int k=0;k<=j;k++) 
    { 
     if(str[k]=='0') 
      str[k] = '1'; 
     else 
      str[k]=='0'; 
    } 
} 

Bütün 1'ler içine ikili dize dönüştürmek için ReverseAndFlip fonksiyonu için gerekli minimum sayıda arama belirlemek gerekir.

Answer 1

Sadece için bir algoritmanın problemini çözdüğünü sanmıyorum, bu yüzden bir tane göndereceğim, ama kuşkusuz bu soruya tamamen cevap vermiyor. Göstermek üzere olduğum şeyin minimumu henüz belirlenmemiştir, ancak n uzunluğundaki bir ikili kelime için en n adımda ihtiyacımız olduğunu garanti edebilirim.

Buradaki hile, gerçekten kelimenin ön tarafındaki bitleri manipüle edebilmemizdir, arka tarafa değil. Bu, bazı "ön" gruplamalar yapmamız gerektiğini ima eder. Yani algoritmam şu şekildedir. Kelimenin önünde başlayan tutarlı bir rakamın (1 ya da 0) en büyük alt dizisini bulun. Ardından, tüm bu bitleri çevirin (çevirme ve geri çevirme işlemlerinin hepsi aynıysa geri sayım ile aynı olduğunu unutmayın). Ardından, tüm 1'lere sahip olana kadar işlemi tekrarlayın.

Örnek:

|  j=1 ||  j=2 ||| j=3 |||| j=4 
"10101" ---> "00101" ---> "11101" ---> "00001" ---> "11111" 

Başka Örnek: kelime Yani 0. ile biterse

||   j=1 ||||  j=2 |||||  j=3 |||||| 
"0011010111" ---> "1111010111" ---> "0000010111" ---> "1111110111" 

j=4 |||||||  j=5 
---> "0000000111" ---> "1111111111" 

Yani, bu algoritma elimizde birçok "çevirir" çalışır, artı bir, " 10101 "her bir bit çevirir ve bir ile biter, çünkü 4 döndürür (" 1x0x1x0x1 ") vardır. Böylece, 4 toplam saygısız. "0011010111", 5 dönüşüme sahiptir ("00x11x0x1x0x111"). Sonunda bir 0 rakamı varsa, bonus turumuz var. Örneğin, "11001010" ("11x00x1x0x1x0x") 6 döndürür, çünkü son basamak 0'dır, bu nedenle son adım tüm 0'ları 1 saniyeye çevirir. Öyleyse:

  j=1   j=2   j=3   j=4 
11001010 ---> 00001010 ---> 11111010 ---> 00000010 ---> 11111110 

j=5   j=6 
---> 00000000 ---> 11111111 

Şimdi bunun neden/sayıştırma sayısının en azı olduğunu gösterme. En azını göstermenin kolay olmadığına göre, örneklerimden birini (veya başka bir örneği) yukarıdaki algoritmadan daha hızlı bir şekilde çevirmenin bir yolunu bulmanız yeterli.