首页 > 代码库 > [LeetCode] 数学计算模拟类问题:除法和幂,注意越界问题。题 Pow(x, n) ,Divide Two Integers
[LeetCode] 数学计算模拟类问题:除法和幂,注意越界问题。题 Pow(x, n) ,Divide Two Integers
引言
数学计算的模拟类题目,往往是要求实现某种计算(比如两数相除),实现的过程中会有所限定,比如不允许乘法等等。
这类题目首先要注意计算过程中本身的特殊情况。比如求相除,则必须首先反映过来除数不能为0。
其次要记得考虑负数的情况,如果计算范围不单单是整数,还要考虑double的比较方式。
最后要注意越界情况,这个是最容易犯错的,只能具体问题具体分析。
例题 1 Pow(x, n)
Implement pow(x, n).
class Solution { public: double pow(double x, int n) { } };
这道题目我在 面试题 11,求double类型的n次幂(double数值的比较不能用==,求幂的logN复杂度方法) 中写过。
要注意的就是:
1) 0 的 0 次幂无意义。
2) 0的负数次幂无意义。
3) 所有非零数的 0次幂为1。
4) double x 判断是否为0时,不能用简单的 == 0判断,因为double类型总是存在误差。
实现,时间复杂度 log(n),"n"是函数中的参数n
class Solution { public: double pow(double x, int n) { if(n == 0) return 1; if(equal(x, 0.0)) return 0; return (n > 0 ? powCore(x, n) : 1.0/powCore(x, -n)); } private: bool equal(double x, double y){ if((x-y) < 0.00001 && (x-y) > -0.00001) return true; return false; } double powCore(double x, int n){ if(n == 0) return 1; double tmp = pow(x, n/2); return tmp*tmp*(n&1 ? x : 1); } };
例题 2 Divide Two Integers
Divide two integers without using multiplication, division and mod operator.
class Solution { public: int divide(int dividend, int divisor) { } };
这道题相较于前一道稍复杂些。首先考虑divisor为0的情况,再考虑负数的情况。
接着考虑解体方法,由于乘除都不能用,只能用加法,而如果直接累加自然会超时。我的思路是定义一个长32的数组path[32],path[0] = divisor, path[i] = path[i-1] + path[i-1]。path[32]不一定全被填满,当计算出path[i] > dividend时,path[i] 就不会被记录。由于path[i] 有大于 dividend的可能,因此临时存储计算结果的数定义为long long。
然后用这个path[32] 去凑成dividend,相除结果其实就是凑得过程中 1 << i 的相加(i 是 path[] 的 index)。
第一版代码如下:
class Solution { public: int divide(int dividend, int divisor) { if(divisor == 0) return 0; if(dividend == 0) return 0; bool minus1 = false, minus2 = false, minus = false; if(divisor < 0){ divisor = (0 - divisor); minus1 = true; } if(dividend < 0){ dividend = (0 - dividend); minus2 = true; } minus = (minus1 ^ minus2); //结果的正负号, minus若为true,结果就添加负号。 if(dividend < divisor) return 0; long long cache = divisor; int* path = new int[32]; int ind = 0; for(; cache <= dividend; path[ind] = (int)cache, ++ind, cache += cache); //填充path[] cache = path[--ind]; int res = 1 << ind; //从path的最末尾开始凑dividend while(ind >= 0){ if(cache == dividend) return minus ? (0-res) : res; if(cache > dividend){ cache -= path[ind]; res -= 1 << ind; } for(--ind; ind >= 0 && cache < dividend; cache += path[ind], res += 1 << ind); } return minus ? (0-res) : res; } };
这版代码在执行 sln.divide(-1010369383, -2147483648) 出现错误。
原因在于 开始的
dividend = (0 - dividend);
补码表示下,int下限绝对值比上限绝对值大1。dividend = -2147483648时,0-dividend 结果并非是2147483648。因此dividend 和 divisor的绝对值应该用unsigned int 表示。
考虑到这一点,当dividend = -2147483648 时,res 和 path 也有越过 int上限的可能,因此它们应该定义为 unisgned int。
改进后的代码,改动了一些参数的 格式,这次AC了。
class Solution { public: int divide(int dividend, int divisor) { if(divisor == 0) return 0; if(dividend == 0) return 0; bool minus1 = false, minus2 = false, minus = false; unsigned int divd, divr; if(divisor < 0){ divr = (0 - divisor); minus1 = true; }else{ divr = divisor; } if(dividend < 0){ divd = (0 - dividend); minus2 = true; }else{ divd = dividend; } minus = (minus1 ^ minus2); //结果的正负号, minus若为true,结果就添加负号。 if(divd < divr) return 0; long long cache = divr; unsigned int* path = new unsigned int[32]; int ind = 0; for(; cache <= divd; path[ind] = (unsigned int)cache, ++ind, cache += cache); //填充path[] cache = path[--ind]; unsigned int res = 1 << ind; //从path的最末尾开始凑dividend while(ind >= 0){ if(cache == divd) return minus ? (0-res) : res; if(cache > divd){ cache -= path[ind]; res -= 1 << ind; } for(--ind; ind >= 0 && cache < divd; cache += path[ind], res += 1 << ind); } return minus ? (0-res) : res; } };