不用乘法、除法、取余操作,將兩個數相除。
如果它溢出了,返回MAX_INT
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
一心撲到了遞歸上,可惜沒能寫出來…………煩躁至極還是找了別人的答案……
class Solution {
public:
int divide(int dividend, int divisor) {
if(!divisor) return INT_MAX;
if(divisor == 1) return dividend;
if(divisor == -1) {
if(dividend == INT_MIN) return INT_MAX;
else return -dividend;
}
bool s1 = dividend < 0;
bool s2 = divisor < 0;
unsigned int nom = s1 ? -dividend : dividend;
unsigned int den = s2 ? -divisor : divisor;
unsigned int rem = 0;
unsigned int quot = 0;
for(int i = 31; i >= 0; --i) {
rem <<= 1;
rem |= (nom >> i) & 1;
if(rem >= den) {
rem -= den;
quot |= (1 << i);
}
}
return s1^s2? -quot : quot;
}
};
再來兩個代碼……(慚愧……)
public class Solution
{
public int Divide(int dividend, int divisor)
{
//1. check overflow: 2 ways of over flow 1) 0 divisor; 2) int.Minvalue/(-1)
if (divisor == 0 || dividend == int.MinValue && divisor == -1) return int.MaxValue;
//2. calculate sign
int sign = dividend > 0 ^ divisor > 0 ? -1 : 1, result = 0;
long m = Math.Abs((long)dividend), n = Math.Abs((long)divisor);
//3. looping from 1 to possible maximum pow(2, x) to add into result
while (m >= n)
{
long subN = n;
for (int subCount = 1; m >= subN; subCount <<= 1, subN <<= 1)
{
m -= subN;
result += subCount;
}
}
return result * sign;
}
}
public class Solution
{
public int Divide(int dividend, int divisor)
{
if (divisor == 1) return dividend;
if (dividend == int.MinValue && divisor == -1 || divisor == 0) return int.MaxValue;
int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1, result = 0;
long dvd = Math.Abs((long)dividend), dvs = Math.Abs((long)divisor);
while (dvd >= dvs)
{
long sub = dvs;
int subR = 1;
while (dvd >= (sub << 1))
{ sub <<= 1; subR <<= 1; }
dvd -= sub;
result += subR;
}
return sign * result;
}
}