0991. Broken Calculator¶
题目信息¶
- 题号:
0991
- 难度:
Medium
- 主题:
整数变换、两种操作、最少次数
- 原题:
- 重点:
从
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。