Решение: кирпичная стена

Решения LeetCode (161 часть серии)

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашел его полезным, Пожалуйста, как Этот пост и/или УПОТАТЬ Мое решение пост на форумах LeetCode Отказ

Проблема лецкода # 554 (средний): Кирпичная стена

Описание:

( Перейти к : Идея решения Код : JavaScript | Python |. Java |. C ++

Перед вами кирпичная стена. Стена прямоугольная и имеет несколько рядов кирпичей. Кирпичи имеют одинаковую высоту, но другую ширину. Вы хотите нарисовать вертикальную линию от верх к снизу и пересечь минимум кирпичи.

Кирпичная стена представлена списком строк. Каждая строка представляет собой список целых чисел, представляющих ширину каждого кирпича в этой строке слева направо.

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

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

Примеры:

Ограничения:

• Сумма ширины кирпича в разных рядах одинакова и не превышает Int_max Отказ
• Количество кирпичей в каждой строке находится в пределах диапазона [1,10,000] . Высота стены находится в диапазоне [1,10,000] . Общее количество кирпичей стены не превышает 20 000 Отказ

Идея:

( Перейти к : Описание проблемы Код : JavaScript | Python |. Java |. C ++

Если цель здесь – найти, где линия будет пересекать наименьшее количество кирпичей, то мы могли бы также сказать, что цель – найти, где самые кирпичные края линией. Мы можем рассмотреть края, когда произойдут при индексе, представляющем текущий прохождение всего предыдущих элементов данной строки стены. Например, если ряд определяется как [1,2,2,1] Тогда появляются внутренние края в [1,1 + 2,1 + 2 + 2] или [1,3,5] .

Если теперь мы узнаем, как найти края, то мы остались с выяснением, какой индекс имеет самую высокую частоту ребер, которые естественным образом требуют для Частотная карта.

Итак, мы можем проиграть через каждый ряд в стена , Держите прогонскую сумму текущей строки ( rowsum ), а затем обновите частоту указателя каждого края на нашей карте частоты ( Freq ).

Как только мы закончим наполнение Freq , нам просто нужно повторить его, чтобы найти наибольшее значение ( Best ), который представляет количество ребер, выровненных на одном индексе. Однако наш фактический ответ – количество кирпичей, а не краев, поэтому мы должны вернуть Общее количество рядов минус Лучший Отказ

Реализация:

Для JavaScript это больше исполнителю, чтобы проиграть через готовую Freq ищу Лучший результат

В Python легче запустить Макс () непосредственно на Freq Отказ

Для Java и C ++ быстрее отслеживать Лучший Как мы добавляем значения в Freq Отказ

Для Java, это также странно более исполнителя для извлечения ряд обработка к функции помощника.

Код JavaScript:

( Перейти к : Описание проблемы Идея решения

var leastBricks = function(wall) {
    let freq = new Map(), best = 0
    for (let i = 0; i < wall.length; i++) {
        let row = wall[i], rowSum = row[0]
        for (let j = 1; j < row.length; j++) {
            freq.set(rowSum, (freq.get(rowSum) || 0) + 1)
            rowSum += row[j]
        } 
    }
    for (let [k,v] of freq)
        if (v > best) best = v
    return wall.length - best
};

Код Python:

( Перейти к : Описание проблемы Идея решения

class Solution:
    def leastBricks(self, wall: List[List[int]]) -> int:
        freq = defaultdict(int)
        for row in wall:
            rowSum = row[0]
            for j in range(1, len(row)):
                freq[rowSum] += 1
                rowSum += row[j]
        return len(wall) - max(freq.values() or [0])

Java код:

( Перейти к : Описание проблемы Идея решения

class Solution {
    int best = 0;
    Map freq = new HashMap<>();
    public int leastBricks(List> wall) {
        for (int i = 0; i < wall.size(); i++)
            processRow(wall.get(i));
        return wall.size() - best;
    }
    public void processRow(List row) {
        int rowSum = row.get(0);
        for (int j = 1; j < row.size(); j++) {
            int f = freq.getOrDefault(rowSum, 0) + 1;
            freq.put(rowSum, f);
            if (f > best) best = f;
            rowSum += row.get(j);
        } 
    }
}

C ++ код:

( Перейти к : Описание проблемы Идея решения

class Solution {
public:
    int leastBricks(vector>& wall) {
        unordered_map freq;
        int best = 0;
        for (int i = 0; i < wall.size(); i++) {
            int rowSum = wall[i][0];
            for (int j = 1; j < wall[i].size(); j++) {
                freq[rowSum]++;
                best = max(best, freq[rowSum]);
                rowSum += wall[i][j];
            };
        };
        return wall.size() - best;
    };
};

Решения LeetCode (161 часть серии)

Оригинал: “https://dev.to/seanpgallivan/solution-brick-wall-4jld”