leetcode29

分手后的思念是犯贱 2022-08-09 03:13 94阅读 0赞

leetcode29------------Divide Two Integers

题目的意思是两数除法，但不使用乘法，除法，取模等运算符来做。

回想除法的最朴素思想：

即，当 **被除数>除数** 一直拿被除数减去除数，能减去除数的**次数**为两数相除的结果。

根据这个思想，我们很容易写出伪代码：

while(被除数>除数)

被除数 -= 除数

count ++

最终的count为我们所要的结果。

但是，我们考虑最坏情况：当被除数是INT\_MAX，除数是1，那么刚刚的代码就要做（2^31-1）次，即2147483647次减法，结果是超时.

那么有一个做法就是通过左移操作减少减法的次数，但事实上循环的次数并没有减少。

左移操作一次相当于乘以2，那么左移N次就相当于乘以2^N。

在这道题上，我们每次减去2^(N) \* 除数，再将上述count 每次加上 1<<2^N次方，就能大大缩减做减法的次数。

左移操作也解决了题目要求不能使用乘法的限制。

这个N就可以通过内循环左移比较来判断。

具体代码：

class Solution {
    public:
    	int divide(int dividend, int divisor) {
    		//记录结果符号
    		int flag = 1;
    		if (dividend < 0)
    			flag =-flag;
    		if (divisor < 0)
    			flag =-flag;
    		//对被除数和除数分别取绝对值计算，并保存在long long变量中以防止溢出
    		long long num1 = abs((long long)dividend);
    		long long num2 = abs((long long)divisor);
    		//两种特殊情况
    		if (num1 < num2)
    			return 0;
    		if (divisor == 0)
    			return INT_MAX;
    		long long  result = 0;//结果保存在long long中来处理 INT_MAX和INT_MIN
    		while (num1 >= num2)
    		{
    			long long temp = num2;
    			int count = 0;
    			while (temp <= num1)
    			{
    				temp = temp << 1;
    				count++;
    			}
    			result = result + ((long long)1 << (count - 1));//此处的1需要强制转换为long long，否则默认超过INT_MAX 后溢出
    			num1 = num1 - (num2 << (count - 1));//被除数每次减去 2^(count-1)*除数
    		}
    		//处理溢出情况
    		if (flag == 1 && result > INT_MAX)
    			return INT_MAX;
    		if (flag == -1 && result > INT_MAX)
    			return INT_MIN;
    		return result*flag;
    	}
    };