个人 申请域名做网站,腾讯云建站多少钱,如何建微信公众号平台,黔南网站建设解题思路#xff1a; 1.获取信息#xff1a; 给定两个整数#xff0c;一个除数#xff0c;一个被除数#xff0c;要求返回商#xff08;商取整数#xff09; 限制条件#xff1a;#xff08;1#xff09;不能使用乘法#xff0c;除法和取余运算 #xff08;2#…解题思路 1.获取信息 给定两个整数一个除数一个被除数要求返回商商取整数 限制条件1不能使用乘法除法和取余运算 2只能存储32位有符号整数 额外条件1除数不等于0 2INT_MIN除数被除数INT_MAX 2.分析题目 1不能使用乘法除法和取余运算 我们可以使用加法减法那么就可以想到快速乘算法 快速乘算法就是使用加法来模拟乘法的哦其中会用到右移运算符和quanzh哦 为了方便你理解我下面的各种方法我打算一反常态直接在这个环节讲解一下快速乘法是什么还会配图哦实在是很贴心但我只会说一下基本原理你可以思考一下该怎么和这道题结合起来
2只能存储32为有符号整数并且INT_MIN除数被除数INT_MAX 所以我们要考虑一下溢出的问题了那么我们想一下一个除法该怎么丧心病狂地溢出呢 你想一下我们是求商对吧在本题的条件下一个除法的商是不会大于它的被除数的吧因为都为整数嘛那么我们可以知道商一般不会溢出 那么造成溢出的情况就只有一些特殊的情况了如下两种溢出 1原则上溢出被除数等于INT_MIN而除数等于-1两者相除会大于INT_MAX所以会溢出 2运算过程中溢出因为使用了快速乘的算法我们在加的过程中可能会造成溢出这个溢出也与我所用方法有关因为我是使用二分查找法来查找一个合适的数来检验是否可以作为商难免有时候会溢出 这个时候就需要对溢出进行检验及时止损我用了以下两步来避免溢出 1第一步我们知道INT_MAXINT_MIN对吧那么我们就将除数和被除数全部变为负数用一个bool类型的变量来决定结果商的正负那么就不容易溢出 如果你有疑惑难道变成正数不行吗其实也行但是麻烦在遇到如 被除数等于INT_MIN除数大于1的情况变成正数肯定会溢出而且进行处理也特别麻烦 所以我们在思考的时候不要给自己增加太多的麻烦你要做的是简化问题而不是让这个问题变得更加麻烦给自己脑袋增加负担哦 2第二步 我们知道在快速乘中会使用加法来模拟乘法所以可以在加的过程中判断一下溢出 我在这里想不到说什么可以讲得明白我也不想长篇大论地来浪费你的精力所以我会在下面的方法中结合代码来帮助你理解我会怎么避免溢出可以期待一下你现在也可以自己想一下再到下面对答案哦 3.示例查验 示例1和示例2都没啥太大帮助也没有提示你什么我其他题的这个环节是很精彩的主要是这道题给我衬托得太没用了 4.尝试编写代码 这道题你可能看过很多的题解了你可能是百思不得其解的状态所以我还是打算换一种方式来帮助你理解我会用我初次看到这道题一直到我写出其他方法的过程来帮助你层层递进哦可以期待一下好了下面就开始了你要跟上咯 1暴力法这是我第一次写的办法最后的结果是超时了被打败了 思路除法的本质就是减法乘法的本质就是加法 所以我们可以用除数一直去减被除数直到被除数小于0或者用除数一直相加直到等于被除数最后得到的进行减法的次数或者进行加法的次数就是商了
下面就是代码的实现但是我这个方法并没有通过只是不想你思维跨度那么大让你摸不着头脑而已如果你也是这种方法没过哈哈那我们蛮有缘的嘛
class Solution {
public:int divide(int dividend, int divisor) {if(dividend0)return 0;//如果被除数为0直接返回0if(dividendINT_MIN){//如果被除数为INT_MINif(divisor1)return INT_MIN;if(divisor-1)return INT_MAX;}if(divisor1)return dividend;//如果除数为1返回被除数if(divisor-1)return -dividend;//如果除数为1返回被除数的相反数bool frontfalse;//分别记录除数和被除数的符号bool tailfalse;if(dividend0){fronttrue;dividend-dividend;};//将被除数和除数全部变为负数if(divisor0){tailtrue;divisor-divisor;}if(dividenddivisor)return 0;//这里它们都是负数了所以表示大小的关系不一样咯别搞错了如果被除数大于除数就返回0int resdivisor;//相加的结果int num1;//相加的次数if(dividend!INT_MIN){//如果被除数不等于INT_MINwhile(res!dividend-1res!dividend1res!dividend){//一直相加步直到满足条件退出循环resdivisor;num;}}else{//如果被除数等于INT_MINwhile(res!dividend1res!dividend){//一直相加直到不满足条件退出循环if(dividend-divisorres)return fronttail?num:-num;resdivisor;num;}}return (fronttail)?num:-num;//返回商}
}; 2二分查找法快速乘全部迭代法 优化思路我上面的暴力法超时了我就在想有没有什么办法可以进行优化 主要的问题是加法进行的次数太多了而且进行加法的方式的效率也太低了 所以我就使用了二分查找法和快速乘的法方法来进行书写 思路我们知道在本题的条件下商肯定是不会大于被除数的那么我们就在1到被除数的大小这个范围使用二分法来查找商即可 我们用二分法查找到一个数来作为商那我们需要对其进行检验吧 我们就使用快速乘求出商待检验的那个数乘除数的结果来对其进行检验无非就三种情况 1结果等于被除数直接返回那个数要考虑一下正负哦即可 2结果小于被除数说明那个数取小了就需要在右边的区间取数 3结果大于被除数说明那个数取大了就需要在左边的区间取数 接下来说重头戏快速乘怎么样在这道题里面实现 快速乘我们写一个自定义函数传入商二分法选取的那个数和除数返回它们的乘积 要考虑商的二进制因为要用到右移运算符嘛那么我们就需要考虑各个位数上的权重将正确的权重加到结果上去再让商每次右移一位直到商为0 我知道你肯定看不懂我说的啥意思即使你看懂了我上面快速乘算法的基本原理所以你可以结合我下面的代码好好理解一下我每行都会给出注释
class Solution {
public:int divide(int dividend, int divisor) {if(dividend0)return 0;//被除数如果为0返回0if(dividendINT_MIN){//如果被除数等于INT_MINif(divisor-1)return INT_MAX;if(divisor1)return INT_MIN;}bool signfalse;//一个bool类型的变量用来表示符号if(dividend0){dividend-dividend;sign!sign;};//将除数和被除数全部变为负数if(divisor0){divisor-divisor;sign!sign;};if(dividenddivisor)return 0;//这里被除数和除数已经全部为负数了所以比较关系不一样了如果被除数大于除数返回0int res0;//用来储存商int begin1;//二分查找法范围的下限int end;if(dividendINT_MIN)endINT_MAX;//二分查找法范围的上限else {end-dividend;}while(beginend){//循环继续条件int midbegin((end2)-(begin2));//求出中值if(quick(mid,divisor,dividend)){//quick用来判断乘积大小如果小于resmid;if(midINT_MAX)return sign?-mid:mid;beginmid1;}else{//如果大于endmid-1;}}return sign?-res:res;}
private:bool quick(int mid,int divisor,int dividend){//此时除数和被除数都为负数所以比较条件你要好好注意一下int res0,adddivisor;//add是指权重哦while(mid){if(mid1){//如果二进制的最后一位为1那么就可以将这一位加到res中了因为下一步就是右移一位舍弃掉这个1if(resdividend-add)return false;resadd;}if(mid!1){//这是在更新权重配合着上面那个if语句进行正确的加法比如末尾一位是二的零次方倒数第二位是二的一次方依次类推if(adddividend-add)return false;addadd;}mid1;}return true;}
}; 3二分查找法快速乘全部迭代版 就是把上面那个方法中用到递归的地方换成了迭代而已根本思路没变只是手法变了我就不写思路咯 也不写注释了考验一下你哈哈
class Solution {
public:int divide(int dividend, int divisor) {if(dividend0)return 0;if(dividendINT_MIN){if(divisor-1)return INT_MAX;if(divisor1)return INT_MIN;}bool signfalse;if(dividend0){dividend-dividend;sign!sign;};if(divisor0){divisor-divisor;sign!sign;};if(dividenddivisor)return 0;int res0;int begin1;int end;if(dividendINT_MIN)endINT_MAX;else {end-dividend;}resreverse(begin,end,divisor,dividend,res,sign);return sign?-res:res;}
private:bool quick(int mid,int divisor,int dividend,int res,int add){if(mid0)return true;if(mid1){if(resdividend-add)return false;resadd;}if(mid!1){if(adddividend-add)return false;addadd;}mid1;return quick(mid,divisor,dividend,res,add);}int reverse(int begin,int end,int divisor,int dividend,int res,bool sign){if(beginend)return res;int midbegin((end1)-(begin1));if(quick(mid,divisor,dividend,0,divisor)){resmid;if(midINT_MAX)return mid;beginmid1;}else{endmid-1;}return reverse(begin,end,divisor,dividend,res,sign);}
}; 4模拟二分查找法 优化思路 二分查找法已经很优秀了那还可不可以更加优秀呢 当然可以咯众所周知时间复杂度和空间复杂度是此消彼长的关系 那么我们可不可以牺牲空间复杂度来成就时间复杂度呢 于是这个办法就诞生了 思路我们通过用一个vector来模拟二分查找法 我们将商的二进制的各个位数对应的权重都存储在这个vector中 我们根据被除数的二进制的各个权重来决定要存多少个位数进入vector中 在逐个取出vector中的权重减去被除数来得出商 这个方法我受到的启发是力扣的那道数字转罗马数字那道题 以下是完整代码如果你没有看懂我的描述你可以结合代码中的注释好好理解一下
class Solution {
public:int divide(int dividend, int divisor) {if(dividend0)return 0;//被除数为0返回0if(dividendINT_MIN){//被除数为INT_MINif(divisor-1)return INT_MAX;if(divisor1)return INT_MIN;}bool signfalse;//一个符号用来记录正负if(dividend0){dividend-dividend;sign!sign;};//将被除数和除数全变成负数if(divisor0){divisor-divisor;sign!sign;};if(dividenddivisor)return 0;//此时被除数和除数全部是负数如果被除数大于除数返回0int res0;//商vectorinttable{divisor};//用来存储商的权重while(table.back()dividend-table.back())table.push_back(table.back()1);//根据被除数来决定商的权重for(int itable.size()-1;i0;i--){if(table[i]dividend){res(1i);//通过商的权重来得出商dividend-table[i];//被除数减去商的权重}}return sign?-res:res;}
};
以上就是这道题的解析希望能够帮到你给你提供便利而没有浪费你的时间和精力
我还是提一嘴纸上得来终觉浅绝知此事要躬行哦
晚安
