Конкурс литкода 297

Проблема 1

Рассчитать сумму уплаченных налогов

Вам дан 0-индексированный двумерный целочисленный массив brackets, где brackets[i] = [upperi, percenti] означает, что налоговая группа ith имеет верхнюю границу upperi и облагается налогом по ставке percenti. Скобки отсортированы по верхней границе (например, upperi-1 < upperi вместо 0 < i < brackets.length).

Налог рассчитывается следующим образом:

Первые заработанные upper0 долларов облагаются налогом по ставке percent0.

Следующие заработанные upper1 - upper0 долларов облагаются налогом по ставке percent1.

Следующие заработанные upper2 - upper1 долларов облагаются налогом по ставке percent2.

И так далее.

Вам дано целое число income, представляющее сумму денег, которую вы заработали. Верните сумму денег, которую вы должны заплатить в виде налогов. Будут приняты ответы в пределах 10-5 от фактического ответа.

Подход

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

Решение

Временная сложность: O(n)

Космическая сложность: O(1)

Проблема 2

Минимальная стоимость пути в сетке

Вам дана 0-индексированная m x n целочисленная матрица grid, состоящая из различных целых чисел от 0 до m * n - 1. Вы можете перемещаться в этой матрице из ячейки в любую другую ячейку в следующей строке. То есть, если вы находитесь в ячейке (x, y) такой, что x < m - 1, вы можете перейти в любую из ячеек (x + 1, 0), (x + 1, 1), ..., (x + 1, n - 1). Обратите внимание, что невозможно перейти из ячеек в последней строке.

Каждое возможное перемещение имеет стоимость, заданную индексированным 0 двумерным массивом moveCost размера (m * n) x n, где moveCost[i][j] – стоимость перемещения из ячейки со значением i в ячейку в столбце j следующей строки. Стоимость перемещения из ячеек в последней строке grid можно не учитывать.

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

Подход

Скажем, есть только одна строка, тогда результат будет простым, выбрав минимальное значение в сетке.

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

Для любой ячейки сетки вычисляем минимальную стоимость ее достижения. Мы повторяем это для каждой ячейки сетки, кроме первой строки. Чтобы избежать повторных вычислений, мы поддерживаем двумерную сетку для кэширования наших результатов. Минимальное значение в последней строке 2D сетки будет нашим результатом.

Решение

Временная сложность: O(m * n²)

Космическая сложность: O(m * n)

Проблема 3

Справедливое распространение файлов cookie

Вам дан массив целых чисел cookies, где cookies[i] обозначает количество печенья в пакете ith. Вам также дается целое число k, обозначающее количество детей, которым нужно раздать все пакеты с печеньем. Все печенья в одном пакете должны достаться одному и тому же ребенку и не могут быть разделены.

Несправедливость распределения определяется как максимальное общее количество файлов cookie, полученных одним дочерним элементом в распределении.

Возвращает минимальную несправедливость всех распределений.

Подход

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

Примечание. Для Python простой возврат будет TLE. Следовательно, необходимо применить привязку к ветвлению. В этом случае мы не переходим, когда несправедливость превышает ранее вычисленный результат. Идти в конец ветки смысла не будет, так как несправедливость в распределении уже превышает ранее вычисленный результат.

Решение

Временная сложность: O(k^n)

Космическая сложность: O(k)

Проблема 4

Именование компании

Вам дан массив строк ideas, который представляет собой список имен, которые будут использоваться в процессе присвоения названия компании. Процесс присвоения имени компании выглядит следующим образом:

Выберите 2 разных имени из ideas, назовите их ideaA и ideaB.

Поменяйте местами первые буквы ideaA и ideaB друг с другом.

Если оба новых имени не найдены в исходном ideas, то имя ideaA ideaB (объединение ideaA и ideaB, разделенных пробелом) является допустимым названием компании. .

В противном случае это недопустимое имя.

Возвращает количество различных допустимых названий для компании.

Подход

Мы группируем все имена по их начальным символам. Имена, начинающиеся с разных символов, могут приниматься во внимание, только если их тела не совпадают.

Например, «кофе» и «пончики» имеют разные начальные символы и разные тела «c-кофе» и «d-onuts». Поменяв местами начальные символы, вы получите два разных слова «c-onuts» и «d-offee». Принимая во внимание, что «кофе» и «ириска» имеют разные начальные символы, но одинаковые тела «c-offee» и «t-offee». Замена начальных символов не приведет к созданию разных слов.

Мы можем использовать set и операцию difference, чтобы устранить это.

Решение

Временная сложность: O(m²), где m — максимальное количество тел под одним и тем же начальным символом. Эта временная сложность в основном связана с операцией установки разности.

Космическая сложность: O(n)

Надеюсь, вам понравился этот пост.

Если вы найдете это полезным, пожалуйста, поделитесь, и хлопки очень ценятся! 😄

Не стесняйтесь задавать свои вопросы в разделе комментариев!.