Сложность: 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 {
isHappy(n) {
function getNext(n) {
let totalSum = 0;
while (n > 0) {
let digit = n % 10;
totalSum += digit * digit;
n = Math.floor(n / 10);
}
return totalSum;
}
let seen = new Set();
while (n !== 1 && !seen.has(n)) {
seen.add(n);
n = getNext(n);
}
return n === 1;
}
}Ставь 👍 и забирай 📚 Базу знаний