Сложность: 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:
def integerReplacement(self, n: int) -> int:
def helper(n, memo):
if n == 1:
return 0
if n in memo:
return memo[n]
if n % 2 == 0:
memo[n] = 1 + helper(n // 2, memo)
else:
memo[n] = 1 + min(helper(n + 1, memo), helper(n - 1, memo))
return memo[n]
return helper(n, {})
Ставь 👍 и забирай 📚 Базу знаний