Минимальное количество кирпичей, которые можно пересечь

Опубликовано: 22 Сентября, 2022

Учитывая двумерный массив arr[][] , представляющий ширину кирпичей одинаковой высоты, присутствующих на стене, задача состоит в том, чтобы найти минимальное количество кирпичей, которые можно пересечь, проведя прямую линию сверху вниз. стена.
Примечание. Говорят, что линия пересекает кирпич, если она проходит через кирпич, и не пересекается, если касается границы кирпича.

Примеры:

Input: arr[][] = {{1, 2, 2, 1}, {3, 1, 2}, {1, 3, 2}, {2, 4}, {3, 1, 2}, {1, 3, 1, 1}}
Output: 2
Explanation: Considering the top left corner of the 2D array as the origin, the line is drawn at the coordinate x = 4 on the x-axis, such that it crosses the bricks on the 1st and 4th level, resulting in the minimum number of bricks crossed.
Input: arr[][] = {{1, 1, 1}}
Output: 0
Explanation: The line can be drawn at x = 1 or x = 2 coordinate on the x-axis such that it does not cross any brick resulting in the minimum number of bricks crossed.

Наивный подход: самый простой подход состоит в том, чтобы рассмотреть прямые линии, которые можно провести по каждой возможной координате по оси x вдоль ширины стены, учитывая, что x = 0 в верхнем левом углу стены. Затем подсчитайте количество кирпичей, вставленных в каждый ящик, и выведите минимальное полученное количество.

Сложность по времени: O(N * M), где N — общее количество кирпичей, а M — общая ширина стены.
Вспомогательное пространство: O(1)

Подход: Чтобы оптимизировать описанный выше подход, идея состоит в том, чтобы сохранить количество кирпичей, заканчивающихся на определенной ширине по оси X, в хэш-карте, а затем найти строку, где заканчивается наибольшее количество кирпичей. Получив это значение, вычтите его из общей высоты стены, чтобы получить минимальное количество пересеченных кирпичей.

Выполните следующие шаги, чтобы решить проблему:

Инициализируйте хэш-карту M , чтобы хранить количество кирпичей, заканчивающихся на определенной ширине по оси x.
Пройдите массив, используя переменную i для хранения индекса строки
- Инициализируйте переменную, ширину как 0 , чтобы сохранить конечную позицию.
- Сохраните размер текущей строки в переменной X .
- Итерация в диапазоне [0, X-2], используя переменную j
  - Увеличьте значение ширины на arr[i][j] и увеличьте значение ширины в M на 1 .
  - Кроме того, отслеживайте наибольшее количество кирпичей, заканчивающихся на определенной ширине, и сохраняйте их в переменной res .
Вычтите значение res из общей высоты стены и сохраните его в переменной ans .
Выведите значение ans в качестве результата.

Ниже приведена реализация вышеуказанного подхода:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find a line across a wall such
// that it intersects minimum number of bricks
void leastBricks(vector<vector<int> > wall)
{
    // Declare a hashmap
    unordered_map<int, int> map;
 
    // Store the maximum number of
    // brick ending a point on x-axis
    int res = 0;
 
    // Iterate over all the rows
    for (vector<int> list : wall) {
 
        // Initialize width as 0
        int width = 0;
 
        // Iterate over individual bricks
        for (int i = 0; i < list.size() - 1; i++) {
 
            // Add the width of the current
            // brick to the total width
            width += list[i];
 
            // Increment number of bricks
            // ending at this width position
            map[width]++;
 
            // Update the variable, res
            res = max(res, map[width]);
        }
    }
 
    // Print the answer
    cout << wall.size() - res;
}
 
