LeetCode 2139. 得到目标值的最少行动次数（贪心）

Michael阿明

发布于 2022-03-10 18:05:35

2020

发布于 2022-03-10 18:05:35

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

文章目录
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 = 0
        while target > 1:
            if target&1 == 1: # 奇数
                ans += 1
                target -= 1
            elif maxDoubles: # 还可以 / 2
                ans += 1
                target //= 2
                maxDoubles -= 1
            else: # 不能除以 2 了，直接全部 -1
                ans += target-1
                break
        return ans

32 ms 15 MB Python3

我的CSDN博客地址 https://michael.blog.csdn.net/

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

https