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’.
Ejemplos:
Input : a[] = {1, 0, 0, 1, 1, 0, 1},
k = 1.
Output : 4
Explanation : Here, we should only change 1
zero(0). Maximum possible length we can get
is by changing the 3rd zero in the array,
we get a[] = {1, 0, 0, 1, 1, 1, 1}
Input : a[] = {1, 0, 0, 1, 0, 1, 0, 1, 0, 1},
k = 2.
Output : 5
Output: Here, we can change only 2 zeros.
Maximum possible length we can get is by
changing the 3rd and 4th (or) 4th and 5th
zeros.
Podemos resolver este problema utilizando la técnica de dos punteros . Tomemos un subarreglo [l, r] que contiene como máximo k ceros. Deje que nuestro puntero izquierdo sea l y el puntero derecho sea r. Siempre mantenemos nuestro subsegmento [l, r] para que no contenga más de k ceros moviendo el puntero izquierdo l. Compruebe en cada paso el tamaño máximo (es decir, r-l+1).
C++
// CPP program to find length of longest
// subsegment of all 1's by changing at
// most k 0's
#include <iostream>
using namespace std;
int longestSubSeg(int a[], int n, int k)
{
int cnt0 = 0;
int l = 0;
int max_len = 0;
// i decides current ending point
for (int i = 0; i < n; i++) {
if (a[i] == 0)
cnt0++;
// If there are more 0's move
// left point for current ending
// point.
while (cnt0 > k) {
if (a[l] == 0)
cnt0--;
l++;
}
max_len = max(max_len, i - l + 1);
}
return max_len;
}
// Driver code
int main()
{
int a[] = { 1, 0, 0, 1, 0, 1, 0, 1 };
int k = 2;
int n = sizeof(a) / sizeof(a[0]);
cout << longestSubSeg(a, n, k);
return 0;
}
Java
// Java program to find length of
// longest subsegment of all 1's
// by changing at most k 0's
import java.io.*;
class GFG {
static int longestSubSeg(int a[], int n,
int k)
{
int cnt0 = 0;
int l = 0;
int max_len = 0;
// i decides current ending point
for (int i = 0; i < n; i++) {
if (a[i] == 0)
cnt0++;
// If there are more 0's move
// left point for current ending
// point.
while (cnt0 > k) {
if (a[l] == 0)
cnt0--;
l++;
}
max_len = Math.max(max_len, i - l + 1);
}
return max_len;
}
// Driver code
public static void main (String[] args)
{
int a[] = { 1, 0, 0, 1, 0, 1, 0, 1 };
int k = 2;
int n = a.length;
System.out.println( longestSubSeg(a, n, k));
}
}
// This code is contributed by vt_m
Python3
# Python3 program to find length # of longest subsegment of all 1's # by changing at most k 0's def longestSubSeg(a, n, k): cnt0 = 0 l = 0 max_len = 0; # i decides current ending point for i in range(0, n): if a[i] == 0: cnt0 += 1 # If there are more 0's move # left point for current # ending point. while (cnt0 > k): if a[l] == 0: cnt0 -= 1 l += 1 max_len = max(max_len, i - l + 1); return max_len # Driver code a = [1, 0, 0, 1, 0, 1, 0, 1 ] k = 2 n = len(a) print(longestSubSeg(a, n, k)) # This code is contributed by Smitha Dinesh Semwal
C#
// C# program to find length of
// longest subsegment of all 1's
// by changing at most k 0's
using System;
class GFG {
static int longestSubSeg(int[] a, int n,
int k)
{
int cnt0 = 0;
int l = 0;
int max_len = 0;
// i decides current ending point
for (int i = 0; i < n; i++)
{
if (a[i] == 0)
cnt0++;
// If there are more 0's move
// left point for current ending
// point.
while (cnt0 > k) {
if (a[l] == 0)
cnt0--;
l++;
}
max_len = Math.Max(max_len, i - l + 1);
}
return max_len;
}
// Driver code
public static void Main()
{
int[] a = { 1, 0, 0, 1, 0, 1, 0, 1 };
int k = 2;
int n = a.Length;
Console.WriteLine(longestSubSeg(a, n, k));
}
}
// This code is contributed by vt_m
PHP
<?php
// PHP program to find length of longest
// subsegment of all 1's by changing at
// most k 0's
function longestSubSeg( $a, $n, $k)
{
$cnt0 = 0;
$l = 0;
$max_len = 0;
// i decides current ending point
for($i = 0; $i < $n; $i++)
{
if ($a[$i] == 0)
$cnt0++;
// If there are more 0's move
// left point for current ending
// point.
while ($cnt0 > $k)
{
if ($a[$l] == 0)
$cnt0--;
$l++;
}
$max_len = max($max_len, $i - $l + 1);
}
return $max_len;
}
// Driver code
$a = array(1, 0, 0, 1, 0, 1, 0, 1);
$k = 2;
$n = count($a);
echo longestSubSeg($a, $n, $k);
// This code is contributed by anuj_67.
?>
Javascript
<script>
// JavaScript program to find length of
// longest subsegment of all 1's
// by changing at most k 0's
function longestSubSeg(a, n, k)
{
let cnt0 = 0;
let l = 0;
let max_len = 0;
// i decides current ending point
for (let i = 0; i < n; i++)
{
if (a[i] == 0)
cnt0++;
// If there are more 0's move
// left point for current ending
// point.
while (cnt0 > k) {
if (a[l] == 0)
cnt0--;
l++;
}
max_len = Math.max(max_len, i - l + 1);
}
return max_len;
}
let a = [ 1, 0, 0, 1, 0, 1, 0, 1 ];
let k = 2;
let n = a.length;
document.write(longestSubSeg(a, n, k));
</script>
Producción
5
Hay otro enfoque O(n), en el que podemos mantener un registro del número de 1 que se descartarán si un 0 no se convierte en uno.
A medida que avanzamos hacia la derecha y encontramos más 0 de los permitidos, reducimos un 0 a la izquierda y en ese momento reducimos la cuenta de unos por los 1 adyacentes al cero más a la izquierda que se descarta.
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.ArrayList;
import java.util.List;
public class Solution {
public int solve(int[] binaryList, int conversionLimit) {
List<Integer> listOfOnesCovered = new ArrayList<>();
int oneCount = 0;
for (int number : binaryList) {
if (number == 0) {
listOfOnesCovered.add(oneCount > 0 ? oneCount + 1 : 1);
oneCount = 0;
} else {
++oneCount;
}
}
int totalOnes = 0;
int maxOnes = 0;
int zeroCount = 0;
for (int integer : binaryList) {
++totalOnes;
if (integer == 0) {
if (zeroCount >= conversionLimit) {
totalOnes -= listOfOnesCovered.get(zeroCount - conversionLimit);
}
++zeroCount;
}
maxOnes = Math.max(totalOnes, maxOnes);
}
return maxOnes;
}
public static void main (String[] args){
System.out.println(
new Solution().solve(new int[]{1, 0, 0, 0, 0,1,1, 1}, 2)
);
}
}
C#
// C# code for the above approach
using System;
using System.Collections;
public class Solution {
public int solve(int[] binaryList, int conversionLimit)
{
ArrayList listOfOnesCovered = new ArrayList();
int oneCount = 0;
foreach(int number in binaryList)
{
if (number == 0) {
listOfOnesCovered.Add(
oneCount > 0 ? oneCount + 1 : 1);
oneCount = 0;
}
else {
++oneCount;
}
}
int totalOnes = 0;
int maxOnes = 0;
int zeroCount = 0;
foreach(int integer in binaryList)
{
++totalOnes;
if (integer == 0) {
if (zeroCount >= conversionLimit) {
totalOnes -= (int)listOfOnesCovered
[zeroCount - conversionLimit];
}
++zeroCount;
}
maxOnes = Math.Max(totalOnes, maxOnes);
}
return maxOnes;
}
static public void Main()
{
// Code
Solution s = new Solution();
Console.WriteLine(s.solve(
new int[] { 1, 0, 0, 0, 0, 1, 1, 1 }, 2));
}
}
// This code is contributed by lokeshmvs21.
Producción
5
Publicación traducida automáticamente
Artículo escrito por Harsha_Mogali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA