Мы Competitive Programming London, мы встречаемся раз в неделю, чтобы попрактиковаться в некоторых алгоритмических задачах из Codeforces, Hackerrank, Leetcode и других задачах. Каждый раз, когда мы встречаемся, мы работаем над несколькими проблемами в парах, а затем обсуждаем решения друг друга в целом ближе к концу. Для этого мероприятия мы решили три задачи:
Этот пост подытожит наши темы для обсуждения и то, как мы подошли к решению каждой проблемы.
Отличительные цифры
ссылка на проблему: https://codeforces.com/contest/1228/problem/A
В этой задаче нам нужно найти любое число с различиями между диапазоном a
и b
. Ограничения задачи заключаются в том, что и a
, и b
находятся в диапазоне от 0 до 10⁵. Кроме того, b
всегда больше, чем a
. Как и в большинстве конкурентных проблем, обычно разумно посмотреть, будет ли достаточно решения грубой силы для этой проблемы. Максимальный размер нашего диапазона равен 10⁵, но если бы нам нужно было проверить любой диапазон между a
и b
, какое наибольшее количество проверок нам нужно сделать? Хорошо, давайте выясним это с помощью быстрого скрипта:
Приведенная выше программа сообщит нам, сколько вычислений мы можем ожидать в *наихудшем случае* для диапазона от 0 до 10⁵. После того, как мы запустим его, мы получим следующий вывод:
1047 10987 12034
Это означает, что большинство вычислений, которые мы будем выполнять, составляют 1047, и это для a=10987
и b=12034
. Таким образом, это говорит нам о том, что мы можем без труда написать решение грубой силы для ее решения:
Есть ли более «эффективный» способ? Оказывается, есть, и это само собой разумеется, если мы сможем сгенерировать минимальное число, большее или равное x
, которое имеет различные цифры. Я вставил код ниже, который выполняет этот тип генерации. Это займет слишком много времени, чтобы объяснить, что он делает, поэтому, если у вас есть какие-либо вопросы по этому поводу, свяжитесь со мной в социальных сетях (ссылки ниже).
Действительная скобка
Ссылка на проблему: https://leetcode.com/problems/valid-parentheses/
Как и большинство задач, связанных со скобками, их можно решить с помощью стека. Каждый раз, когда вы видите открывающую скобку, вы помещаете ее в стек. Когда вы видите закрывающую фигурную скобку, вы открываете стек и проверяете совпадение. Если таковой существует, продолжайте. Если совпадения нет или стек пуст, последовательность недействительна.
Если мы итерируем строку без проблем, мы просто проверяем в конце, что стек пуст. Если это так, то наша последовательность была правильной, иначе, если стек не был пуст, наша последовательность была неверной:
Книга для рисования
Ссылка на проблему: https://www.hackerrank.com/challenges/drawing-book/problem
В этой задаче нам просто нужно найти, в каком номере листа мы находимся для данного номера страницы. Для этого деление на 2 (пол) даст нам это значение. например для страницы 1, 1/2 = 0
, для страницы 2, 2/2 = 1
, для страницы 3, 3/2 = 1
, для страницы 4, 2/2 = 2
и так далее. Таким образом, это дает нам, в каком индексе перелистывания мы находимся. Ключевым моментом является вычисление индекса перелистывания последней страницы, и тогда нашим ответом будет минимальное расстояние перелистывания от начала (индекс 0) до индекса перелистывания p
. , и расстояние от конца до флип-индекса p
:
def pageCount(n, p): fromStart = p // 2 fromEnd = n // 2 - p // 2 return (min(fromStart, fromEnd))
Если вы находитесь в Лондоне, я надеюсь увидеть вас на следующем мероприятии :). Хотите присоединиться к нашей слабой группе, чтобы обсудить подобные проблемы? Напишите мне в twitter или linkedin, чтобы присоединиться