LeetCode 991. Broken Calculator

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2019/02/12/LeetCode-991-Broken-Calculator/

访问原文「LeetCode 991. Broken Calculator

题目要求

On a broken calculator that has a number showing on its display, we can perform two operations:

  • Double: Multiply the number on the display by 2, or;
  • Decrement: Subtract 1 from the number on the display.
    Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: X = 3, Y = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

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

题意解析

目前有一个坏了的计算器,只能有两个操作,一个是加倍也就是乘以2,另外一个是减一。
现在两个数字,XY,在使用这个坏计算器的基础上,从X得到Y的最少操作次数。

解法分析

反过来考虑这个问题,也就是如何从Y得到X,而操作变为:

  1. 如果Y是偶数,Y = Y / 2
  2. 如果Y是奇数,Y = Y + 1

Y <= X时,无法进行Y = Y / 2,只需要进行Y = Y + 1
Y > X时,需要持续的减少Y,直到Y <= X

  • 如果Y是偶数,Y = Y / 2
  • 如果Y是奇数,Y = Y + 1
    因为(Y + 1 + 1) / 2 = (Y / 2) + 1,而等号左边需要3步而右边仅需要2步,所以当Y为偶数时仅需要考虑Y = Y / 2

解题代码

1
2
3
4
5
6
7
8
public int brokenCalc(int X, int Y) {
int step = 0;
while (Y > X) {
Y = Y % 2 > 0 ? Y + 1 : Y / 2;
step++;
}
return step + X - Y;
}
Jerky Lu wechat
欢迎加入微信公众号