坏了的计算器
难度:
标签:
题目描述
代码结果
运行时间: 24 ms, 内存: 16.2 MB
/*
* 思路：
* 使用 Java Stream API 来实现相同的逻辑。
* 通过反向操作来减少目标值并使用计数器记录操作次数。
*/
import java.util.stream.Stream;
public class BrokenCalculatorStream {
public int brokenCalc(int startValue, int target) {
int operations = 0;
while (target > startValue) {
target = target % 2 == 0 ? target / 2 : target + 1;
operations++;
}
return operations + (startValue - target);
}
public static void main(String[] args) {
BrokenCalculatorStream calculator = new BrokenCalculatorStream();
System.out.println(calculator.brokenCalc(2, 3)); // 输出: 2
System.out.println(calculator.brokenCalc(5, 8)); // 输出: 2
System.out.println(calculator.brokenCalc(3, 10)); // 输出: 3
}
}解释
方法:
该题解采用了逆向思维的策略。从 target 开始，逆向操作直到达到或小于 startValue。如果 target 是偶数，则进行逆向的双倍操作（实际上是除以 2），如果是奇数，则通过逆向的递减操作（实际上是加 1）使其变为偶数。这种逆向操作持续进行，直至 target 小于或等于 startValue。一旦 target 小于 startValue，剩余的操作数即为两者之差，因为每一次递减操作相当于直接从 startValue 减去 1 直到等于 target。这种逆向策略利用了除法迅速减小数值的特性，通常比正向操作更快达到目标。
时间复杂度:
O(log(target))
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在逆向操作中优先选择将奇数变为偶数再进行除以2的操作，而不是直接对奇数减1直到与startValue相等？
▷🦆
在逆向操作的过程中，如果target经过除以2操作后变得小于startValue，这种情况下如何最小化操作数？
▷🦆
逆向操作的策略是否总是优于正向操作，即从startValue操作到target？能否举例说明可能的情况？
▷🦆
在最终操作，即将target调整到小于startValue的情况中，是否考虑过其他操作方式，例如，使用倍增操作来减少总操作次数？
▷相关问题
两个键的键盘
最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：
Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。Paste（粘贴）：粘贴 上一次 复制的字符。
给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。
示例 1：
输入：3 输出：3 解释： 最初, 只有一个字符 'A'。 第 1 步, 使用 Copy All 操作。 第 2 步, 使用 Paste 操作来获得 'AA'。 第 3 步, 使用 Paste 操作来获得 'AAA'。
示例 2：
输入：n = 1 输出：0
提示：
1 <= n <= 1000