554. Brick Wall

LeetCode medium original: C# #array #csharp #leetcode #math #medium

Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.

LeetCode Static

Перед вами находится прямоугольная кирпичная стена с n рядами кирпичей. В i-м ряду находится несколько кирпичей одинаковой высоты (то есть один юнит), но они могут быть разной ширины. Общая ширина каждого ряда одинакова.

Нарисуйте вертикальную линию от верха до низа, пересекающую наименьшее количество кирпичей. Если ваша линия проходит по краю кирпича, то кирпич не считается пересеченным. Вы не можете нарисовать линию прямо по одному из двух вертикальных краев стены, так как в этом случае линия очевидно не пересечет ни одного кирпича.

Дан двумерный mảng wall, содержащий информацию о стене, return минимальное количество пересеченных кирпичей после проведения такой вертикальной линии.

Ví dụ:

Input: wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]

Output: 2

C# lời giải

đã khớp/gốc

public class Solution {
    public int LeastBricks(IList<IList<int>> wall) {
        int[] pos = new int[wall.Count];
        int sum = 0, res = int.MaxValue;
        foreach (int el in wall[0])
            sum += el;
        while (sum != 0) {
            int count = 0;
            for (int i = 0; i < wall.Count; i++) {
                if (wall[i][pos[i]] != 0)
                    count++;
                else
                    pos[i]++;
                wall[i][pos[i]]--;
            }
            sum--;
            res = Math.Min(res, count);
        }
        return res;
    }
}

C++ lời giải

bản nháp tự động, xem lại trước khi gửi

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int LeastBricks(IList<vector<int>> wall) {
        vector<int>& pos = new int[wall.size()];
        int sum = 0, res = int.MaxValue;
        foreach (int el in wall[0])
            sum += el;
        while (sum != 0) {
            int count = 0;
            for (int i = 0; i < wall.size(); i++) {
                if (wall[i][pos[i]] != 0)
                    count++;
                else
                    pos[i]++;
                wall[i][pos[i]]--;
            }
            sum--;
            res = min(res, count);
        }
        return res;
    }
}

Java lời giải

đã khớp/gốc

public class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        int[] pos = new int[wall.size()];
        int sum = 0;
        int res = Integer.MAX_VALUE;
        
        for (int el : wall.get(0)) {
            sum += el;
        }
        
        while (sum != 0) {
            int count = 0;
            for (int i = 0; i < wall.size(); i++) {
                List<Integer> row = wall.get(i);
                if (row.get(pos[i]) != 0) {
                    count++;
                } else {
                    pos[i]++;
                }
                row.set(pos[i], row.get(pos[i]) - 1);
            }
            sum--;
            res = Math.min(res, count);
        }
        
        return res;
    }
}

JavaScript lời giải

đã khớp/gốc

var leastBricks = function(wall) {
    let pos = new Array(wall.length).fill(0);
    let sum = wall[0].reduce((a, b) => a + b, 0);
    let res = Infinity;

    while (sum !== 0) {
        let count = 0;
        for (let i = 0; i < wall.length; i++) {
            if (wall[i][pos[i]] !== 0) {
                count++;
            } else {
                pos[i]++;
            }
            wall[i][pos[i]]--;
        }
        sum--;
        res = Math.min(res, count);
    }

    return res;
};

Python lời giải

đã khớp/gốc

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        pos = [0] * len(wall)
        res = float('inf')
        sum_width = sum(wall[0])
        
        while sum_width != 0:
            count = 0
            for i in range(len(wall)):
                if wall[i][pos[i]] != 0:
                    count += 1
                else:
                    pos[i] += 1
                wall[i][pos[i]] -= 1
            sum_width -= 1
            res = min(res, count)
        
        return res

Go lời giải

đã khớp/gốc

package main

import (
    "math"
)

func leastBricks(wall [][]int) int {
    pos := make([]int, len(wall))
    sum := 0
    res := math.MaxInt32

    for _, el := range wall[0] {
        sum += el
    }

    for sum != 0 {
        count := 0
        for i := 0; i < len(wall); i++ {
            if wall[i][pos[i]] != 0 {
                count++
            } else {
                pos[i]++
            }
            wall[i][pos[i]]--
        }
        sum--
        res = min(res, count)
    }

    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Algorithm

Определите общую ширину стены, сложив ширины кирпичей в первом ряду. Создайте mảng pos, где pos[i] указывает на текущую позицию в i-ом ряду.

Пройдите по каждой возможной позиции для вертикальной линии (от 1 до общей ширины стены - 1). Для каждой позиции обновите mảng pos, проверяя, пересекает ли линия границу кирпича. Если пересекает, увеличьте значение pos[i].

Подсчитайте количество кирпичей, которые пересечет вертикальная линия для каждой возможной позиции, обновляя счетчик. Выберите минимальное количество пересеченных кирпичей из всех возможных позиций для вертикальной линии.

😎

Vacancies for this task

việc làm đang hoạt động with overlapping task tags are đã hiển thị.

Tất cả việc làm

Chưa có việc làm đang hoạt động.