网站搭建福州公司,行业网站建设收费明细,高端服装品牌排行榜,做营销网站代理挣钱吗文章目录1. 题目2. 解题1. 题目
你正在玩一个整数游戏。从整数 1 开始#xff0c;期望得到整数 target 。
在一次行动中#xff0c;你可以做下述两种操作之一#xff1a;
递增#xff0c;将当前整数的值加 1#xff08;即#xff0c; x x 1#xff09;。加倍#…
文章目录1. 题目2. 解题1. 题目
你正在玩一个整数游戏。从整数 1 开始期望得到整数 target 。
在一次行动中你可以做下述两种操作之一
递增将当前整数的值加 1即 x x 1。加倍使当前整数的值翻倍即x 2 * x。
在整个游戏过程中你可以使用 递增 操作 任意 次数。 但是只能使用 加倍 操作 至多 maxDoubles 次。
给你两个整数 target 和 maxDoubles 返回从 1 开始得到 target 需要的最少行动次数。
示例 1
输入target 5, maxDoubles 0
输出4
解释一直递增 1 直到得到 target 。示例 2
输入target 19, maxDoubles 2
输出7
解释最初x 1 。
递增 3 次x 4 。
加倍 1 次x 8 。
递增 1 次x 9 。
加倍 1 次x 18 。
递增 1 次x 19 。示例 3
输入target 10, maxDoubles 4
输出4
解释
最初x 1 。
递增 1 次x 2 。
加倍 1 次x 4 。
递增 1 次x 5 。
加倍 1 次x 10 。 提示
1 target 10^9
0 maxDoubles 100来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-moves-to-reach-target-score 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
逆向考虑是偶数的话优先使用 除以 2
class Solution:def minMoves(self, target: int, maxDoubles: int) - int:ans 0while target 1:if target1 1: # 奇数ans 1target - 1elif maxDoubles: # 还可以 / 2ans 1target // 2maxDoubles - 1else: # 不能除以 2 了直接全部 -1ans target-1breakreturn ans 32 ms 15 MB Python3 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
