Матрица и хеш-таблица
Сложность: средняя
Коэффициент принятия: 46,5 %
Проблема
Перед вами кирпичная стена. Стена прямоугольная и имеет несколько рядов кирпичей. Кирпичи имеют одинаковую высоту, но разную ширину. Вы хотите провести вертикальную линию от верха к низу и пересечь наименьшие кирпичи.
Кирпичная стена представлена списком рядов. Каждая строка представляет собой список целых чисел, представляющих ширину каждого кирпича в этой строке слева направо.
Если ваша линия проходит через край кирпича, то кирпич не считается пересеченным. Вам нужно выяснить, как нарисовать линию, чтобы пересечь наименьшее количество кирпичей и вернуть количество пересеченных кирпичей.
Вы не можете провести линию только вдоль одного из двух вертикальных краев стены, и в этом случае линия, очевидно, не будет пересекать кирпичи.
Мысли:
Эта проблема довольно прямолинейна.
Первые две вещи, которые нам нужно знать, это ширина и высота стены. Из ширины и высоты мы могли бы сначала создать матрицу, подобную этой:
Каждый «0» означает, что пространство заблокировано кирпичом.
Мы хотим, чтобы матрица стала примерно такой:
где 1 означает пересечение между двумя кирпичами (или не пересечение).
Итак, что мы делаем, так это находим максимальное количество сложенных единиц среди столбцов.
Полный метод выглядит так:
Это работоспособное решение, но это также и TLE.
Сложность этого решения в основном составляет O( n² ), но сначала мы создаем матрицу, а также есть другие циклы for, из-за чего время выполнения превышает ограничение по времени.
Кажется, что матрица для этого не подходит, поэтому давайте сделаем это в виде хеш-таблицы.
В строке 3 мы сначала создаем словарь, чтобы отметить, сколько кирпичей НЕ пересекается в каждом столбце,
Затем мы проходим через кирпичную стену, мы знаем, что в колонне не будет кирпича, когда колонна находится между кирпичами. Замените переменную mostCrossed во время цикла. Сложность этого решения тоже O( n² ), но с помощью хеш-таблицы, видимо, быстрее.
