關於二進制字符串的數學難題

Question

我得到了一個長度爲n的二進制字符串，我需要找到執行這樣的操作的最小數目，使得字符串不包含超過k個連續的相等字符。

我被允許執行的一種操作是翻轉字符串的任何第i個字符。翻轉字符意味着將'1'改爲'0'或將'0'改爲'1'。

例如：

如果n = 4，K = 1個字符串= 1001

然後回答：

串= 1010和最小操作= 2

我需要也找到新的字符串。

誰能告訴我要解決的問題考慮ň< = 10^5

Answer 1

對於k的高效算法= 1只有兩種可能的輸出字符串 - 一個從0開始和一個與1.開始可以檢查他們哪一個更接近輸入字符串。

對於較大的k，您可以只查看k + 1個相同字符的每個序列，並在內部對其進行修復 - 而不更改任何一端的字符。對於k'> k的序列，您需要floor（k'/（k + 1））翻轉。不難證明這是最佳的。

運行時間是線性的，額外的空間是恆定的。

Answer 2

還有一個辦法：

if k>1: 
    if k+1 matching characters are found: 
     if a[k+1]==a[k+2]: 
      flip a[k+1] 
     else if a[k+1]!=a[k+2]: 
      flip a[k] 

對於k = 1，你可以做到這一點！ 這裏翻轉裝置從1到0，反之亦然

Answer 3

有兩種情況：

1)For k>1 
    We have 2 possibilities. 
    a)one that is starting with 0: 
     eg:0101010101 
    b)one that is starrting with 1 
     eg:10101010..... 
We should now calculate the distance(the number of different elements between the 2 strings)for each possiblity.Then the ans will be the one that has minimum changes. 

2）對於k> 1

res2=0;res1=1; 
    c1=A[i];//it represents the last elemnet 
    i=1; 
    while(A[i]!='\0'){ 
     if(A[i]==c1){ 
     res1++;//the no of consecutive elements 
      if(res1>k){ 
       if(A[i]==A[i+1]) 
        flip(i);//it flips the ith element 
       else 
        flip(i-1); 
       res2++;//it counts the no of changes 
       res1=1; 
      }    
     } 
     else 
     res1=1; 

     c1=A[i]; 
     i++; 
    }