0991. Broken Calculator

题目信息

题号:

0991

难度:

Medium

主题:

整数变换、两种操作、最少次数

原题:

LeetCode 0991

重点:

从 startValue 开始,每次只能把当前数乘以 2 或减去 1;需要恰好变为 target 并返回最少操作次数

题目重述

一个计算器初始显示正整数 startValue,只剩下两个可用操作:把当前显示值乘以 2,或把当前显示值减去 1。

可以按任意顺序重复使用这两个操作。请返回使显示值恰好变为正整数 target 所需的最少操作次数。

1 <= startValue, target <= 10^9。

自建示例

先减小再连续翻倍:

输入:startValue = 7, target = 20
输出:4
解释:执行 7 -> 6 -> 5 -> 10 -> 20,共四次操作。反向看,20 连续除以 2 得到 5,再增加两次回到 7,也说明少于四次无法完成。

初始值已经等于目标值:

输入:startValue = 9, target = 9
输出:0
解释:不执行任何操作就已经达到目标,因此最少操作次数为 0。