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++
// 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
// 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
Python3
# 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#
// 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.
Javascript
<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
Publicación traducida automáticamente
Artículo escrito por harshalkhond y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA