企业官网建设流程全解析

题目

标题和出处

标题：得到目标值的最少行动次数

出处：2139. 得到目标值的最少行动次数

难度

4 级

题目描述

要求

你正在玩一个整数游戏。从整数1 \texttt{1}1开始，目标是得到整数target \texttt{target}target。

在一次行动中，你可以做下述两种操作之一：

• 递增，将当前整数的值加1 \texttt{1}1（即x \texttt{x}x变成x + 1 \texttt{x} + \texttt{1}x+1）。
• 加倍，使当前整数的值翻倍（即x \texttt{x}x变成2 × x \texttt{2} \times \texttt{x}2×x）。

可以使用递增操作任意次数，但是只能使用加倍操作至多maxDoubles \texttt{maxDoubles}maxDoubles次。

给定两个整数target \texttt{target}target和maxDoubles \texttt{maxDoubles}maxDoubles，返回从1 \texttt{1}1开始得到target \texttt{target}target需要的最少行动次数。

示例

示例 1：

输入：target = 5, maxDoubles = 0 \texttt{target = 5, maxDoubles = 0}target = 5, maxDoubles = 0
输出：4 \texttt{4}4
解释：一直递增1 \texttt{1}1直到得到target \texttt{target}target。

示例 2：

输入：target = 19, maxDoubles = 2 \texttt{target = 19, maxDoubles = 2}target = 19, maxDoubles = 2
输出：7 \texttt{7}7
解释：最初，x = 1 \texttt{x = 1}x = 1。
递增3 \texttt{3}3次，x = 4 \texttt{x = 4}x = 4。
加倍1 \texttt{1}1次，x = 8 \texttt{x = 8}x = 8。
递增1 \texttt{1}1次，x = 9 \texttt{x = 9}x = 9。
加倍1 \texttt{1}1次，x = 18 \texttt{x = 18}x = 18。
递增1 \texttt{1}1次，x = 19 \texttt{x = 19}x = 19。

示例 3：

输入：target = 10, maxDoubles = 4 \texttt{target = 10, maxDoubles = 4}target = 10, maxDoubles = 4
输出：4 \texttt{4}4
解释：最初，x = 1 \texttt{x = 1}x = 1。
递增1 \texttt{1}1次，x = 2 \texttt{x = 2}x = 2。
加倍1 \texttt{1}1次，x = 4 \texttt{x = 4}x = 4。
递增1 \texttt{1}1次，x = 5 \texttt{x = 5}x = 5。
加倍1 \texttt{1}1次，x = 10 \texttt{x = 10}x = 10。

数据范围

• 1 ≤ target ≤ 10 9 \texttt{1} \le \texttt{target} \le \texttt{10}^\texttt{9}1≤target≤109
• 0 ≤ maxDoubles ≤ 100 \texttt{0} \le \texttt{maxDoubles} \le \texttt{100}0≤maxDoubles≤100

解法

思路和算法

如果正向计算如何从1 11到达target \textit{target}target，则由于乘法的情况较为复杂，因此需要考虑多种可能的情况。

可以考虑反向操作，每次反向操作可以将当前整数除以2 22或减1 11，除以2 22的操作只有在当前整数是偶数且加倍操作剩余次数大于0 00的情况下才能执行，计算从target \textit{target}target到达1 11的最少反向操作次数，反向操作过程中如果有除以2 22的操作则需要更新maxDoubles \textit{maxDoubles}maxDoubles。以下所说的操作均为反向操作。

当target \textit{target}target是奇数或maxDoubles = 0 \textit{maxDoubles} = 0maxDoubles=0时，只能将target \textit{target}target减1 11。当target \textit{target}target是偶数且maxDoubles > 0 \textit{maxDoubles} > 0maxDoubles>0时，可以将target \textit{target}target除以2 22并将maxDoubles \textit{maxDoubles}maxDoubles减1 11，或将target \textit{target}target减1 11，此时需要分别考虑两种操作，计算最少操作次数。

对target \textit{target}target执行一次除以2 22操作之后，target \textit{target}target变成target 2 \dfrac{\textit{target}}{2}2target​，等价于执行target 2 \dfrac{\textit{target}}{2}2target​次减1 11操作，因此和全部执行减1 11操作相比，执行一次除以2 22操作可以将操作次数减少target 2 − 1 \dfrac{\textit{target}}{2} - 12target​−1次，当target \textit{target}target越大时，执行除以2 22操作可以减少的操作次数越多。由于除以2 22操作的次数存在上限，为了使操作次数最少，应该尽可能在target \textit{target}target大的时候执行除以2 22操作。

由于每次对target \textit{target}target执行除以2 22或减1 11操作都会使target \textit{target}target减少，因此应该尽早执行除以2 22操作。当target \textit{target}target是大于2 22的偶数且maxDoubles > 0 \textit{maxDoubles} > 0maxDoubles>0时，如果将target \textit{target}target执行两次减1 11再除以2 22，则需要三次操作，可以替换成等效的将target \textit{target}target除以2 22再减1 11，只需要两次操作，且两种情况都将maxDoubles \textit{maxDoubles}maxDoubles减1 11，因此将target \textit{target}target除以2 22的情况下可以得到最少操作次数。

根据上述分析，可以使用贪心的思想模拟反向操作并计算最少操作次数。具体做法如下。

1. 当target > 1 \textit{target} > 1target>1且maxDoubles > 0 \textit{maxDoubles} > 0maxDoubles>0时，如果target \textit{target}target是奇数则将target \textit{target}target减1 11，如果target \textit{target}target是偶数则将target \textit{target}target除以2 22并将maxDoubles \textit{maxDoubles}maxDoubles减1 11，每次操作之后将操作次数加1 11。重复该操作直到target = 1 \textit{target} = 1target=1或maxDoubles = 0 \textit{maxDoubles} = 0maxDoubles=0。

2. 当target = 1 \textit{target} = 1target=1或maxDoubles = 0 \textit{maxDoubles} = 0maxDoubles=0时，不能再执行除以2 22操作，需要将target \textit{target}target执行target − 1 \textit{target} - 1target−1次减1 11，将操作次数加target − 1 \textit{target} - 1target−1。

3. 上述操作结束之后，操作次数即为最少操作次数。

代码

classSolution{publicintminMoves(inttarget,intmaxDoubles){intmoves=0;while(target>1&&maxDoubles>0){if(target%2!=0){target--;}else{target/=2;maxDoubles--;}moves++;}moves+=target-1;returnmoves;}}

复杂度分析

• 时间复杂度：O ( min ⁡ ( log ⁡ target , maxDoubles ) ) O(\min(\log \textit{target}, \textit{maxDoubles}))O(min(logtarget,maxDoubles))，其中target \textit{target}target是给定的目标值，maxDoubles \textit{maxDoubles}maxDoubles是加倍操作次数上限。只有当加倍操作剩余次数大于0 00时才需要模拟反向操作过程，模拟过程中每次对target \textit{target}target的操作仅限于除以2 22或减1 11，不可能出现连续两次减1 11操作，且加倍操作次数不超过maxDoubles \textit{maxDoubles}maxDoubles，因此需要模拟的操作次数是O ( min ⁡ ( log ⁡ target , maxDoubles ) ) O(\min(\log \textit{target}, \textit{maxDoubles}))O(min(logtarget,maxDoubles))，每次操作的时间是O ( 1 ) O(1)O(1)。

• 空间复杂度：O ( 1 ) O(1)O(1)。