文章目錄題目標題和出處難度題目描述要求示例數(shù)據(jù)范圍解法思路和算法代碼復雜度分析題目標題和出處標題得到目標值的最少行動次數(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則由于乘法的情況較為復雜因此需要考慮多種可能的情況。可以考慮反向操作每次反向操作可以將當前整數(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。重復該操作直到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;}}復雜度分析時間復雜度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復雜度O ( 1 ) O(1)O(1)。