Сложность: easy
Напишите алгоритм для определения, является ли число n счастливым.
Счастливое число определяется следующим образом:
1. Начинаем с любого положительного числа и заменяем его на сумму квадратов его цифр.
2. Повторяем процесс до тех пор, пока число не станет равным 1 (где оно останется), или пока оно не зациклится бесконечно, не достигая 1.
3. Числа, для которых этот процесс заканчивается на 1, являются счастливыми.
4. Верните true, если n является счастливым числом, и false, если нет.
Пример:
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
👨💻 Алгоритм:
1️⃣Определите следующее число для заданного числа n. Это можно сделать, используя операции деления и взятия по модулю, чтобы последовательно извлекать цифры из числа, пока они не закончатся, затем возводить каждую извлечённую цифру в квадрат и суммировать их. Внимательно посмотрите на код для этого, "извлечение цифр по одной" — полезная техника, которую вы будете использовать для решения множества различных задач.
2️⃣Следите за цепочкой чисел и обнаруживайте, если мы вошли в цикл. Это можно сделать с помощью HashSet. Каждый раз, когда мы генерируем следующее число в цепочке, мы проверяем, есть ли оно уже в нашем HashSet. Если его нет в HashSet, мы добавляем его. Если оно уже в HashSet, это означает, что мы находимся в цикле и должны вернуть false.
3️⃣Мы используем HashSet, а не Vector, List или Array, потому что мы многократно проверяем, находятся ли числа в нём. Проверка, находится ли число в HashSet, занимает время O(1), тогда как для других структур данных это занимает время O(n). Выбор правильных структур данных — важная часть решения этих задач.
😎 Решение:
class Solution:
def isHappy(self, n: int) -> bool:
def get_next(n):
total_sum = 0
while n > 0:
n, digit = divmod(n, 10)
total_sum += digit**2
return total_sum
seen = set()
while n != 1 and n not in seen:
seen.add(n)
n = get_next(n)
return n == 1
Ставь 👍 и забирай 📚 Базу знаний