Еще раз здравствуйте и добро пожаловать на серию ежедневных тренировок LeetCode. Сегодня мы реализуем оптимальную версию задачи, которую пытались решить вчера. В общей сложности сегодня я решил 3 задачи за 30 минут.
Реванш
Вчера я написал решение для этого, но, как вы, возможно, помните, оно не совсем сработало:
И это тоже было хорошее решение, оно делало именно то, что должно было, у него было 2 приятные функции, но проблема заключалась в том, что это занимало слишком много времени.
Вот улучшенное решение:
Теперь, если вы прочитаете его, вы, возможно, не поймете, почему он работает, но вы точно поймете, что он делает. Он подсчитывает все последовательные строки из единиц или нулей. Затем он перебирает каждую пару из двух таких счетчиков и добавляет минимальный один к окончательному решению.
Логика такова, что если у вас есть что-то вроде 11100011, это приведет к следующим строкам: 111000, 0011.
111000 генерирует 111000, 1100 и 10
0011 генерирует 0011 и 01
Очевидно, что это решение — не первое, о чем вы думаете, когда смотрите на проблему, если только вы не проверяете ограничения. 1 <= s.length <= 10^5
Если вы знакомы с большой нотацией O, вы можете сделать вывод, что наша первоначальная реализация имела сложность O(n²), а текущая — O( н). Это означает, что для первого решения потребовалось (10⁵)² операций, а для улучшенного решения — всего 10⁵ операций.
Стандартный процессор с частотой 1 ГГц может выполнять 10⁶ операций в секунду, и вы можете смело предположить, что ваш код на LeetCode будет работать на чем-то подобном не более 1 секунды.
Подумайте об этом так: всякий раз, когда вы реализуете какое-либо решение проблемы на LeetCode, у вас есть общий бюджет в 10⁶ операций. Если вам нужно работать с вектором из 10⁶элементов, вы должны реализовать алгоритм не хуже O(n). Если длина вектора составляет 10³ элементов, вы можете обойтись O(n²). Для 10² можно обойтись O(n³) и так далее.
Если вы всегда проверяете ограничения, прежде чем приступить к написанию кода для решения проблемы, теперь вы можете с самого началазнать, какие решения не стоит даже думать, потому что они >слишком неэффективно.
Нет исключений
Эта задача не очень сложна, вам нужно сначала найти индекс символа, а затем перевернуть строку до этого символа. Что интересно, так это то, как строковый метод .index() работает в Python:
Как видите, это исключение, и его необходимо обработать. Это означает, что мы должны окружить его блоком try-except. В блок try мы помещаем наш код, который может генерировать исключение, а в блок exception мы помещаем код, который должен выполняться, если исключение сгенерировано. Вот мое решение проблемы:
Как видите, единственная инструкция в предложении except — это pass, то есть инструкция Python, которая ничего не делает. Мы в основном игнорируем исключение и позволяем программе завершиться как обычно, что вернет исходное слово.
Загадочный
Последнюю сегодняшнюю задачу очень легко обобщить: найти максимальное произведение трех чисел в массиве.
Вот решение, двухстрочное, которое обрабатывает все случаи:
Итак, мы сначала сортируем числа, и одно значение, которое мы можем попробовать в качестве кандидата на самый большой продукт, — это произведение 3 самых больших чисел.
Давайте рассмотрим случай, когда некоторые из наших чисел отрицательны. Тогда может оказаться выгодным умножить два самых маленьких (которые имеют очень большие абсолютные значения) на самый большой.
Но в последней ситуации все равно может быть выгодно умножить 3 самых больших числа , как в следующем примере: [-2, -1, 10, 20, 30].
Когда я изначально писал его, у меня было около 2 вложенных условий if, но я всегда возвращал из них только 2 возможных значения, поэтому тогда я подумал о рефакторинге. strong> это так.
Если вас интересуют такие же простые для понимания проблемы, решение которых может быть запутанным или очень чистым, в зависимости от вашей изобретательности, вы должны проверить печально известную проблему с FizzBuzz.
Заключительные мысли:
- Что бы ни случилось, продолжайте двигаться вперед
