文章目錄題目標題和出處難度題目描述要求示例數(shù)據(jù)范圍解法思路和算法代碼復(fù)雜度分析題目標題和出處標題得到目標值的最少行動次數(shù)出處2139. 得到目標值的最少行動次數(shù)難度4 級題目描述要求你正在玩一個整數(shù)游戲。從整數(shù)1 \texttt{1}1開始目標是得到整數(shù)target \texttt{target}target。在一次行動中你可以做下述兩種操作之一遞增將當前整數(shù)的值加1 \texttt{1}1即x \texttt{x}x變成x 1 \texttt{x} \texttt{1}x1。加倍使當前整數(shù)的值翻倍即x \texttt{x}x變成2 × x \texttt{2} \times \texttt{x}2×x?？梢允褂眠f增操作任意次數(shù)但是只能使用加倍操作至多maxDoubles \texttt{maxDoubles}maxDoubles次。給定兩個整數(shù)target \texttt{target}target和maxDoubles \texttt{maxDoubles}maxDoubles返回從1 \texttt{1}1開始得到target \texttt{target}target需要的最少行動次數(shù)。示例示例 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。數(shù)據(jù)范圍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則由于乘法的情況較為復(fù)雜因此需要考慮多種可能的情況。可以考慮反向操作每次反向操作可以將當前整數(shù)除以2 22或減1 11除以2 22的操作只有在當前整數(shù)是偶數(shù)且加倍操作剩余次數(shù)大于0 00的情況下才能執(zhí)行計算從target \textit{target}target到達1 11的最少反向操作次數(shù)反向操作過程中如果有除以2 22的操作則需要更新maxDoubles \textit{maxDoubles}maxDoubles。以下所說的操作均為反向操作。當target \textit{target}target是奇數(shù)或maxDoubles 0 \textit{maxDoubles} 0maxDoubles0時只能將target \textit{target}target減1 11。當target \textit{target}target是偶數(shù)且maxDoubles 0 \textit{maxDoubles} 0maxDoubles0時可以將target \textit{target}target除以2 22并將maxDoubles \textit{maxDoubles}maxDoubles減1 11或?qū)arget \textit{target}target減1 11此時需要分別考慮兩種操作計算最少操作次數(shù)。對target \textit{target}target執(zhí)行一次除以2 22操作之后target \textit{target}target變成target 2 \dfrac{\textit{target}}{2}2target?等價于執(zhí)行target 2 \dfrac{\textit{target}}{2}2target?次減1 11操作因此和全部執(zhí)行減1 11操作相比執(zhí)行一次除以2 22操作可以將操作次數(shù)減少target 2 ? 1 \dfrac{\textit{target}}{2} - 12target??1次當target \textit{target}target越大時執(zhí)行除以2 22操作可以減少的操作次數(shù)越多。由于除以2 22操作的次數(shù)存在上限為了使操作次數(shù)最少應(yīng)該盡可能在target \textit{target}target大的時候執(zhí)行除以2 22操作。由于每次對target \textit{target}target執(zhí)行除以2 22或減1 11操作都會使target \textit{target}target減少因此應(yīng)該盡早執(zhí)行除以2 22操作。當target \textit{target}target是大于2 22的偶數(shù)且maxDoubles 0 \textit{maxDoubles} 0maxDoubles0時如果將target \textit{target}target執(zhí)行兩次減1 11再除以2 22則需要三次操作可以替換成等效的將target \textit{target}target除以2 22再減1 11只需要兩次操作且兩種情況都將maxDoubles \textit{maxDoubles}maxDoubles減1 11因此將target \textit{target}target除以2 22的情況下可以得到最少操作次數(shù)。根據(jù)上述分析可以使用貪心的思想模擬反向操作并計算最少操作次數(shù)。具體做法如下。當target 1 \textit{target} 1target1且maxDoubles 0 \textit{maxDoubles} 0maxDoubles0時如果target \textit{target}target是奇數(shù)則將target \textit{target}target減1 11如果target \textit{target}target是偶數(shù)則將target \textit{target}target除以2 22并將maxDoubles \textit{maxDoubles}maxDoubles減1 11每次操作之后將操作次數(shù)加1 11。重復(fù)該操作直到target 1 \textit{target} 1target1或maxDoubles 0 \textit{maxDoubles} 0maxDoubles0。當target 1 \textit{target} 1target1或maxDoubles 0 \textit{maxDoubles} 0maxDoubles0時不能再執(zhí)行除以2 22操作需要將target \textit{target}target執(zhí)行target ? 1 \textit{target} - 1target?1次減1 11將操作次數(shù)加target ? 1 \textit{target} - 1target?1。上述操作結(jié)束之后操作次數(shù)即為最少操作次數(shù)。代碼classSolution{publicintminMoves(inttarget,intmaxDoubles){intmoves0;while(target1maxDoubles0){if(target%2!0){target--;}else{target/2;maxDoubles--;}moves;}movestarget-1;returnmoves;}}復(fù)雜度分析時間復(fù)雜度O ( min ? ( log ? target , maxDoubles ) ) O(\min(\log \textit{target}, \textit{maxDoubles}))O(min(logtarget,maxDoubles))其中target \textit{target}target是給定的目標值maxDoubles \textit{maxDoubles}maxDoubles是加倍操作次數(shù)上限。只有當加倍操作剩余次數(shù)大于0 00時才需要模擬反向操作過程模擬過程中每次對target \textit{target}target的操作僅限于除以2 22或減1 11不可能出現(xiàn)連續(xù)兩次減1 11操作且加倍操作次數(shù)不超過maxDoubles \textit{maxDoubles}maxDoubles因此需要模擬的操作次數(shù)是O ( min ? ( log ? target , maxDoubles ) ) O(\min(\log \textit{target}, \textit{maxDoubles}))O(min(logtarget,maxDoubles))每次操作的時間是O ( 1 ) O(1)O(1)?？臻g復(fù)雜度O ( 1 ) O(1)O(1)。