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

Топ K наиболее частый



К наиболее часто встречающихся элементов — LeetCode
По заданному целочисленному массиву nums и целому числу k вернуть k наиболее часто встречающихся элементов. Вы можете вернуть ответ в любой…leetcode.com



Статистика:

  • Большим преимуществом шлифовки является тот факт, что вы начинаете видеть закономерности в различных задачах и начинаете задаваться вопросом, какой оптимальный способ выполнения очень распространенных операций.
  • Одной из таких операций является подсчет отдельных элементов в массиве с использованием словаря. При использовании обычных операций со словарем требуется 5 строк кода. Если вместо этого вы используете setdefault, требуется 2.
  • Если вы действительно хотите это сделать, вы можете использовать Counter()из стандартных коллекций Python и сделать это одной строкой кода. .
  • Вы также получаете преимущество, заключающееся в том, что ваш код теперь настолько явный, насколько это возможно. Когда люди прочитают его, вместо того, чтобы увидеть объявление словаря и подумать «Интересно, для чего он будет его использовать…», они увидят счетчик. strong> и подумать: «Хорошо, он считает материал».
  • Та же идея применима и к спискам. Когда вы видите цикл for, вы понятия не имеете, что будет дальше, но понимание списка начнется со списка и создаст новый список, это все.
  • Последнее, что я хочу отметить, это то, что рекрутеры не глупы. Они не зададут вам именно эту задачу, а затем поразятся тому, насколько вы умны. Однако представьте, что у вас есть другая проблема, когда подсчет появлений является промежуточным шагом. Затем, если вы знаете кратчайший способ сделать это, у вас будет больше времени для реализации остальных.

Непрерывная сумма в массиве (TLE)



Минимальные операции для уменьшения X до нуля — LeetCode
Вам дан целочисленный массив nums и целое число x. За одну операцию вы можете либо удалить крайний левый, либо…leetcode.com



Статистика:

  • Поскольку мое решение недостаточно оптимально, я не буду подробно описывать каждый шаг, а буду следить за завтрашней версией.
  • Основная идея, на которую я хочу обратить внимание, заключается в том, что вы можете решить дополнительную проблему путем поиска самой длинной последовательности в середине массива. чья сумма равна sum(nums)-x. Так проще думать об этом, и вы можете легко преобразовать решение этой задачи в решение исходной задачи. В математике это называется двойные задачи, но я не буду притворяться, что достаточно умен, чтобы говорить об этом.
  • Мой подход стандартный, я сначала вычисляю частичные суммы, а затем вычисляю любую возможную сумму между двумя индексами в массиве, принимая во внимание самую длинную последовательность. Это имеет сложность O(n²), потому что у нас есть 2 вложенных цикла for, поэтому я полагаю, что оптимальное решение будет O(n logn) или О (п)
  • На самом деле, теперь, когда я подумал о сложности, я думаю, что все, что мне нужно сделать, это заменить второй цикл for на бинарный поиск, поскольку массив частичной суммы строго увеличивается. Посмотрим завтра, как это обернется.

Заключительные мысли:

  • Это похоже на шаг назад от двух проблем до одной, но это часть процесса. Если вы делаете что-то последовательно в течение достаточно долгого времени, вы понимаете, что небольшая неэффективность означает, чтовы правильно выбрали свой прогресс.
  • Но людей не учат так думать. Например, система образования дает вам отличную оценку, к которой нужно стремиться, но не более того. Если вы будете делать все, что вам говорят учителя, вы будете получать пятерки в течение многих лет.
  • Раньше я делал домашнее задание, готовился к контрольным, получал хорошие оценки, а затем играл в видеоигры до конца дня. Черт, меня даже похвалилиза то, что я так живу.
  • Затем вы поступите в хороший университет и поймете, что отличные оценки вашей средней школы в маленьком городке не совпадают с высокими оценками вашего коллеги в частной школе. или ваш иностранный коллега требует пятерки в азиатской школе.
  • Итак, теперь вы впервые в жизни оказались позади и не знаете, что делать. Вы всегда хорошо справлялись, но теперь вам нужно работать вдвое за половину похвалы.
  • Таким образом, вы либо принимаете тот факт, что вы сейчас проигрываете (осознание, которое обычно приводит вас к самому быстрому прогрессу в вашей жизни), либо решаете, что вы достаточно умны, чтобы справляться с трудностями (так что зачем пытаться преуспеть?)
  • Дело в том, что я не говорю вам приступить к работе и стать идеальным учеником, это далеко не так. Я просто хочу, чтобы вы поняли, что если вы решите быть только достаточно хорошими вместо того, чтобы отличиться (в любой области), вы должны использовать дополнительное время продуктивно.
  • Другими словами, это нормально, если вы умеренно хорошо успеваете в университете, потому что сейчас вы пытаетесь стать лучшим спортсменом, улучшить свои социальные навыки, работать над своими собственными проектами. , волонтер или путешествие
  • Ноэто не нормально, если вы игнорируете школьные задания, чтобы играть в игры или смотреть Netflix