翻转元素将最大连续元素最小化到一起

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