Wie macht man p aufeinanderfolgende Zeichen, indem man k Tauschen in einem String macht?

Question

Es gibt einen String von 1's und 0's zum Beispiel 110001110. Ich habe zwei Nummern gegeben k und p und ich habe zu prüfen, ob ich atmost p in Folge 1's oder 0's indem k Swaps und Swaps bekommen kann ich meine, wenn es 1 macht es dann 0 und umgekehrt.

EDIT- Ich denke, ich habe nicht klar erklärt. Zum Beispiel lassen Sie die Zeichenfolge 1110000111 und lassen Sie p = 3 und k = 1. So kann ich mit 1 Swaps fast 3 aufeinanderfolgende 1's oder 0's bekommen, für die die Antwort ist, da ich es in 1110010111 ändern kann.

Answer 1

Sie könnten dies in linearer Zeit mit einer einfachen Schleife tun. Nachdem Sie eine monotone Sequenz von entweder 0 oder 1 festgestellt haben, würden Sie berechnen, wie viele Flips mit einer einfachen Formel notwendig wären. Diese Flips können immer so gemacht werden, dass die äußeren Ziffern dieser Sequenz unberührt bleiben, außer für den Fall, dass p 1 ist. In diesem Fall müssen die Flips dazu gebracht werden entweder 01010101 ... oder auch 101010101 zu bekommen .... Das kann auch mit einem einfachen Modulo-Ausdruck geschehen. Dann würde das Beste von beiden genommen (weniger Swaps). Hier

ist eine Implementierung in JavaScript mit zwei Probe läuft für den generischen Fall (p> 1) und den erwähnten Sonderfall (p = 1):

function swapsForMaxSequence(s, maxSize) { 
 
    var head, tail, swaps; 
 

 
    if (maxSize < 1) return false; 
 
    
 
    swaps = 0; 
 
    if (maxSize === 1) { // Special case 
 
     // 0 and 1 should be alternating: 
 
     for (head = 0; head < s.length; head++) { // n iterations 
 
      if (Number(s[head]) == head % 2) swaps++; 
 
     } 
 
     // Either the made swaps or the opposite swaps would do it: 
 
     return Math.min(swaps, s.length - swaps); 
 
    } 
 
    tail = 0; 
 
    for (head = 1; head <= s.length; head++) { // n iterations 
 
     if (head === s.length || s[head] != s[tail]) { // end of sequence? 
 
      swaps += Math.floor((head - tail)/(maxSize+1)); 
 
      tail = head; // Start of new sequence 
 
     } 
 
    } 
 
    return swaps; 
 
} 
 

 
// Sample input: 
 
var s = '10110101010', // Special case 
 
    k = 1, 
 
    p = 1; 
 

 
// Display input: 
 
console.log('s:', s, 'k:', k, 'p:', p); 
 

 
// Run the algorithm 
 
result = swapsForMaxSequence(s, p); 
 

 
// Display outcome: 
 
console.log('result:', result); 
 

 
// Second sample: 
 
var s = '1110000111', // Special case 
 
    k = 1, 
 
    p = 3; 
 

 
// Display input: 
 
console.log('s:', s, 'k:', k, 'p:', p); 
 

 
// Run the algorithm 
 
result = swapsForMaxSequence(s, p); 
 

 
// Display outcome: 
 
console.log('result:', result);