0029. 兩數相除 · ttttt

# 0029. 兩數相除 ## 題目地址(29. 兩數相除) <https://leetcode-cn.com/problems/divide-two-integers/> ## 題目描述 ``` <pre class="calibre18">``` 給定兩個整數，被除數 dividend 和除數 divisor。將兩數相除，要求不使用乘法、除法和 mod 運算符。返回被除數 dividend 除以除數 divisor 得到的商。整數除法的結果應當截去（truncate）其小數部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2 示例 1: 輸入: dividend = 10, divisor = 3 輸出: 3 解釋: 10/3 = truncate(3.33333..) = truncate(3) = 3 示例 2: 輸入: dividend = 7, divisor = -3 輸出: -2 解釋: 7/-3 = truncate(-2.33333..) = -2 提示：被除數和除數均為 32 位有符號整數。除數不為 0。假設我們的環境只能存儲 32 位有符號整數，其數值范圍是 [?231, 231 ? 1]。本題中，如果除法結果溢出，則返回 231 ? 1。 ``` ``` ## 前置知識 - 二分法 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路符合直覺的做法是，減數一次一次減去被減數，不斷更新差，直到差小于0，我們減了多少次，結果就是多少。核心代碼： ``` <pre class="calibre18">``` let acc = divisor; let count = 0; while (dividend - acc >= 0) { acc += divisor; count++; } return count; ``` ``` 這種做法簡單直觀，但是性能卻比較差. 下面來介紹一種性能更好的方法。 ![](https://img.kancloud.cn/70/7d/707d53194424e817c1ecd05c817d9ed4_830x767.jpg) 通過上面這樣的分析，我們直到可以使用二分法來解決，性能有很大的提升。 ## 關鍵點解析 - [二分查找](binary-search.html) - 正負數的判斷中，這樣判斷更簡單。 ``` <pre class="calibre18">``` const isNegative = dividend > 0 !== divisor > 0; ``` ``` 或者利用異或： ``` <pre class="calibre18">``` const isNegative = dividend ^ divisor < 0; ``` ``` ## 代碼 - 語言支持：JS，Python3 ``` <pre class="calibre18">``` /* * @lc app=leetcode id=29 lang=javascript * * [29] Divide Two Integers */ /** * @param {number} dividend * @param {number} divisor * @return {number} */ var divide = function(dividend, divisor) { if (divisor === 1) return dividend; // 這種方法很巧妙，即符號相同則為正，不同則為負 const isNegative = dividend > 0 !== divisor > 0; const MAX_INTERGER = Math.pow(2, 31); const res = helper(Math.abs(dividend), Math.abs(divisor)); // overflow if (res > MAX_INTERGER - 1 || res < -1 * MAX_INTERGER) { return MAX_INTERGER - 1; } return isNegative ? -1 * res : res; }; function helper(dividend, divisor) { // 二分法 if (dividend <= 0) return 0; if (dividend < divisor) return 0; if (divisor === 1) return dividend; let acc = 2 * divisor; let count = 1; while (dividend - acc > 0) { acc += acc; count += count; } // 直接使用位移運算，比如acc >> 1會有問題 const last = dividend - Math.floor(acc / 2); return count + helper(last, divisor); } ``` ``` Python3 Code: ``` <pre class="calibre18">``` class Solution: def divide(self, dividend: int, divisor: int) -> int: """ 二分法 :param int divisor :param int dividend :return int """ # 錯誤處理 if divisor == 0: raise ZeroDivisionError if abs(divisor) == 1: result = dividend if 1 == divisor else -dividend return min(2**31-1, max(-2**31, result)) # 確定結果的符號 sign = ((dividend >= 0) == (divisor >= 0)) result = 0 # abs也可以直接寫在while條件中，不過可能會多計算幾次 _divisor = abs(divisor) _dividend = abs(dividend) while _divisor <= _dividend: r, _dividend = self._multi_divide(_divisor, _dividend) result += r result = result if sign else -result # 注意返回值不能超過32位有符號數的表示范圍 return min(2**31-1, max(-2**31, result)) def _multi_divide(self, divisor, dividend): """ 翻倍除法，如果可以被除，則下一步除數翻倍，直至除數大于被除數，返回商加總的結果與被除數的剩余值；這里就不做異常處理了； :param int divisor :param int dividend :return tuple result, left_dividend """ result = 0 times_count = 1 while divisor <= dividend: dividend -= divisor result += times_count times_count += times_count divisor += divisor return result, dividend ``` ``` **復雜度分析** - 時間復雜度：O(logN)O(logN)O(logN) - 空間復雜度：O(1)O(1)O(1) ## 相關題目 - [875.koko-eating-bananas](875.koko-eating-bananas.html) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)