零、写在前面
这个系列不经常更新,主要看今天这个题目有点意思,我们一起看一看,主要知识点在
【第04题】给定 a 和 b,问 a 能否被 b 整除 | if 语句 和 条件运算符的应用https://blog.csdn.net/WhereIsHeroFrom/article/details/118198012
https://blog.csdn.net/WhereIsHeroFrom/article/details/118198012
顺带吐槽,英雄哥给的题有时候有点感觉和知识点不太对应-.-
一、主要知识点
1.if else语句 以及三目运算符
if(a == 0) .... else if( a== 1) .... else ... return a > b ? a : b ;
2 .数据的表示(补充知识点)
平时我们正常的自然数表示是 13154,-456456。但是计算机不能像我们这样表示,因为都是二进制,所以正负有符号位,最高位有符号位表示正负,其中0为正,1为负。
对于正数。比如1 就是00000001。
对于负数呢?比如-1,有三种表示方式,分别叫做原码、反码、补码。分别是10000001,11111110,11111111 。
其中源码就是加一个符号位,反码是除了符号位以外取反,补码是除了符号位以外取反加1,其中 规定100000000为最小的负数,这里就是-2^7。(要考知识点)
二、课后习题
两数相减
29. 两数相除
https://leetcode-cn.com/problems/divide-two-integers/
思路1
之前看英雄哥的文章有提过,这里题目说不让你用你就不用啊,作为一个入门玩家,能过就行,管他让不让用。冲就完了。但是!但是啊!!!注意上面的表示范围 对应int的数据范围就是-2^31 ~ 2^31 -1 。负数比正数大1一个 这里会溢出所以做判断就行了。
int MIN_INT = -2147483648;//最小的int变量大小 int divide(int dividend, int divisor){ if(dividend == MIN_INT) //判断溢出 if(divisor == -1) return -(MIN_INT + 1);//溢出,返回指定大小 if(divisor == MIN_INT) //除数为最小的解决方法 if(dividend == MIN_INT) return 1; else return 0; return dividend / divisor; }
结果分析
大家都开开心心的,多好???
思路2
俗话说,不作死,枉为人啊。作为一个已经站在门口的玩家,我还是得看看这题该咋写。
、 第一个思路必然是暴力,从0到最大值枚举,超时。。。。wtf?
换个思路,其实也没换。。。超时那就减少时间复杂度嘛,最容易想到的就是二分查找最终结果。说干就干。其中最开始进行操作数的转换,变成两个负数。(因为负数范围大!)
熟悉二分的同学肯定知道有左右范围,然后根据中间范围的值进行判断来修改范围,最终得到最终的结果,判断的时候为了防止数据溢出,我们把加法改成减法就不会溢出(负数-负数)怎么溢出?你说说。。(看不懂这部分的建议看完英雄哥的二次幂之后再来观摩)
int MIN_INT = -2147483648; //int的最小值 int MAX_INT = 2147483647; //int最大值 bool quickadd(int y, int z, int x){ //判断z*y >= x? int result = 0,add = y; while(z){ //二分快速乘 if(z & 1){ if(result < x - add) return false;//保证 result + add >= x result += add; } if(z != 1){ if(add < x - add) return false; // 保证add + add >= x add += add; } z >>= 1; } return true; } int divide(int dividend, int divisor){ //异常处理 if(dividend == MIN_INT) //被除数的溢出处理 if(divisor == -1) return -(MIN_INT + 1);//超出正整数表示范围 返回2^31-1 else if(divisor == 1) return MIN_INT; //除1直接返回相应的值 if(divisor == MIN_INT) //除数的溢出处理 if(dividend == MIN_INT) return 1; //两个想等的数字相除 返回1 else return 0; //其它情况都是返回0 的 int flag = 0;//记录正负 if(dividend > 0) dividend = -dividend,flag++;//统一处理为负数 if(divisor > 0) divisor = -divisor,flag ++; //统一处理为负数 int a = 0,b = MAX_INT,ans = 0; //定义左右点和结果 while(a <= b){ int mid = a + ((b - a) >> 1); if(quickadd(divisor,mid,dividend)){ printf("d"); ans = mid; //记录最大的满足乘法的值 if(mid == MAX_INT) break; a = mid + 1; } else b = mid -1; } return flag & 1 ? -ans :ans; //看着flag&1高级。其实返回的结果就是flag%2. }
结果分析
凑合玩吧。。
写在最后
其实最近一直在产出东西,但是没有得到一些反馈建议,英雄哥的这种搭伙一起coding的模式是能双方都能得到成长的。希望以后大家看我的文章能够给出一些建议和修改意见,如果看不懂也希望能在群里@我,我会根据疑问进行文章修改,这样才是一个良性的循环。
这个系列是不经常更新系列,因为这个比较基础,很多题解写出来没什么感觉,所以见谅。当然如果我看到有意思的题或者是大家疑问多的某一天就会写写文章跟大家分享。如果有什么需求同样可以私信或者找你任何能联系到我的方式进行交流沟通,加油,别放弃!