1725. Количество прямоугольников, из которых может образоваться самый большой квадрат

Введение

Геометрия в программировании, о боже… вот и мы. Задачи программирования созданы исключительно для студентов, изучающих информатику, чем я и занялся. Разве они не понимают, что многие люди, вступающие в эту сферу, меняют карьеру? Прошли годы с тех пор, как многие из нас даже не видели геометрическую задачу, не говоря уже о ее решении!

Ну, по крайней мере, это то, что я чувствовал изначально. Часто «математика» вызывает массу негативных переживаний из прошлого. Я заметил это у других людей, которые так изменили свою жизнь. Возможно, вы были плохим учеником, у вас был ужасный учитель математики или вы просто сочли эту тему скучной. Что бы ни случилось в вашем прошлом, я хочу, чтобы вы знали, что мне очень жаль, и я явно был обижен. Математика - это круто, и, возможно, вы не были к ней готовы; подумайте о том, чтобы снова впустить это в свое сердце. Что еще более важно, эта проблема не такая «математика», как кажется. Так что не беспокойтесь, получите этот вызов кода.

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

Подсказка

You are given an array rectangles where rectangles[i] = [li, wi] represents the ith rectangle of length li and width wi.
You can cut the ith rectangle to form a square with a side length of k if both k <= li and k <= wi. For example, if you have a rectangle [4,6], you can cut it to get a square with a side length of at most 4.
Let maxLen be the side length of the largest square you can obtain from any of the given rectangles.
Return the number of rectangles that can make a square with a side length of maxLen.

Мои мысли

Для решения этой проблемы нам нужно будет прочитать подсказку, посмотреть на предоставленные примеры и попытаться понять, о чем нас спрашивает автор. Идея здесь в том, чтобы сформулировать вопрос своими словами. Если мы полностью осознаем проблему, у нас будет гораздо больше шансов создать всеобъемлющее решение для нее.

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

You are given an array rectangles where rectangles[i] = [li, wi] represents the ith rectangle of length li and width wi.

Ладно, спишем с места. Мы видим, что автор использует li и wi, - ширину и длину прямоугольника. Автор упоминает, что размеры прямоугольников (li и wi) содержатся в массиве как пара. Пока имеет смысл.

You can cut the ith rectangle to form a square with a side length of k if both k <= li and k <= wi. For example, if you have a rectangle [4,6], you can cut it to get a square with a side length of at most 4.

Интересно и в то же время запутанно. Автор говорит, что из прямоугольников можно вырезать квадраты. Думайте об этом как о листе цветной бумаги, и мы вырезаем из него квадраты.

Let maxLen be the side length of the largest square you can obtain from any of the given rectangles.

Понимание того, что будет вырезать квадраты из любого прямоугольника из массива прямоугольников. Нам нужны квадраты максимального размера, в зависимости от длины прямоугольника, из которого мы вырезаем. Итак, прямоугольник [i] = [4,6], мы знаем, что 4 - это значение длины «li», поэтому самый большой квадрат будет иметь длину 4.

Return the number of rectangles that can make a square with a side length of maxLen.

Нам понадобится количество квадратов, которые мы можем вырезать из данного прямоугольника. Таким образом, наш результат будет целым числом. Довольно просто.

Подведем итоги того, что мы знаем…

  • Наш вход представляет собой массив прямоугольников, называемых прямоугольниками.
  • li - длина, wi - ширина, хранится парами. Первое число - длина, второе - ширина.
  • Каждый прямоугольник [i] = [li, wi], каждый прямоугольник хранится в массиве под индексом
  • Мы будем вырезать квадраты из любого прямоугольника.
  • Нам нужен максимально большой квадрат, чтобы он соответствовал либо длине, либо ширине.
  • Однако нам нужно будет посмотреть на наименьшее значение (длину или ширину), потому что квадраты всегда имеют одинаковую ширину и длину.
  • Наш результат: максимальное количество квадратов максимальной длины или самых больших квадратов, которые вы можете вырезать из любого прямоугольника.

Давайте разберемся…

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

