Код Python для этой задачи Leetcode
Ниже приводится мое решение проблемы с Leetcode, Happy Number. Это взято из моего информационного бюллетеня Technology Made Simple. Больше информации в конце.
Проблема
Напишите алгоритм, определяющий, является ли число n счастливым.
Счастливое число – это число, определяемое следующим процессом:
- Начиная с любого положительного целого числа, замените число суммой квадратов его цифр.
- Повторяйте процесс до тех пор, пока число не станет равным 1 (где оно и останется), или он зацикливается бесконечно в цикле, который не включает 1.
- Те числа, для которых этот процесс заканчивается на 1, считаются счастливыми.
Возвратите true если n это счастливое число, и false если нет.
Пример 1:
Input: n = 19 Output: true Explanation: 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1
Пример 2:
Input: n = 2 Output: false
Ограничения:
1 <= n <= 2^(31) - 1
Вы можете протестировать свое решение здесь
Шаг 1: Анализ определений
Я считаю, что в таких случаях лучше атаковать, пытаясь разобрать определения, данные в задаче. Четко определяя проблему и все определения, мы можем лучше понять проблему. И во многих случаях это может помочь вам придумать математические правила и формулировки, которые позволят вам решить проблему намного быстрее, чем в среднем. Это может быть просто моя степень по математике и работа в области искусственного интеллекта, но такой подход определенно является конкурентным преимуществом. Не так много специалистов по программному обеспечению, которые активно пытаются искать закономерности или математические/алгоритмические утверждения. Даже если вы не можете придумать полные функции для создания выходных данных, вы получите представление о том, как решить/оптимизировать эту проблему.
Я предпочитаю идти снизу вверх при атаке определений, начиная с самых простых. Постоянные читатели знают, насколько сильна погоня за низко висящими плодами, особенно в таких контекстах, как интервью, где от вас ожидают связного изложения своих мыслей. Итак, давайте приступим к наименьшему определению, которое мы можем видеть: что означает бесконечное повторение числа?
Это может показаться очевидным для всех вас, но сделайте шаг назад. Как бы вы определили бесконечный цикл? Некоторым людям может потребоваться очень-очень много времени, чтобы достичь счастья, но они не несчастны. Называть их несчастными было бы неправильно и, вероятно, задело бы их чувства.
Итак, давайте напрягем наши мозги, чтобы посмотреть, сможем ли мы что-нибудь придумать. Вспомните, как вы можете определить, застряли ли мы в петле. Какие определения обычно используются?
Шаг 2: Велоспорт
Обратите внимание на проблему. Имея число x, мы можем перейти только к одному другому y. Например, учитывая 2, мы можем сгенерировать только 4. Благодаря заданным правилам мы не можем перейти к другим числам при заданном входе. Наше решение является детерминированным (просто причудливый математический термин для тех из вас, кто действительно хочет заявить о своем доминировании над интервьюерами).
Это означает, что если мы уже видели число во время прогона, мы застряли в цикле. Мы уже знаем, куда мы пойдем отсюда, и что мы в конечном итоге вернемся к этой точке. Мы будем бегать по кругу.
Если вы заметили это до этого момента, похлопайте себя по спине. Отличное понимание. Если у вас не получилось, не корите себя слишком сильно. Требуется время и усилия, чтобы стать хорошим в этом. Теперь, когда вы здесь, просто приходите и делайте работу. Ваши результаты гарантированы. Теперь вернемся к проблеме.
Таким образом, мы можем применять стандартные алгоритмы обнаружения циклов для быстрого прохождения. Лучший способ сделать это — сохранить набор для отслеживания посещенных узлов. Хотя это можно было бы сделать с помощью алгоритма Флойда, этот подход, похоже, не слишком хорошо работает на практике. Это связано с тем, что для больших циклов сходимость происходит относительно медленно. Наше решение использует немного больше памяти, но всегда останавливается на первом общем узле. Обнаружение цикла Флойда этого не сделает (но требует меньше памяти).
Убедитесь, что вы исследуете этот компромисс в своих интервью. Оба решения будут иметь одинаковую временную сложность Big O, но использование набора обычно будет быстрее. Спросите своего интервьюера, что он предпочел бы (это действительно показывает ваши знания и способность рассматривать альтернативы). Я собираюсь поделиться решением с использованием набора, но убедитесь, что вы практикуете оба. Если кто-то из вас, подписавшихся премиум-классом, хочет другое решение, просто ответьте на это письмо (или воспользуйтесь ссылками ниже) и дайте мне знать. Однако сначала я бы порекомендовал создать альтернативу самостоятельно для получения наибольшей выгоды.
Код
Когда мы знаем, как обнаруживать циклы, код становится относительно простым. Посмотрите ниже.
class Solution:
def isHappy(self, n: int) -> bool:
def squareDigits(old_n):
new_n = 0
while old_n > 0:
digit = old_n % 10
new_n += pow(digit, 2)
old_n //= 10
return new_n
seen = set()
while n!=1 and n not in seen:
seen.add(n)
n = squareDigits(n)
return n==1
Временная сложность — O(n).
Космическая сложность - O (n)
Если вам понравилась эта статья, вам понравится мой ежедневный электронный бюллетень Простые технологии. Он охватывает темы по разработке алгоритмов, математике, искусственному интеллекту, науке о данных, недавним событиям в области технологий, разработке программного обеспечения и многим другим, чтобы сделать вас лучшим разработчиком. Сейчас действует скидка 20 % на ЦЕЛЫЙ ГОД, так что не забудьте проверить. Использование этой скидки снизит цены-
800 индийских рупий (10 долларов США) → 533 индийских рупии (8 долларов США) в месяц
8000 индийских рупий (100 долларов США) → 6400 индийских рупий (80 долларов США) в год
Подробнее о новостной рассылке можно узнать здесь
Свяжитесь со мной
Воспользуйтесь ссылками ниже, чтобы ознакомиться с другим моим контентом, узнать больше о репетиторстве или просто поздороваться. Кроме того, ознакомьтесь с бесплатной реферальной ссылкой Robinhood. Мы оба получаем свободный сток (денег вкладывать не надо), и никакого риска для вас нет. Таким образом, если вы не используете его, вы просто потеряете бесплатные деньги.
Чтобы помочь мне понять вас, заполните этот опрос (анонимно)
Ознакомьтесь с другими моими статьями на Medium. : https://rb.gy/zn1aiu
Мой Ютуб: https://rb.gy/88iwdd
Свяжитесь со мной в LinkedIn. Подключаемся: https://rb.gy/m5ok2y
Мой Инстаграм: https://rb.gy/gmvuy9
Мой Твиттер: https://twitter.com/Machine01776819
Если вы хотите построить карьеру в сфере технологий: https://codinginterviewsmadesimple.substack.com/
Получите бесплатный сток на Robinhood: https://join.robinhood.com/fnud75
