Leetcode 991 Broken Calculator

发表于 |

给定两个数X,Y。现在需要你使用一定的操作将X变为Y，你可以使用的操作有：

  1. 将x翻倍
  2. 将x-1

返回最少的操作次数。

示例 1:
输入: X = 2, Y = 3
输出: 2
解释: Use double operation and then decrement operation {2 -> 4 -> 3}.

示例 2:
输入: X = 5, Y = 8
输出: 2
解释: Use decrement and then double {5 -> 4 -> 8}.

示例 3:
输入: X = 3, Y = 10
输出: 3
解释: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

示例 4:
输入: X = 1024, Y = 1
输出: 1023
解释: Use decrement operations 1023 times.

Note:

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

思路分析：
首先我们发现x要么乘2要么减1，如果x初始就比y大，那么只能一直做减法！
在x小于y的情况下：
如果y是奇数，那么最后一个操作一定是减1（显然）
如果y是偶数呢？最后操作一定是乘2吗？答案是yes!

因为对于某个x现在要变为y可能是先乘2再做若干次减法，也可能是先做若干次减法再乘2
第一种用式子表示为1 + 2*x-y，第二种用式子表示为x-y/2 + 1
显然式子2的结果永远小于等于式子1的结果！
所以，我们想要最小化次数一定是先减法再乘2，也就是y为偶数时，最后的操作一定是乘2

那么这里我们就从y开始反推，是奇数就加1，是偶数就除2，一直到y小于等于x为止！

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def brokenCalc(self, X, Y):
        if X >= Y: return X - Y
        res = 0
        while X < Y:
            if Y % 2 == 1:
                Y += 1
                res += 1
            Y //= 2
            res += 1
        return res + X - Y