leetcode 991. 坏了的计算器

题意：

在显示着数字的坏计算器上，我们可以执行以下两种操作：

• 双倍（Double）：将显示屏上的数字乘 2；
• 递减（Decrement）：将显示屏上的数字减 1 。

最初，计算器显示数字 X。

返回显示数字 Y 所需的最小操作数

示例 1：

输入：X = 2, Y = 3
输出：2
解释：先进行双倍运算，然后再进行递减运算 {2 -> 4 -> 3}.

示例 2：

输入：X = 5, Y = 8
输出：2
解释：先递减，再双倍 {5 -> 4 -> 8}.

提示：

1. 1 <= X <= 10^9
2. 1 <= Y <= 10^9

思路：

我们进行逆向思维，若Y只能除二或者加一，怎样通过最小的步数变为X，那么就有如下两种情况：

1.当前Y<=X，那么直接返回步数加上( X - Y )

2.当前Y是奇数，我们将Y + 1

3.当前Y是偶数，我们将Y / 2

那么为什么是这样的呢？Y是偶数时，我们假设X = Y / 2 + K，即2X = Y + 2K，前者需要K+1次操作，而后者需要2K+1次操作，显然前者更优，所以我们采取先减后乘，而不是先乘后减，那么对Y来说就是除法优先；Y是奇数时，我们假设X = (Y + 1) / 2 + K，对于这种情况，我们只需要将Y+1就可以转换为前者了。

 1 class Solution {
 2 public:
 3     int brokenCalc(int X, int Y) {
 4         int ans=0;
 5         while(1){
 6             if(X>=Y)return ans+X-Y;
 7             if(Y%2)Y+=1,ans++;
 8             else Y/=2,ans++;
 9         }
10         return ans;
11     }
12 };

View Code

leetcode 991. 坏了的计算器

原文：https://www.cnblogs.com/ljy08163268/p/11815636.html