Dada una string binaria s y un número K, la tarea es encontrar el número máximo de 0 que se pueden reemplazar por 1 de manera que dos 1 adyacentes estén separados por al menos K 0 entre ellos.
Ejemplos:
Entrada: K = 2, s = “000000”
Salida: 2
Explicación:
Cambie los 0 en la posición 0 y 3. Luego, la string final será “100100” de modo que cada 1 esté separado por al menos 2 0 .Entrada: K = 1, s = «01001000100000»
Salida: 3
Explicación:
Cambie los 0 en las posiciones 6, 10 y 12. Luego, la string final será «01001010101010», de modo que cada 1 esté separado por al menos 1 0 .
Acercarse:
- Inserte todos los caracteres de la string dada en una array (digamos arr[]) .
- Recorra la array arr[] y convierta todos los 0 en -1 que se encuentran en <= K lugares cerca de un 1 ya existente . Esta operación da todas las posiciones posibles de la string donde se puede insertar 1 .
- Inicializar una variable de conteo a 0.
- Recorre la array arr[] desde la izquierda hasta el final. Tan pronto como se encuentre el primer 0, reemplácelo con 1 y aumente el valor de conteo.
- Convierta todos los 0 en -1 que se encuentran en <= K lugares cerca del 1 recién convertido.
- Siga recorriendo la array hasta el final y cada vez que encuentre un 0, repita los pasos 4 y 5 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above problem #include <bits/stdc++.h> using namespace std; // Function to find the // count of 0s to be flipped int count(int k, string s) { int ar[s.length()]; int end = 0; // Loop traversal to mark K // adjacent positions to the right // of already existing 1s. for(int i = 0; i < s.length(); i++) { if (s[i] == '1') { for(int j = i; j < s.length() && j <= i + k; j++) { ar[j] = -1; end = j; } i = end; } } end = 0; // Loop traversal to mark K // adjacent positions to the left // of already existing 1s. for(int i = s.length() - 1; i >= 0; i--) { if (s[i] == '1') { for(int j = i; j >= 0 && j >= i - k; j--) { ar[j] = -1; end = j; } i = end; } } int ans = 0; end = 0; // Loop to count the maximum // number of 0s that will be // replaced by 1s for(int j = 0; j < s.length(); j++) { if (ar[j] == 0) { ans++; for(int g = j; g <= j + k && g < s.length(); g++) { ar[g] = -1; end = g; } j = end - 1; } } return ans; } // Driver code int main() { int K = 2; string s = "000000"; cout << count(K, s) << endl; return 0; } // This code is contributed by divyeshrabadiya07
Java
// Java program for the above problem import java.util.Scanner; // Driver Code public class Check { // Function to find the // count of 0s to be flipped public static int count(int k, String s) { int ar[] = new int[s.length()]; int end = 0; // Loop traversal to mark K // adjacent positions to the right // of already existing 1s. for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == '1') { for (int j = i; j < s.length() && j <= i + k; j++) { ar[j] = -1; end = j; } i = end; } } end = 0; // Loop traversal to mark K // adjacent positions to the left // of already existing 1s. for (int i = s.length() - 1; i >= 0; i--) { if (s.charAt(i) == '1') { for (int j = i; j >= 0 && j >= i - k; j--) { ar[j] = -1; end = j; } i = end; } } int ans = 0; end = 0; // Loop to count the maximum // number of 0s that will be // replaced by 1s for (int j = 0; j < s.length(); j++) { if (ar[j] == 0) { ans++; for (int g = j; g <= j + k && g < s.length(); g++) { ar[g] = -1; end = g; } j = end - 1; } } return ans; } // Driver code public static void main(String[] args) { int K = 2; String s = "000000"; System.out.println(count(K, s)); } }
Python3
# Python3 program for the above problem # Function to find the # count of 0s to be flipped def count(k, s): ar = [0] * len(s) end = 0 # Loop traversal to mark K # adjacent positions to the right # of already existing 1s. for i in range(len(s)): if s[i] == '1': for j in range(i, len(s)): if (j <= i + k): ar[j] = -1 end = j i = end end = 0 # Loop traversal to mark K # adjacent positions to the left # of already existing 1s. for i in range(len(s) - 1, -1, -1): if (s[i] == '1'): for j in range(i, -1, -1): if (j >= i - k): ar[j] = -1 end = j i = end ans = 0 end = 0 # Loop to count the maximum # number of 0s that will be # replaced by 1s for j in range(len(s)): if (ar[j] == 0): ans += 1 for g in range(j, len(s)): if (g <= j + k): ar[g] = -1 end = g j = end - 1 return ans # Driver code K = 2 s = "000000" print(count(K, s)) # This code is contributed by avanitrachhadiya2155
C#
// C# program for the above problem using System; class GFG{ // Function to find the // count of 0s to be flipped public static int count(int k, String s) { int []ar = new int[s.Length]; int end = 0; // Loop traversal to mark K // adjacent positions to the right // of already existing 1s. for(int i = 0; i < s.Length; i++) { if (s[i] == '1') { for(int j = i; j < s.Length && j <= i + k; j++) { ar[j] = -1; end = j; } i = end; } } end = 0; // Loop traversal to mark K // adjacent positions to the left // of already existing 1s. for(int i = s.Length - 1; i >= 0; i--) { if (s[i] == '1') { for(int j = i; j >= 0 && j >= i - k; j--) { ar[j] = -1; end = j; } i = end; } } int ans = 0; end = 0; // Loop to count the maximum // number of 0s that will be // replaced by 1s for(int j = 0; j < s.Length; j++) { if (ar[j] == 0) { ans++; for(int g = j; g <= j + k && g < s.Length; g++) { ar[g] = -1; end = g; } j = end - 1; } } return ans; } // Driver code public static void Main(String[] args) { int K = 2; String s = "000000"; Console.WriteLine(count(K, s)); } } // This code is contributed by amal kumar choubey
Javascript
<script> // Javascript program for the above problem // Function to find the // count of 0s to be flipped function count(k, s) { var ar = Array(s.length).fill(0); var end = 0; var i,j; // Loop traversal to mark K // adjacent positions to the right // of already existing 1s. for(i = 0; i < s.length; i++) { if (s[i] == '1') { for(j = i; j < s.length && j <= i + k; j++) { ar[j] = -1; end = j; } i = end; } } end = 0; // Loop traversal to mark K // adjacent positions to the left // of already existing 1s. for(i = s.length - 1; i >= 0; i--) { if (s[i] == '1') { for(j = i; j >= 0 && j >= i - k; j--) { ar[j] = -1; end = j; } i = end; } } var ans = 0; end = 0; // Loop to count the maximum // number of 0s that will be // replaced by 1s var g; for(j = 0;j < s.length; j++) { if (ar[j] == 0) { ans++; for(g = j; g <= j + k && g < s.length; g++) { ar[g] = -1; end = g; } j = end - 1; } } return ans; } // Driver code var K = 2; var s = "000000"; document.write(count(K, s)); </script>
2
Complejidad temporal: O(N * K)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por abhinavpande y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA