当前位置: 代码迷 >> 综合 >> LeetCode 29 Divide Two Integers (C,C++,Java,Python)
  详细解决方案

LeetCode 29 Divide Two Integers (C,C++,Java,Python)

热度:65   发布时间:2024-01-04 10:47:50.0

Problem:

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

Solution:

不能乘除就加减就行了,但是一个问题是加减有可能速度太慢,因此需要转换,由于任何一个数都能表示成二进制,所以有dividend=divisor*(a*2^1 + b*2^2 + ...... + m*2^k)

所以只要计算出所有divisor*2^k,然后减去即可。

题目大意:

给定两个整数,要求不用乘除法和取模运算,计算出a/b的值,当结果越界的时候输出INT最大值



Java源代码(260ms):

public class Solution {public int divide(int dividend, int divisor) {long a,b,flag=0,sum=0;long[] map=new long[33],times=new long[33];if(dividend<0 && divisor<0)flag=1;else if(dividend>0 && divisor>0)flag=1;a=Math.abs((long)dividend);b=Math.abs((long)divisor);int i=0;map[0]=b;times[0]=1;while(map[i]<=a){i++;map[i]=map[i-1]+map[i-1];times[i]=times[i-1]+times[i-1];}for(int j=i-1;j>=0;j--){while(a >= map[j]){a-=map[j];sum+=times[j];}}sum=flag==1?sum:-sum;if(sum>Integer.MAX_VALUE || sum<Integer.MIN_VALUE)return Integer.MAX_VALUE;return (int)sum;}
}

C语言源代码(4ms):

long long ABS(long long a){return a>0?a:-a;
}
int divide(int dividend, int divisor) {int i=0,j,flag=0;long long sum=0,a,b,map[33],times[33],STOP=1;STOP=((long long)2147483647)+1;if(divisor==0)return INT_MAX;if(dividend==0)return 0;if((dividend>0 && divisor>0) || (dividend<0 && divisor<0))flag=1;a=ABS((long long)dividend);b=ABS((long long)divisor);map[0]=b;times[0]=1;while(map[i] <= a && i<33){i++;map[i]=map[i-1]+map[i-1];times[i]=times[i-1]+times[i-1];}for(j=i-1;j>=0;j--){while(a >= map[j]){a-=map[j];sum+=times[j];}}sum=flag?sum:-sum;if(sum<INT_MIN || sum > INT_MAX)return INT_MAX;return (int)sum;
}

C++源代码(24ms):

class Solution {
public:int divide(int dividend, int divisor) {int i=0,j,flag=0;long long sum=0,a,b,map[33],times[33],STOP=1;STOP=STOP<<31;if(divisor==0)return INT_MAX;if((dividend>0 && divisor>0) || (dividend<0 && divisor<0))flag=1;a=abs((long long)dividend);b=abs((long long)divisor);map[0]=b;times[0]=1;while(map[i] <= STOP){i++;map[i]=map[i-1]+map[i-1];times[i]=times[i-1]+times[i-1];}for(j=i-1;j>=0;j--){while(a >= map[j]){a-=map[j];sum+=times[j];}}sum=flag?sum:-sum;if(sum<INT_MIN || sum > INT_MAX)return INT_MAX;return (int)sum;}
};

Python源代码(72ms):

class Solution:# @param {integer} dividend# @param {integer} divisor# @return {integer}def divide(self, dividend, divisor):flag=0if dividend>0 and divisor>0:flag=1elif dividend<0 and divisor<0:flag=1if dividend==0:return 0dividend=abs(dividend)divisor=abs(divisor)map=[0 for i in range(33)]times=[1 for i in range(33)]i=0map[0]=divisor;times[0]=1while map[i]<=dividend:i+=1map[i]=map[i-1]+map[i-1]times[i]=times[i-1]+times[i-1]j=i-1;sum=0while j>=0:while map[j]<=dividend:dividend-=map[j]sum+=times[j]j-=1sum = -sum if flag==0 else sumif sum>2147483647:return 2147483647return sum


  相关解决方案