(a) Теория чисел.

Leetcode описывает Счастливое число как число, определяемое следующим процессом: начиная с любого положительного целого числа, замените число суммой квадратов его цифр и повторяйте процесс, пока число не станет равным 1 (там, где он останется), или он бесконечно зацикливается в цикле, который не включает 1.

Используя 23 в качестве примера,

2² + 3² = 13
Hence 23 is replaced by 13. The process is now repeated:
1² + 3² = 10
Then:
1² + 0² = 1
The process ends at this point since 1² = 1. From this we conclude that 23 (and 13 and 10) are happy numbers.

Рассмотрим путь ниже, иллюстрирующий связь между несчастливыми числами от 1 до 100.

Обратите внимание, что несчастливые числа перемещаются по циклическому циклу, включающему 4, 16, 37, 58, 89, 145, 42,и20.

Алгоритм счастливого числа требует, чтобы мы определили, является ли число n «счастливым». Возвращает True, если n — счастливое число, и False, если нет.

(b) не очень оптимальное решение.

Рассмотрим следующий подход грубой силы к решению алгоритма.

+function isHappyNumber(num) {
  num = num.toString().split('');
  var sum = 0;
for(i=0; i<num.length; i++) {
    sum+= num[i] * num[i];
  }
if(sum==0) {
    return true;
  } else {
    try {
      return isHappyNumber(sum);
    } catch(error) {
      return false;
    }
  }
}(19);

Вы можете использовать игровую площадку кода Leetcode для запуска тестов. Обязательно установите JavaScript в качестве языка редактора. +function isHappyNumber(){}(); является IIFE. Я использовал последние круглые скобки, чтобы передать 19 в качестве аргумента функции в приведенном выше примере.

Здесь мы оцениваем значение суммы, а затем используем sum == 0 в качестве проверки базового условия. Затем мы рекурсивно повторяем этот процесс, пока не получим значение return. Для счастливых чисел цикл завершается на ранних стадиях цикла рекурсии. Несчастливые числа будут повторяться дольше. Мы учитываем их поведение, перехватывая исключение StackOverflow, вызванное использованием неудовлетворительного числа в качестве аргумента нашей функции. Мы возвращаем false, когда это происходит, выходим из нашей функции.

( c ) Оптимизированное решение.

Учитывая, что все несчастливые числа превращаются в циклический цикл значений sum, то есть — 4, 16, 37, 58, 89, 145, 42, и 20 — мы можем заменить проверку StackOverflow в приведенном выше решении проверкой циклического цикла для наших значений sum, чтобы идентифицировать не -счастливые числа. Сколько времени потребуется относительно большому несчастливому числу, чтобы добраться до этой циклической петли? Я провел несколько тестов — ознакомьтесь с результатами тестов ниже.

Не так уж и долго, верно? Теперь мы изменим определение функции на:

var sumArray = [];
+function isHappy(n) {
    n = n.toString().split('');
    var sum = 0;
    for(var i =0; i<n.length; i++)
        sum += +n[i] * +n[i];
if(sum==1) {
        return true;
    } else {
        if(sumArray.indexOf(sum)===-1) {
            sumArray.push(sum);
            return isHappy(sum);
        } else {
            return false;
        }
    }
}(13);

Приведенная выше функция должна возвращать true.

Удачного кодирования! 🎉

Повышение уровня кодирования

Спасибо, что являетесь частью нашего сообщества! Подпишитесь на наш канал YouTube или присоединитесь к курсу собеседования по программированию Skilled.dev.



Вопросы на собеседовании по программированию + поиск работы для разработчиков | Skilled.dev
Курс для прохождения собеседования по кодированиюskilled.dev