文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题坏了的计算器出处991. 坏了的计算器难度4 级题目描述要求有一台坏计算器初始时显示整数startValue \texttt{startValue}startValue可以执行以下两种操作双倍将显示屏上的数字乘以2 \texttt{2}2递减将显示屏上的数字减1 \texttt{1}1。给定两个整数startValue \texttt{startValue}startValue和target \texttt{target}target返回在计算器上显示数字target \texttt{target}target所需的最小操作数。示例示例 1输入startValue 2, target 3 \texttt{startValue 2, target 3}startValue 2, target 3输出2 \texttt{2}2解释先双倍再递减2 → 4 → 3 \texttt{2} \rightarrow \texttt{4} \rightarrow \texttt{3}2→4→3。示例 2输入startValue 5, target 8 \texttt{startValue 5, target 8}startValue 5, target 8输出2 \texttt{2}2解释先递减再双倍5 → 4 → 8 \texttt{5} \rightarrow \texttt{4} \rightarrow \texttt{8}5→4→8。示例 3输入startValue 3, target 10 \texttt{startValue 3, target 10}startValue 3, target 10输出3 \texttt{3}3解释先双倍再递减最后双倍3 → 6 → 5 → 10 \texttt{3} \rightarrow \texttt{6} \rightarrow \texttt{5} \rightarrow \texttt{10}3→6→5→10。数据范围1 ≤ startValue, target ≤ 10 9 \texttt{1} \le \texttt{startValue, target} \le \texttt{10}^\texttt{9}1≤startValue, target≤109解法思路和算法如果正向计算如何从startValue \textit{startValue}startValue到达target \textit{target}target则由于乘法的情况较为复杂因此需要考虑多种可能的情况。可以考虑反向操作每次反向操作可以将当前整数除以2 22或加1 11除以2 22的操作只有在当前整数是偶数的情况下才能执行计算从target \textit{target}target到达startValue \textit{startValue}startValue的最小反向操作数。以下所说的操作均为反向操作。当target \textit{target}target是奇数时只能将target \textit{target}target加1 11。当target \textit{target}target是偶数时可以将target \textit{target}target除以2 22或加1 11因此需要对target \textit{target}target是偶数的情况分别考虑两种操作计算最小操作数。如果startValue target \textit{startValue} \textit{target}startValuetarget则当target \textit{target}target是偶数时应将target \textit{target}target除以2 22。如果将target \textit{target}target执行两次加1 11再除以2 22则需要三次操作可以替换成等效的将target \textit{target}target除以2 22再加1 11只需要两次操作因此将target \textit{target}target除以2 22的情况下可以得到最小操作数。如果startValue target \textit{startValue} \textit{target}startValuetarget则将target \textit{target}target加1 11直到等于startValue \textit{startValue}startValue是操作数最小的做法。如果当target \textit{target}target是偶数时将target \textit{target}target除以2 22则会将target \textit{target}target减小到达startValue \textit{startValue}startValue需要更多次操作。根据上述分析可以使用贪心的思想模拟反向操作并计算最小操作数。具体做法如下。当startValue target \textit{startValue} \textit{target}startValuetarget时如果target \textit{target}target是奇数则将target \textit{target}target加1 11如果target \textit{target}target是偶数则将target \textit{target}target除以2 22每次操作之后将操作数加1 11。重复该操作直到startValue ≥ target \textit{startValue} \ge \textit{target}startValue≥target。当startValue ≥ target \textit{startValue} \ge \textit{target}startValue≥target时需要将target \textit{target}target执行startValue − target \textit{startValue} - \textit{target}startValue−target次加1 11将操作数加startValue − target \textit{startValue} - \textit{target}startValue−target。上述操作结束之后操作数即为最小操作数。代码classSolution{publicintbrokenCalc(intstartValue,inttarget){intoperations0;while(startValuetarget){if(target%2!0){target;}else{target/2;}operations;}operationsstartValue-target;returnoperations;}}复杂度分析时间复杂度O ( log ⁡ target ) O(\log \textit{target})O(logtarget)其中target \textit{target}target是给定的目标值。每次对target \textit{target}target的操作仅限于除以2 22或加1 11由于不可能出现连续两次加1 11操作因此操作次数是O ( log ⁡ target ) O(\log \textit{target})O(logtarget)每次操作的时间是O ( 1 ) O(1)O(1)。空间复杂度O ( 1 ) O(1)O(1)。