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

文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题得到目标值的最少行动次数出处2139. 得到目标值的最少行动次数难度4 级题目描述要求你正在玩一个整数游戏。从整数1 \texttt{1}1开始目标是得到整数target \texttt{target}target。在一次行动中你可以做下述两种操作之一递增将当前整数的值加1 \texttt{1}1即x \texttt{x}x变成x 1 \texttt{x} \texttt{1}x1。加倍使当前整数的值翻倍即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≤1090 ≤ 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} 0maxDoubles0时只能将target \textit{target}target减1 11。当target \textit{target}target是偶数且maxDoubles 0 \textit{maxDoubles} 0maxDoubles0时可以将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} 0maxDoubles0时如果将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的情况下可以得到最少操作次数。根据上述分析可以使用贪心的思想模拟反向操作并计算最少操作次数。具体做法如下。当target 1 \textit{target} 1target1且maxDoubles 0 \textit{maxDoubles} 0maxDoubles0时如果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} 1target1或maxDoubles 0 \textit{maxDoubles} 0maxDoubles0。当target 1 \textit{target} 1target1或maxDoubles 0 \textit{maxDoubles} 0maxDoubles0时不能再执行除以2 22操作需要将target \textit{target}target执行target − 1 \textit{target} - 1target−1次减1 11将操作次数加target − 1 \textit{target} - 1target−1。上述操作结束之后操作次数即为最少操作次数。代码classSolution{publicintminMoves(inttarget,intmaxDoubles){intmoves0;while(target1maxDoubles0){if(target%2!0){target--;}else{target/2;maxDoubles--;}moves;}movestarget-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)。