Задача: 397. Integer Replacement
Сложность: medium

К положительному целому числу n можно применить одну из следующих операций: если n четное, замените n на n / 2. если n нечетное, замените n на n + 1 или n - 1. верните минимальное количество операций, необходимых для того, чтобы n стало 1.

Пример:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

👨‍💻 Алгоритм:

1⃣Начните с данного числа n и выполните одну из следующих операций:
Если n четное, замените n на n / 2.
Если n нечетное, замените n на n + 1 или n - 1.

2⃣Используйте метод динамического программирования или жадный метод, чтобы найти минимальное количество операций, необходимых для достижения n = 1. Определите, какая операция (n + 1 или n - 1) является более эффективной для минимизации количества шагов.

3⃣Продолжайте выполнять выбранные операции, пока n не станет равным 1. Считайте количество выполненных операций и верните это значение как результат.

😎 Решение:

class Solution {
    integerReplacement(n) {
        const memo = new Map();
        return this.helper(n, memo);
    }
    
    helper(n, memo) {
        if (n === 1) return 0;
        if (memo.has(n)) return memo.get(n);
        
        if (n % 2 === 0) {
            memo.set(n, 1 + this.helper(n / 2, memo));
        } else {
            memo.set(n, 1 + Math.min(this.helper(n + 1, memo), this.helper(n - 1, memo)));
        }
        
        return memo.get(n);
    }
}

Ставь 👍 и забирай 📚 Базу знаний