Subsegmento más largo de ‘1’ formado cambiando como máximo k ‘0’s | Conjunto 2 (usando cola)

Dada una array binaria a[] y un número k , necesitamos encontrar la longitud del subsegmento más largo posible de ‘1’ cambiando como máximo k ‘0’s .

Ejemplos: 

Entrada : a[] = {1, 0, 0, 1, 1, 0, 1}, k = 1
Salida : 4
Explicación : Aquí, solo debemos cambiar 1 cero (0). La longitud máxima posible que podemos obtener es cambiando el tercer cero en la array, obtenemos a[] = {1, 0, 0, 1, 1, 1, 1}

Entrada : a[] = {1, 0, 0, 1, 0, 1, 0, 1, 0, 1}, k = 2
Salida : 5 

Enfoque de dos punteros: Consulte el Conjunto 1 de este artículo para la implementación del enfoque de dos punteros.
 

Enfoque de cola: la tarea se puede resolver con la ayuda de una cola . Almacene los índices de 0 encontrados hasta ahora en una cola . Para cada 0 , verifique si el valor de K es mayor que 0 o no, si es distinto de cero , cámbielo a 1 y maximice la longitud del subsegmento correspondientemente, de lo contrario, mueva el puntero izquierdo (inicialmente en el índice de inicio de la string ) al índice del primer cero (frente a la cola) + 1 .
Siga los pasos a continuación para resolver el problema:

• Declare una cola para almacenar índices de 0 visitados.
• Iterar sobre la string y si el carácter actual es 0 y quedan algunos hechizos, es decir (k != 0) , entonces use el hechizo, es decir (decremento k). Además, almacene el índice de «0» ocurrido.
• Si k = 0 , saque el frente de la cola y guárdelo en una variable.
• Almacene la longitud como máxima entre i-low y la de la respuesta anterior .
• Cambie bajo al índice del primer «0» + 1 e incremente k.
• Finalmente, devuelva la respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to Find longest subsegment of 1s
int get(int n, int k, int arr[])
{
    // Queue for storing indices of 0s
    queue<int> q;
  
    int low = 0;
    int ans = INT_MIN;
  
    int p = k;
    int i = 0;
  
    while (i < n) {
        // If the current character is 1
        // then increment i by 1
        if (arr[i] == 1) {
            i++;
        }
  
        // If the current character is 0
        // and some spells are
        // left then use them
        else if (arr[i] == 0 && k != 0) {
            q.push(i);
            k--;
            i++;
        }
        // If k == 0
        else {
            // Take out the index where
            // the first "0" was found
            int x = q.front();
            q.pop();
  
            // Store the length as max
            // between i-low and that
            // of the previous answer
            ans = max(ans, i - low);
  
            // Shift low to index
            // of first "O" + 1
            low = x + 1;
  
            // Increase spell by 1
            k++;
        }
  
        // Store the length between
        // the i-low and that of
        // previous answer
        ans = max(ans, i - low);
    }
    return ans;
}
  
// Driver Code
int main()
{
    int N = 10;
    int K = 2;
    int arr[] = { 1, 0, 0, 1, 0,
                  1, 0, 1, 0, 1 };
  
    cout << get(N, K, arr) << endl;
    return 0;
}

// Java program for the above approach
import java.util.LinkedList;
import java.util.Queue;
  
class GFG{
  
// Function to Find longest subsegment of 1s
static int get(int n, int k, int arr[]) 
{
      
    // Queue for storing indices of 0s
    Queue<Integer> q = new LinkedList<Integer>();
  
    int low = 0;
    int ans = Integer.MIN_VALUE;
    int i = 0;
  
    while (i < n)
    {
          
        // If the current character is 1
        // then increment i by 1
        if (arr[i] == 1) 
        {
            i++;
        }
  
        // If the current character is 0
        // and some spells are
        // left then use them
        else if (arr[i] == 0 && k != 0) 
        {
            q.add(i);
            k--;
            i++;
        }
          
        // If k == 0
        else
        {
              
            // Take out the index where
            // the first "0" was found
            int x = q.peek();
            q.remove();
  
            // Store the length as max
            // between i-low and that
            // of the previous answer
            ans = Math.max(ans, i - low);
  
            // Shift low to index
            // of first "O" + 1
            low = x + 1;
  
            // Increase spell by 1
            k++;
        }
  
        // Store the length between
        // the i-low and that of
        // previous answer
        ans = Math.max(ans, i - low);
    }
    return ans;
}
  
// Driver Code
public static void main(String args[])
{
    int N = 10;
    int K = 2;
    int arr[] = { 1, 0, 0, 1, 0,
                  1, 0, 1, 0, 1 };
  
    System.out.println(get(N, K, arr));
}
}
  
