Java | LeetCode

Задача: 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 {
    public int integerReplacement(int n) {
        Map<Long, Integer> memo = new HashMap<>();
        return helper(n, memo);
    }
    
    private int helper(long n, Map<Long, Integer> memo) {
        if (n == 1) return 0;
        if (memo.containsKey(n)) return memo.get(n);
        
        if (n % 2 == 0) {
            memo.put(n, 1 + helper(n / 2, memo));
        } else {
            memo.put(n, 1 + Math.min(helper(n + 1, memo), helper(n - 1, memo)));
        }
        
        return memo.get(n);
    }
}

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