Сложность: 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 {
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = getNext(n);
}
return n == 1;
}
}Ставь 👍 и забирай 📚 Базу знаний