Давайте начнем с извлечения всех наименьших значений из каждого прямоугольника. Нам понадобятся несколько переменных и цикл. Я подошел к этому шагу так ...

  • Поиск- установлен на пустой объект. Вы сохраните каждое число, и если мы получим дубликаты, мы их посчитаем. Это должна быть пара "ключ-значение"…
  • Ключ: «уникальное наименьшее число (может быть длиной или шириной)»
  • Значение: «ваше количество дубликатов / сколько у вас есть».
  • Младшая переменная - устанавливается в пустой массив. Здесь нужно собрать все самые маленькие значения из прямоугольника досягаемости.
  • Для цикла - он должен перебирать массив прямоугольников.
const countGoodRectangles = function(rectangles) {
    let lookup = {}, low = [];
    
    for(let i = 0; i < rectangles.length; i++) {     
      
    } ...

Мы будем использовать метод массива .push (), чтобы поместить каждое значение прямоугольника в наш нижний массив. Чтобы найти наименьшее значение, воспользуемся методом Math.min (). Поскольку мы не хотим изменять массив прямоугольников, который мы повторяем, мы будем использовать оператор распространения, чтобы сделать клонирование / копию этих данных. Это выглядит так: «… прямоугольники [i]»

... for(let i = 0; i < rectangles.length; i++) {     
         low.push(Math.min(...rectangles[i]))
    } ...

Теперь мы будем использовать троичный оператор для просмотра каждого значения в нашем нижнем массиве. Здесь произойдет новая запись в созданную нами переменную поиска (наша пара "ключ-значение"). Если он уже существует, он упростит счетчик на 1.

... for(let i = 0; i < rectangles.length; i++) {     
         low.push(Math.min(...rectangles[i]))
         lookup[low[i]] ? lookup[low[i]] += 1 : lookup[low[i]] = 1 
    } ...

Итак, теперь у нас есть объект со всей информацией, необходимой для решения этой проблемы. Нам нужно получить доступ к этим данным и вернуть их. Давайте начнем с другого цикла for и переберем наш нижний массив ...

for(let j = 0; j < low.length; j++) {

    }

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

for(let j = 0; j < low.length; j++) {
      let target = Math.max(...low)

    }

Наконец, нам нужно будет использовать оператор if для доступа к этой переменной поиска. Если он существует, он вернет свое значение. ТАДА! Вот счет, который нам нужно было вернуть. Запустите свой тест, затем отправьте его и похлопайте себя по плечу.

for(let j = 0; j < low.length; j++) {
      let target = Math.max(...low)
      
      if (`${target}`in lookup) {
            return lookup[target]
        }   
    }

Решение

const countGoodRectangles = function(rectangles) {
    let lookup = {}, low = [];
    
    for(let i = 0; i < rectangles.length; i++) {     
         low.push(Math.min(...rectangles[i]))
         lookup[low[i]] ? lookup[low[i]] += 1 : lookup[low[i]] = 1 
    }
    
    for(let j = 0; j < low.length; j++) {
      let target = Math.max(...low)
      
      if (`${target}`in lookup) {
            return lookup[target]
        }   
    }
};

Заключение

Нам удалось пройти наш код, одновременно преодолев иррациональный страх перед математикой. По крайней мере, я на это надеюсь ... Не беспокойтесь, если это сбивает с толку. Самое сложное. Итак, вы находитесь в нужном месте, чтобы учиться и расти;)

Давайте сосредоточимся на выводах из этой проблемы. Разбивая вещи на более мелкие части, мы можем лучше их понять. Написание концепций на собственном языке означает, что вы воплотили знания во что-то, что имеет для вас смысл. Используя эти знания, НАМНОГО легче решить проблему.

Если вы ошиблись, вам НЕОБХОДИМО выявить проблемы. Была ли это концептуальная проблема, вроде правил квадрата? Была ли это реальная проблема ... вы забыли синтаксис для .reduce (). Настоящее обучение начинается здесь. Это не обязательно быстро. Часто это похоже на медленную работу, но со временем вы накапливаете эти знания, и внезапно вы чертовски хорошо умеете решать проблемы. Придерживайтесь этого, и удачного программирования!

Ссылки:

LeetCode: leetcode.com