// This code is contributed by gfking

# Python code for the above approach
  
# Function to Find longest subsegment of 1s
def get(n, k, arr):
    
    # Queue for storing indices of 0s
    q = []
  
    low = 0
    ans = 10 ** -9
  
    p = k
    i = 0
  
    while (i < n):
        
        # If the current character is 1
        # then increment i by 1
        if (arr[i] == 1):
            i += 1
  
        # If the current character is 0
        # and some spells are
        # left then use them
        elif (arr[i] == 0 and k != 0):
            q.append(i)
            k -= 1
            i += 1
        # If k == 0
        else:
            # Take out the index where
            # the first "0" was found
            x = q[0]
            q.pop(0)
  
            # Store the length as max
            # between i-low and that
            # of the previous answer
            ans = max(ans, i - low)
  
            # Shift low to index
            # of first "O" + 1
            low = x + 1
  
            # Increase spell by 1
            k += 1
  
        # Store the length between
        # the i-low and that of
        # previous answer
        ans = max(ans, i - low)
      
    return ans
  
# Driver Code
N = 10
K = 2
arr = [1, 0, 0, 1, 0, 1, 0, 1, 0, 1]
print(get(N, K, arr))
  
# This code is contributed by Saurabh Jaiswal

// C# program for the above approach
using System;
using System.Collections.Generic;
  
class GFG {
  
  // Function to Find longest subsegment of 1s
  static int get(int n, int k, int[] arr)
  {
  
    // Queue for storing indices of 0s
    Queue<int> q = new Queue<int>();
  
    int low = 0;
    int ans = Int32.MinValue;
    int i = 0;
  
    while (i < n) {
  
      // If the current character is 1
      // then increment i by 1
      if (arr[i] == 1) {
        i++;
      }
  
      // If the current character is 0
      // and some spells are
      // left then use them
      else if (arr[i] == 0 && k != 0) {
        q.Enqueue(i);
        k--;
        i++;
      }
  
      // If k == 0
      else {
  
        // Take out the index where
        // the first "0" was found
        int x = q.Peek();
        q.Dequeue();
  
        // Store the length as max
        // between i-low and that
        // of the previous answer
        ans = Math.Max(ans, i - low);
  
        // Shift low to index
        // of first "O" + 1
        low = x + 1;
  
        // Increase spell by 1
        k++;
      }
  
      // Store the length between
      // the i-low and that of
      // previous answer
      ans = Math.Max(ans, i - low);
    }
    return ans;
  }
  
  // Driver Code
  public static void Main()
  {
    int N = 10;
    int K = 2;
    int[] arr = { 1, 0, 0, 1, 0, 1, 0, 1, 0, 1 };
  
    Console.WriteLine(get(N, K, arr));
  }
}
  
// This code is contributed by ukasp.

<script>
        // JavaScript code for the above approach
  
  
        // Function to Find longest subsegment of 1s
        function get(n, k, arr) {
            // Queue for storing indices of 0s
            let q = [];
  
            let low = 0;
            let ans = Number.MIN_VALUE;
  
            let p = k;
            let i = 0;
  
            while (i < n) {
                // If the current character is 1
                // then increment i by 1
                if (arr[i] == 1) {
                    i++;
                }
  
                // If the current character is 0
                // and some spells are
                // left then use them
                else if (arr[i] == 0 && k != 0) {
                    q.push(i);
                    k--;
                    i++;
                }
                // If k == 0
                else {
                    // Take out the index where
                    // the first "0" was found
                    let x = q[0];
                    q.shift();
  
                    // Store the length as max
                    // between i-low and that
                    // of the previous answer
                    ans = Math.max(ans, i - low);
  
                    // Shift low to index
                    // of first "O" + 1
                    low = x + 1;
  
                    // Increase spell by 1
                    k++;
                }
  
                // Store the length between
                // the i-low and that of
                // previous answer
                ans = Math.max(ans, i - low);
            }
            return ans;
        }
  
        // Driver Code
  
        let N = 10;
        let K = 2;
        let arr = [1, 0, 0, 1, 0,
            1, 0, 1, 0, 1];
  
        document.write(get(N, K, arr) + '<br>');
  
  // This code is contributed by Potta Lokesh
    </script>

5

Tiempo Complejidad : O(N)
Espacio Auxiliar : O(k)

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array