Divide Two Integers (M)

題目

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3

Example 2:

Input: dividend = 7, divisor = -3
Output: -2

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: \([?2^{31}, 2^{31} ? 1]\). For the purpose of this problem, assume that your function returns \(2^{31} ? 1\) when the division result overflows.

題意

在不使用乘法、除法、取模操作的前提下，實作除法，若得到的商溢位Integer的范圍，則回傳Integer的最大值，

思路

首先要明確正負數除法的規則，經過實驗可得Java的規則是使得到的商盡可能接近0(即直接省去得到的負數商的小數部分)，說明商與除數的乘積的絕對值小于等于被除數的絕對值，在這個基礎上實作除法的演算法，

最直接的做法是讓被除數挨個減去(若正負數除法則為加上)除數，復雜度為\(O(N)\)但在商的絕對值很大的情況下會超時，

更高效方法的大致方向是：將除數和被除數都化為絕對值后，倍增除數，找到比被除數小的那個值，記錄倍增的次數n，\(2^n\)即是所求的商，復雜度為\(O(logN)\)，(當然具體實作更加復雜)

因為題目要求環境只能存盤int范圍的值，所以不使用long，也不使用與乘除相似的位運算，具體操作直接看代碼，

代碼實作

Java

class Solution {
    public int divide(int dividend, int divisor) {
        // 只有這一種情況會造成商溢位，先處理掉
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        // 記錄商的正負值
        boolean isMinus = ((dividend < 0) != (divisor < 0));
        
        // 如果除數或被除數中有一個是Integer.MIN_VALUE，那么取絕對值就會溢位
        // 所以全部轉化為負數進行處理
        dividend = dividend > 0 ? -dividend : dividend;
        divisor = divisor > 0 ? -divisor : divisor;
		
        // 如果被除數已經比除數大(因為全是負數)，商只可能為0
        if (dividend > divisor) {
            return 0;
        }

        int quotient = 1;		// 商的絕對值
        int d = divisor;		// 當前需要在除數上累加的值
        int sum = divisor;		// 累加后的除數
        int count = 1;			// 當前累加值對應的divisor個數，d = count * divisor

        while (true) {
            // 當累加后的除數絕對值仍小于等于被除數時，則進行累加
            // sum + d < 0 的判斷是為了防止sum+d后溢位
            if (sum + d < 0 && sum + d >= dividend) {
                sum += d;				// 將待加值累加到除數上
                d += d;					// 待加值自我累加
                quotient += count;		// 更新商
                count += count;			
            } else {
                // 當且僅當加上待加值后的除數絕對值大于被除數，且待加值正好為最原始除數時才跳出
                // 因為這時累加后的除數已經達到小于等于被除數的最大值，多加一個除數都不行
                if (d == divisor) {
                    break;		
                } else {
                    // 重置待加值，以盡可能使累加除數的絕對值接近被除數
                    d = divisor;
                    count = 1;
                }
            }
        }
		
        // 最后注意商的正負號
        return isMinus ? -quotient : quotient;
    }
}

JavaScript

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function (dividend, divisor) {
  if (dividend === -Math.pow(2, 31) && divisor === -1) {
    return Math.pow(2, 31) - 1
  }
  let isMinus = dividend < 0 !== divisor < 0
  dividend = Math.abs(dividend)
  divisor = Math.abs(divisor)
  let quotient = 0
  let count = 1
  let curDiv = divisor

  while (dividend >= divisor) {
    if (dividend >= curDiv) {
      dividend -= curDiv
      quotient += count
      count += count
      curDiv += curDiv
    } else {
      curDiv = divisor
      count = 1
    }
  }

  return isMinus ? -quotient : quotient
}

------------恢復內容結束------------

標籤：其他

上一篇：0028. Implement strStr() (E)

下一篇：0030. Substring with Concatenation of All Words (H)