LeetCode991：故障计算器的最优解法

在故障计算器上，我们有两种操作方式：

- **加倍（Double）**：将显示屏上的数字乘以2。
- **递减（Decrement）**：将显示屏上的数字减去1。

给定初始数字X，目标是通过上述两种操作，使显示屏上的数字变为Y。要求返回实现这一目标所需的最小操作次数。

### 示例

1. **示例 1**
- 输入: X = 2, Y = 3
- 输出: 2
- 解释: 先进行加倍运算，再递减 {2 -> 4 -> 3}。

2. **示例 2**
- 输入: X = 5, Y = 8
- 输出: 2
- 解释: 先递减，再加倍 {5 -> 4 -> 8}。

3. **示例 3**
- 输入: X = 3, Y = 10
- 输出: 3
- 解释: 先加倍，再递减，最后再加倍 {3 -> 6 -> 5 -> 10}。

4. **示例 4**
- 输入: X = 1024, Y = 1
- 输出: 1023
- 解释: 执行递减运算1023次。

### 提示

- 1 <= X <= 10^9
- 1 <= Y <= 10^9

### 解题思路

这是一个典型的贪心算法问题。当X >= Y时，直接返回X - Y即可。当X
关键在于逆向思维：如果Y是偶数，我们可以将其除以2；如果Y是奇数，我们可以先加1使其变为偶数再除以2。这样可以确保每次操作都是最优的。

例如，假设X - k = Y / 2，而2X - 2k = Y，前者需要K + 1次操作，后者需要2K + 1次操作。显然，前者的效率更高。

对于奇数Y，我们可以将其加1变为偶数，再进行除法操作。具体来说，如果X = (Y + 1) / 2 + k，那么只需要K + 2次操作，而直接递减则需要K + 3次操作。

### Python代码实现

#### 迭代版本
```python
class Solution:
def brokenCalc(self, X: 'int', Y: 'int') -> 'int':
res = 0
while X res += Y % 2 + 1
Y = (Y + 1) // 2
return res + X - Y
```

#### 递归版本
```python
class Solution:
def brokenCalc(self, X: 'int', Y: 'int') -> 'int':
if X >= Y:
return X - Y
return 1 + self.brokenCalc(X, Y + 1 if Y % 2 else Y // 2)
```

### 参考资料

- [LeetCode讨论区](https://leetcode.com/problems/broken-calculator/discuss/234484/JavaC%2B%2BPython-Change-Y-to-X-in-1-Line)

### 总结

通过逆向思维和贪心算法，我们可以高效地解决这个问题。希望这篇文章能帮助你更好地理解该问题及其解决方案。如果有任何问题或建议，请随时指出！