翻轉元素將最大連續元素最小化到一起

Question

我給出了一個1和0的數組，以及一個數字k。我最多允許翻轉數組元素k次（0到1或1到0）。

我需要編寫一個算法來翻轉至多K個元素的狀態，以便使具有相同元素的最大連續塊元素的大小最小化。

ex: 

Array : 110001111 and k=2; 
Solution is 2 , because: we can change the string to: 110101011, and the length of the maximum consecutive length is minimised to 2. 

Array : 1001 k=1 
Solution is 2, because: If we don't change the input string at all, the answer will be 2. It is the best value we can achieve under the given conditions. 

有人能爲我提供解決這個問題的方法嗎？

Answer 1

讓我嘗試啓動簡化這個問題： 我們有一個數字的列表，代表同一類型的序列： [a1,a2,a3...a_m]使得它們的總和n

的k操作是下列任何一項：

1. 與[a_i^1,1,a_i^2]
2. 變化a_i到a_i-1和更換至a_{i-1}+1
3. 變化a_i到a_i+1和a_{i-1}到a_{i-1}-1

但很明顯，操作2和3是隻有a_i<=2優於操作1，除非有隻有一個元素的總長度爲2在這種情況下做任何事情都是毫無意義的。所以我們可以認爲這是如何分割價值的問題，在這種情況下，我們不關心a_i的操作順序k您需要執行哪些操作max(a1,a2,...)最後最小

很明顯，如果我們不在最大字符串內翻轉一點，那麼我們並沒有改變最大值。同樣清楚的是，我們翻轉比特的順序並不重要（例如，如果我們先將7號位翻轉然後再將4號位翻轉，或者從4號位開始，然後將7號位翻轉，則無關緊要）。所以我們不妨決定從分裂最大的連續區塊開始。

最大連續塊的最大長度爲n，所以我們已經找到了O(n^k)算法。

Answer 2

讓f(i,len,k,state)代表最小序列高達索引i，其中len是當前序列長度，k是迄今爲止翻轉的數量和state是a[i]狀態。

然後：

if a[i] == 0: 
    // starting a new sequence 
    f(i, 1, k, 0) = min(f(i-1, len, k, 1) for all len) 

    // adding to a sequence (len > 1) 
    f(i, len, k, 0) = max(len, f(i-1, len-1, k, 0)) 

    // starting a new sequence 
    f(i, 1, k, 1) = min(f(i-1, len, k-1, 0) for all len) 

    // adding to a sequence (len > 1) 
    f(i, len, k, 1) = max(len, f(i-1, len-1, k-1, 1)) 

if a[i] == 1: 
    ...left as an exercise 

JavaScript代碼：

function f(a,i,len,k,state){ 
 
    // We cannot change the state of a[i] if k is zero 
 
    if (k === 0 && a[i] != state) 
 
    return Infinity; 
 
    
 
    // The first element is a sequence of length 1 
 
    if (i === 0) 
 
    return 1; 
 
    
 
    var oppositeState = state == 0 ? 1 : 0; 
 
    
 
    if (a[i] == state){ 
 
    // Starting a new sequence 
 
    if (len === 1){ 
 
     var best = Infinity; 
 
     
 
     for (var l=1; l<i+1; l++) 
 
     best = Math.min(best, f(a, i-1, l, k, oppositeState)); 
 
    
 
     return best; 
 
     
 
    // Adding to a sequence (len > 1) 
 
    } else { 
 
     return Math.max(len, f(a, i-1, len-1, k, state)); 
 
    } 
 

 
    // a[i] does not equal state 
 
    } else if (k > 0) { 
 
    // Starting a new sequence 
 
    if (len === 1){ 
 
     var best = Infinity; 
 
     
 
     for (var l=1; l<i+1; l++) 
 
     best = Math.min(best, f(a, i-1, l, k-1, oppositeState)); 
 
    
 
     return best; 
 
     
 
    // Adding to a sequence (len > 1) 
 
    } else { 
 
     return Math.max(len, f(a, i-1, len-1, k-1, state)); 
 
    } 
 

 
    // If k is zero, we cannot change the state of a[i] 
 
    } else { 
 
    return Infinity; 
 
    } 
 
} 
 

 
function g(arr,k){ 
 
    var best = Infinity; 
 
    
 
    for (var l=1; l<=2*arr.length; l++) 
 
    best = Math.min(best, f(arr, arr.length-1, Math.ceil(l/2), k, l % 2)); 
 
    
 
    return best; 
 
} 
 

 
console.log(g('110001111',2)); // 2 
 

 
console.log(g('1001',1)); // 2 
 

 
console.log(g('111111',0)); // 6