최대 연속 요소를 최소화하기 위해 요소를 뒤집기

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] 자신의 합이

k 작업 n는 다음 중 하나입니다되도록 :

1. a_i-1 및에 [a_i^1,1,a_i^2]
2. 변경 a_i와 a_i 교체a_ia_{i-1}

a_{i-1}-1 것이 아니라이 동작을 2, 3 a_i<=2 경우 동작을 1 만 더 나은, 그리고 단 하나 개의 요소가 아니라면 및 총 길이가 2 꽤 분명 a_i+1 및 변경

a_{i-1}+1 to , 그 경우에는 아무 것도하지 않는 것이 무의미합니다. 따라서이 값을 분할하는 방법에 대한 질문으로 간주 할 수 있습니다.이 경우 a_i의 순서는 신경 쓰지 않습니다.

k 작업의 경우 수행해야 할 작업은 무엇입니까? kmax(a1,a2,...)은 끝 부분에서 최소값입니다.

최대 문자열 내에서 조금 뒤집지 않으면 최대 값을 변경하지 않았 음이 분명합니다. 우리가 비트를 뒤집는 순서는 중요하지 않습니다 (예 : 비트 번호 7을 뒤집고 비트 번호 4를 뒤집거나 비트 번호 4로 시작한 다음 비트 번호 7을 뒤집는 것이 중요하지 않음). 그래서 우리는 가장 큰 연속적인 블록을 분할하는 것으로 시작할 수도 있습니다.

최대 연속 블록은 최대 길이가 n이므로 O(n^k) 알고리즘을 이미 발견했습니다.

Answer 2

하자 f(i,len,k,state)len는 현재 시퀀스 길이 i 인덱스, 최대 최소의 서열을 나타내고, k 지금까지 플립의 수이고 statea[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 

자바 스크립트 코드 : // 메타 : [합의보기를 참조하시기 바랍니다] (HTTPS,이 플래그 얻을 찾고 사용자의

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