// Driver Code
int main()
{
    // Given Input
    vector<vector<int> > arr{
        { 1, 2, 2, 1 }, { 3, 1, 2 },
        { 1, 3, 2 }, { 2, 4 },
        { 3, 1, 2 }, { 1, 3, 1, 1 }
    };
 
    // Function Call
    leastBricks(arr);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
 
public class GFG
{
 
    // Function to find a line across a wall such
    // that it intersects minimum number of bricks
    static void leastBricks(ArrayList<ArrayList<Integer> > wall)
    {
       
        // Declare a hashmap
        HashMap<Integer, Integer> map = new HashMap<>();
 
        // Store the maximum number of
        // brick ending a point on x-axis
        int res = 0;
 
        // Iterate over all the rows
        for (ArrayList<Integer> list : wall) {
 
            // Initialize width as 0
            int width = 0;
 
            // Iterate over individual bricks
            for (int i = 0; i < list.size() - 1; i++) {
 
                // Add the width of the current
                // brick to the total width
                width += list.get(i);
 
                // Increment number of bricks
                // ending at this width position
                map.put(width,
                        map.getOrDefault(width, 0) + 1);
 
                // Update the variable, res
                res = Math.max(res,
                               map.getOrDefault(width, 0));
            }
        }
 
        // Print the answer
        System.out.println(wall.size() - res);
    }
 
    // Driver code
    public static void main(String[] args)
    {
      // Given Input
        ArrayList<ArrayList<Integer> > arr
            = new ArrayList<>();
        arr.add(new ArrayList<>(Arrays.asList(1, 2, 2, 1)));
        arr.add(new ArrayList<>(Arrays.asList(3, 1, 2)));
        arr.add(new ArrayList<>(Arrays.asList(1, 3, 2)));
        arr.add(new ArrayList<>(Arrays.asList(2, 4)));
        arr.add(new ArrayList<>(Arrays.asList(3, 1, 2)));
        arr.add(new ArrayList<>(Arrays.asList(1, 3, 1, 1)));
 
        // Function Call
        leastBricks(arr);
    }
}
 
// This code is contributed by abhinavjain194

Python3

# Python 3 program for the above approach
from collections import defaultdict
 
# Function to find a line across a wall such
# that it intersects minimum number of bricks
def leastBricks(wall):
 
    # Declare a hashmap
    map = defaultdict(int)
 
    # Store the maximum number of
    # brick ending a point on x-axis
    res = 0
 
    # Iterate over all the rows
    for list in wall:
 
        # Initialize width as 0
        width = 0
 
        # Iterate over individual bricks
        for i in range(len(list) - 1):
 
            # Add the width of the current
            # brick to the total width
            width += list[i]
 
            # Increment number of bricks
            # ending at this width position
            map[width] += 1
 
            # Update the variable, res
            res = max(res, map[width])
 
    # Print the answer
    print(len(wall) - res)
 
 
# Driver Code
if __name__ == "__main__":
 
    # Given Input
    arr = [
        [1, 2, 2, 1], [3, 1, 2],
        [1, 3, 2], [2, 4],
        [3, 1, 2], [1, 3, 1, 1]
    ]
 
    # Function Call
    leastBricks(arr)
 
    # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
  
// Function to find a line across a wall such
// that it intersects minimum number of bricks
static void leastBricks(List<List<int>> wall)
{
     
    // Declare a hashmap
    Dictionary<int,
               int> map = new Dictionary<int,
                                         int>();
 
    // Store the maximum number of
    // brick ending a point on x-axis
    int res = 0;
 
    // Iterate over all the rows
    foreach (List<int> subList in wall)
    {
         
        // Initialize width as 0
        int width = 0;
        for(int i = 0; i < subList.Count - 1; i++)
        {
             
            // Add the width of the current
            // brick to the total width
            width += subList[i];
             
            // Increment number of bricks
            // ending at this width position
            if (map.ContainsKey(width))
                map[width]++;
            else
                map.Add(width, 1);
             
            // Update the variable, res
            res = Math.Max(res, map[width]);
        }
    }
 
    // Print the answer
    Console.Write(wall.Count-res);
}
 
// Driver Code
public static void Main()
{
     
    // Given Input
    List<List<int>> myList = new List<List<int>>();
    myList.Add(new List<int>{ 1, 2, 2, 1 });
    myList.Add(new List<int>{ 3, 1, 2 });
    myList.Add(new List<int>{ 1, 3, 2 });
    myList.Add(new List<int>{ 2, 4 });
    myList.Add(new List<int>{ 3, 1, 2 });
    myList.Add(new List<int>{ 1, 3, 1, 1 });
     
    // Function Call
    leastBricks(myList);
}
}
 
// This code is contributed by bgangwar59

Javascript

<script>
 
// JavaScript program for the above approach
 
 
// Function to find a line across a wall such
// that it intersects minimum number of bricks
function leastBricks(wall) {
    // Declare a hashmap
    let map = new Map();
 
    // Store the maximum number of
    // brick ending a point on x-axis
    let res = 0;
 
    // Iterate over all the rows
    for (let list of wall) {
 
        // Initialize width as 0
        let width = 0;
 
        // Iterate over individual bricks
        for (let i = 0; i < list.length - 1; i++) {
 
            // Add the width of the current
            // brick to the total width
            width += list[i];
 
            // Increment number of bricks
            // ending at this width position
            if (map.has(width)) {
                map.set(width, map.get(width) + 1);
            } else {
                map.set(width, 1)
            }
 
            // Update the variable, res
            res = Math.max(res, map.get(width));
        }
    }
 
    // Print the answer
    document.write(wall.length - res);
}
 
// Driver Code
 
// Given Input
let arr = [
    [1, 2, 2, 1], [3, 1, 2],
    [1, 3, 2], [2, 4],
    [3, 1, 2], [1, 3, 1, 1]
];
 
// Function Call
leastBricks(arr);
 
</script>

Сложность по времени: O(N), где N — общее количество кирпичей на стене.
Вспомогательное пространство: O(M), где M — общая ширина стены.

Mathematical

Минимальное количество кирпичей, которые можно пересечь

C++

Java

Python3

C#

Javascript

РЕКОМЕНДУЕМЫЕ СТАТЬИ