本文主要是介绍#991双倍或递减得到某数的最小操作数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
#991双倍或递减得到某数的最小操作数
一、题目
难度:中等
在显示着数字的坏计算器上,我们可以执行以下两种操作:
双倍(Double):将显示屏上的数字乘 2;
递减(Decrement):将显示屏上的数字减 1 。
最初,计算器显示数字 X。
返回显示数字 Y 所需的最小操作数。
示例 1:
输入:X = 2, Y = 3
输出:2
解释:先进行双倍运算,然后再进行递减运算 {2 -> 4 -> 3}.
示例 2:
输入:X = 5, Y = 8
输出:2
解释:先递减,再双倍 {5 -> 4 -> 8}.
示例 3:
输入:X = 3, Y = 10
输出:3
解释:先双倍,然后递减,再双倍 {3 -> 6 -> 5 -> 10}.
示例 4:
输入:X = 1024, Y = 1
输出:1023
解释:执行递减运算 1023 次
提示:
1 <= X <= 10^9
1 <= Y <= 10^9
二、解题
1、逆向思维
(1)思路
除了对 X 执行乘 2 或 减 1 操作之外,我们也可以对 Y 执行除 2(当 Y 是偶数时)或者加 1 操作。
这样做的动机是我们可以总是贪心地执行除 2 操作:
当 Y 是偶数,如果先执行 2 次加法操作,再执行 1 次除法操作,我们可以通过先执行 1 次除法操作,再执行 1 次加法操作以使用更少的操作次数得到相同的结果 [(Y+2) / 2 vs Y/2 + 1]。(即如果是偶数先进行除法)
当 Y 是奇数,如果先执行 3 次加法操作,再执行 1 次除法操作,我们可以将其替代为顺次执行加法、除法、加法操作以使用更少的操作次数得到相同的结果 [(Y+3) / 2 vs (Y+1) / 2 + 1]。(即如果是偶奇数先进行加法)
(2)算法
当 Y 大于 X 时,如果它是奇数,我们执行加法操作,否则执行除法操作。之后,我们需要执行 X - Y 次加法操作以得到 X。
class Solution {public int brokenCalc(int X, int Y) {int account=0;while(Y>X){if(Y%2!=0){Y++;account++;}else{Y/=2;account++;}}return account+X-Y;}
}
执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:36.4 MB, 在所有 Java 提交中击败了56.41%的用户
- 时间复杂度: O(\log Y)O(logY)。
- 空间复杂度: O(1)O(1)。
2、正向思维
class Solution {public int brokenCalc(int X, int Y) {if(Y<=X) return X-Y;int cnt1=0;//先计算需要多少次乘法while(X<Y){X*=2;cnt1++;}if(X==Y) return cnt1;int r=X-Y;//计算减法次数,减法穿插在各次乘法中int cnt2=0;//计算 每次乘法前的减法次数for(int i=cnt1;i>=0;i--){int t=(int)Math.pow(2,i);int coeff=r/t;r=r%t;cnt2+=coeff;if(r==0) break;}return cnt1+cnt2;}
}
执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:36.4 MB, 在所有 Java 提交中击败了61.54%的用户
3、贪心算法
class Solution {public int brokenCalc(int X, int Y) {if (Y <= X) return X-Y;if (Y % 2 == 0) return 1 + brokenCalc(X, Y/2);else return 1 + brokenCalc(X, Y+1);}
}
复杂度分析:
- 时间复杂度:O(logY)
- 空间复杂度:O(1)
这篇关于#991双倍或递减得到某数的最小操作数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!