筆試題42. LeetCode OJ (29)

題目意思清晰明了：求兩個數的商，不能使用乘法，除法或者求模運算等等。看似很簡單的一道題，可是在排行榜上的正確率卻是最低的一道，原因是情況很復雜，邊界很難控制。需要考慮到的細節特別多，如：正負號，除數和被除數的取值，還有就是越界情況。其中越界情況最難考慮到，我也給拉低這道題的正確率增加了一份”功勞“，真的測試了好幾遍才將條件考慮全面，我的代碼中寫有很多注釋(大部分以測試用例形式給出)可以幫助大家分析特定情況，這類型的題目沒有很強的技巧，唯一需要注意的就是”細心“。對了，還有一個問題就是如何不使用乘除法以及求模運算求商。我的思路是采用移位運算(其實是一種特殊的乘法)舉個例子吧：

如 ：23/4

(4<<3)= 32 > 23

(4<<2)=16 < 23

那麼商在 2^2(4)~2^3(8)之間，最小為 4(第一部分)

23-4*2^2 = 23 - 16 = 7

4<<1 = 8 > 7 , 但是 4 < 7 所以可以求出第二部分的商為 1

綜上所述，23/4 = 5(商為5)

如果還不理解那就參看我的代碼吧，代碼如下：

class Solution {
public:
	int divide(int dividend, int divisor)
	{
		//求兩個數的商
		//1.被除數為0
		if (divisor == 0)
		{//不合法的數
			return 0;
		}
		//2.除數為 0
		if (dividend == 0)
		{//除數為0
			return 0;
		}
		//3.被除數為1
		if (divisor == 1)
		{
			return dividend;
		}
		//4.被除數為2
		else if (divisor == 2)
		{
			return dividend >> 1;
		}
		//5.考慮溢出問題,正數溢出或者負數溢出
		double maxint = pow(2, 31) - 1;
		if (dividend - maxint > 0.000001)
		{
			dividend = int(maxint);
		}
		if (divisor - maxint > 0.000001)
		{
			divisor = int(maxint);
		}
		if(dividend < maxint*(-1) && divisor < maxint*(-1))
		{// 例如：-2147483648 / -2147483648  
		    return 1;
		}
		if (dividend < maxint*(-1))
		{
			dividend = maxint*(-1);
		}
		if (divisor < maxint*(-1))
		{//被除數越界 例如：(1~2147483647) / -2147483648
			//divisor = maxint*(-1);
			return 0;
		}
		//6.考慮正負號
		int minus = 1; //商是否為負數
		if (dividend < 0 && divisor < 0)
		{
			dividend *= -1;
			divisor *= -1;
			if (divisor > dividend)
			{
				return 0;
			}
		}
		else
		{
			if (dividend < 0)
			{
				dividend *= -1;
				minus = -1;
			}
			if (divisor < 0)
			{
				divisor *= -1;
				minus = -1;
			}
		}
		if (dividend == divisor)
		{   //例如： 1 / -1
			return 1*minus;
		}
		//7.被除數為1
		if (divisor == 1)
		{   //例如： -1 / -1
			return dividend;
		}
		else if (divisor == 2)
		{ //例如： -6 / -2
			return dividend >> 1;
		}
		//8.開始求商 25 / 4   -> 6   4<<2--16  25  4<<3--32  所以，商在4~8之間
		int left = 0;
		int right = 1;
		int ret = 0;
		int mybeover = maxint / 2;
		while (dividend > divisor)
		{
			left = 0;
			right = 1;
			while ((divisor << right) < dividend)
			{
				if ((divisor << left) >= mybeover)
				{
					break;
				}
				++left;
				++right;
			}
			ret += 1 << left;
			dividend -= divisor << left;
		}
		return ret*minus;
	}
};