397. 整数替换

🟠   🔖  贪心 位运算 记忆化搜索 动态规划  🔗 力扣 LeetCode

题目

Given a positive integer n, you can apply one of the following operations:

1. If n is even, replace n with n / 2.
2. If n is odd, replace n with either n + 1 or n - 1.

Return the minimum number of operations needed for n to become 1.

Example 1:

Input: n = 8

Output: 3

Explanation: 8 -> 4 -> 2 -> 1

Example 2:

Input: n = 7

Output: 4

Explanation: 7 -> 8 -> 4 -> 2 -> 1

or 7 -> 6 -> 3 -> 2 -> 1

Example 3:

Input: n = 4

Output: 2

Constraints:

• 1 <= n <= 2^31 - 1

题目大意

给定一个正整数 n ，你可以做如下操作：

1. 如果 n 是偶数，则用 n / 2替换 n 。
2. 如果 n 是奇数，则可以用 n + 1 或 n - 1 替换 n 。

返回 n 变为 1 所需的最小替换次数 。

示例 1：

输入： n = 8

输出： 3

解释： 8 -> 4 -> 2 -> 1

示例 2：

输入： n = 7

输出： 4

解释： 7 -> 8 -> 4 -> 2 -> 1

或 7 -> 6 -> 3 -> 2 -> 1

示例 3：

输入： n = 4

输出： 2

提示：

• 1 <= n <= 2^31 - 1

解题思路

• 递归与记忆化：

  • 使用递归方法计算从 n 到 1 的最小操作次数。
  • 通过缓存中间结果避免重复计算，加速求解过程。

• 奇偶处理策略：

  • 若 n 为偶数，直接递归计算 n / 2，所需操作次数为 1 + traverse(n / 2)。
  • 若 n 为奇数，则有两种选择：
    • 将 n - 1 递归转换为 1。
    • 将 n + 1 递归转换为 1。
  • 取两者中较小的操作次数。

复杂度分析

• 时间复杂度：O(log n)，由于记忆化递归避免了大量重复计算，每次减少数值规模。
• 空间复杂度：O(log n)，递归调用栈深度。

代码

/**
 * @param {number} n
 * @return {number}
 */
var integerReplacement = function (n) {
	let cache = new Map();
	const traverse = (n) => {
		if (n == 1) return 0; // 基础情况
		if (cache.has(n)) return cache.get(n);
		let operations;
		if (n % 2 == 0) {
			operations = traverse(n / 2) + 1;
		} else {
			operations = Math.min(traverse(n - 1), traverse(n + 1)) + 1;
		}
		cache.set(n, operations); // 缓存结果
		return operations;
	};
	return traverse(n);
};