Dada una array 2D que representa el ancho y el nivel de los mosaicos de igual longitud, con cada nivel del mismo ancho total, la tarea es encontrar el número mínimo de mosaicos que se pueden cortar con un solo golpe vertical de espada que pasa por todos los niveles del losas.
Ejemplos:
Entrada: tilesStack[][] = { { 2, 3 }, { 3, 2 }, { 1, 1, 1, 2 }, { 1, 1, 1, 1, 1 } }
Salida: 1
Explicación:
El mínimo número de fichas que se pueden cortar es igual a 1
Entrada: tilesStack[][] = { { 1, 1 }, { 1, 1 } }
Salida: 0
Planteamiento: La idea es encontrar el número máximo de huecos para que si se dibuja una línea vertical que pase por esos puntos, corte el número mínimo de baldosas. Siga los pasos a continuación para resolver el problema:
- Atraviesa cada fila de la array 2D tilesStack[][] . Para cada i -ésima fila, Mapee su suma de prefijos , que representa la distancia de los espacios a partir del mosaico más a la izquierda y almacene la frecuencia de la suma de prefijos de cada fila usando Map .
- Encuentre la frecuencia más grande de la suma de prefijos (de la distancia de los espacios), digamos X .
- Finalmente, imprime el valor de (length(tilesStack) – X) , que representa la cantidad mínima de mosaicos que se cortan al dibujar una línea vertical.
A continuación se muestra la implementación de este enfoque.
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to count the minimum number
// of tiles that gets cut by a single
// vertical strike of a sword
void cutTiles(vector<vector<int>> tilesStack)
{
// Map prefix sum of each row
// of tilesStack
map<int, int> gaps;
// Traverse each row of the tiles
for(vector<int> tiles:tilesStack)
{
// Stores distance of gap from
// left of each row
int totWidth = 0;
// Excluding the last gap as it will
// be the edge of the level
for(int i = 0; i < tiles.size() - 1; i++)
{
// Update totWidth
totWidth += tiles[i];
// If gap is already found at
// this points in previous levels
gaps[totWidth]++;
}
}
// Stores maximum number of
// gap from left
int X = 0;
for(auto x : gaps)
{
X = max(x.second, X);
}
cout << tilesStack.size() - X;
}
// Driver code
int main()
{
vector<vector<int>> tilesStack(4);
tilesStack[0].push_back(2);
tilesStack[0].push_back(3);
tilesStack[1].push_back(3);
tilesStack[1].push_back(2);
tilesStack[2].push_back(1);
tilesStack[2].push_back(1);
tilesStack[2].push_back(1);
tilesStack[2].push_back(2);
tilesStack[3].push_back(1);
tilesStack[3].push_back(1);
tilesStack[3].push_back(1);
tilesStack[3].push_back(1);
tilesStack[3].push_back(1);
// Function Call
cutTiles(tilesStack);
}
// This code is contributed by rutvik_56.
Java
// Java program for the above approach
import java.util.*;
public class GFG
{
// Function to count the minimum number
// of tiles that gets cut by a single
// vertical strike of a sword
static void cutTiles(Vector<Vector<Integer>> tilesStack)
{
// Map prefix sum of each row
// of tilesStack
HashMap<Integer, Integer> gaps = new HashMap<>();
// Traverse each row of the tiles
for(Vector<Integer> tiles : tilesStack)
{
// Stores distance of gap from
// left of each row
int totWidth = 0;
// Excluding the last gap as it will
// be the edge of the level
for(int i = 0; i < tiles.size() - 1; i++)
{
// Update totWidth
totWidth += tiles.get(i);
// If gap is already found at
// this points in previous levels
if(gaps.containsKey(totWidth))
{
gaps.put(totWidth, gaps.get(totWidth) + 1);
}
else{
gaps.put(totWidth, 1);
}
}
}
// Stores maximum number of
// gap from left
int X = 0;
for (Map.Entry Key : gaps.entrySet())
{
X = Math.max((int)Key.getValue(),X);
}
System.out.print(tilesStack.size() - X);
}
// Driver code
public static void main(String[] args)
{
Vector<Vector<Integer>> tilesStack = new Vector<Vector<Integer>>();
tilesStack.add(new Vector<Integer>());
tilesStack.get(0).add(2);
tilesStack.get(0).add(3);
tilesStack.add(new Vector<Integer>());
tilesStack.get(1).add(3);
tilesStack.get(1).add(2);
tilesStack.add(new Vector<Integer>());
tilesStack.get(2).add(1);
tilesStack.get(2).add(1);
tilesStack.get(2).add(1);
tilesStack.get(2).add(2);
tilesStack.add(new Vector<Integer>());
tilesStack.get(3).add(1);
tilesStack.get(3).add(1);
tilesStack.get(3).add(1);
tilesStack.get(3).add(1);
tilesStack.get(3).add(1);
// Function Call
cutTiles(tilesStack);
}
}
// This code is contributed by divyeshrabadiya07.
Python
# Python3 program for the above approach
# Function to count the minimum number
# of tiles that gets cut by a single
# vertical strike of a sword
def cutTiles(tilesStack):
# Map prefix sum of each row
# of tilesStack
gaps = {}
# Handling the case when
# map will be empty
gaps[-1] = 0
# Traverse each row of the tiles
for tiles in tilesStack:
# Stores distance of gap from
# left of each row
totWidth = 0
# Excluding the last gap as it will
# be the edge of the level
for tile in tiles[:-1]:
# Update totWidth
totWidth += tile
# If gap is already found at
# this points in previous levels
if totWidth in gaps:
gaps[totWidth] += 1
else:
gaps[totWidth] = 1
# Stores maximum number of
# gap from left
X = max(list(gaps.values()))
print(len(tilesStack) - X)
# Driver Code
if __name__ == '__main__':
tilesStack = [[2, 3], [3, 2], [1, 1, 1, 2],
[1, 1, 1, 1, 1]]
# Function Call
cutTiles(tilesStack)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to count the minimum number
// of tiles that gets cut by a single
// vertical strike of a sword
static void cutTiles(List<List<int>> tilesStack)
{
// Map prefix sum of each row
// of tilesStack
Dictionary<int, int> gaps = new Dictionary<int, int>();
// Traverse each row of the tiles
foreach(List<int> tiles in tilesStack)
{
// Stores distance of gap from
// left of each row
int totWidth = 0;
// Excluding the last gap as it will
// be the edge of the level
for(int i = 0; i < tiles.Count - 1; i++)
{
// Update totWidth
totWidth += tiles[i];
// If gap is already found at
// this points in previous levels
if(gaps.ContainsKey(totWidth))
{
gaps[totWidth] += 1;
}
else{
gaps[totWidth] = 1;
}
}
}
// Stores maximum number of
// gap from left
int X = 0;
foreach(KeyValuePair<int, int> Key in gaps)
{
X = Math.Max(Key.Value,X);
}
Console.WriteLine(tilesStack.Count - X);
}
static void Main() {
List<List<int>> tilesStack = new List<List<int>>();
tilesStack.Add(new List<int>());
tilesStack[0].Add(2);
tilesStack[0].Add(3);
tilesStack.Add(new List<int>());
tilesStack[1].Add(3);
tilesStack[1].Add(2);
tilesStack.Add(new List<int>());
tilesStack[2].Add(1);
tilesStack[2].Add(1);
tilesStack[2].Add(1);
tilesStack[2].Add(2);
tilesStack.Add(new List<int>());
tilesStack[3].Add(1);
tilesStack[3].Add(1);
tilesStack[3].Add(1);
tilesStack[3].Add(1);
tilesStack[3].Add(1);
// Function Call
cutTiles(tilesStack);
}
}
// This code is contributed by divyeshrbadiya07.
Javascript
<script>
// Javascript program for the above approach
// Function to count the minimum number
// of tiles that gets cut by a single
// vertical strike of a sword
function cutTiles(tilesStack)
{
// Map prefix sum of each row
// of tilesStack
let gaps = new Map();
// Traverse each row of the tiles
for(let tiles = 0; tiles < tilesStack.length; tiles++)
{
// Stores distance of gap from
// left of each row
let totWidth = 0;
// Excluding the last gap as it will
// be the edge of the level
for(let i = 0; i < tilesStack[tiles].length - 1; i++)
{
// Update totWidth
totWidth += tilesStack[tiles][i];
// If gap is already found at
// this points in previous levels
if(gaps.has(totWidth))
{
gaps.set(totWidth, gaps.get(totWidth) + 1);
}
else{
gaps.set(totWidth, 1);
}
}
}
// Stores maximum number of
// gap from left
let X = 0;
gaps.forEach((values,keys)=>
{
X = Math.max(values,X);
})
document.write(tilesStack.length - X);
}
let tilesStack = new Array(4);
for(let i = 0; i < tilesStack.length; i++)
{
tilesStack[i] = [];
}
tilesStack[0].push(2);
tilesStack[0].push(3);
tilesStack[1].push(3);
tilesStack[1].push(2);
tilesStack[2].push(1);
tilesStack[2].push(1);
tilesStack[2].push(1);
tilesStack[2].push(2);
tilesStack[3].push(1);
tilesStack[3].push(1);
tilesStack[3].push(1);
tilesStack[3].push(1);
tilesStack[3].push(1);
// Function Call
cutTiles(tilesStack);
</script>
Producción:
1
Complejidad de Tiempo: O(N * M), donde N es el conteo total de niveles y M es el ancho de cada nivel
Espacio Auxiliar: O(M)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA