「leetcode」29.兩數相除

googollee 發布于2019-08-26 11:00 / 1490人閱讀

摘要：原題給定兩個整數，被除數和除數。將兩數相除，要求不使用乘法除法和運算符。返回被除數除以除數得到的商。右移位，等價于，除以的次方。當除以時，結果相較于除數會非常的小。我們使用循環逐漸減少右移的位數，逐漸逼近除數，當時等于，大于等于。

原題

給定兩個整數，被除數?dividend?和除數?divisor。將兩數相除，要求不使用乘法、除法和 mod 運算符。

返回被除數?dividend?除以除數?divisor?得到的商。

示例?1:

輸入: dividend = 10, divisor = 3
輸出: 3

示例?2:

輸入: dividend = 7, divisor = -3
輸出: -2

說明：

被除數和除數均為 32 位有符號整數。

除數不為?0。

假設我們的環境只能存儲 32 位有符號整數，其數值范圍是 [?2^31,? 2^31?? 1]。本題中，如果除法結果溢出，則返回 231?? 1。

思路

解題思路來自評論區的foxleezh大神。題目中明確不能使用/, 我們可以右移模擬除法，右移可以等價于下面的等式

右移1位，等價于，除以2的1次方。

右移2位，等價于，除以2的2次方。

右移3位，等價于，除以2的3次方。

a / 2 === a >> 1
a / 4 === a >> 2
a / 8 === a >> 3

被除數 / 除數 === 商……余數 等價于 ?? 被除數 === (商 * 除數) + 余數 等價于 ?? (被除數 - 余數) / 商 === 除數

假設，我們的被除數等于100，除數等于5。

根據等式(被除數 - 余數) / 商 == 除數，我們首先要找到，100除以多少最接近于除數（或者說，除以多少時會大于等于除數）。

當100除以2^31時，結果相較于除數會非常的小。我們使用循環逐漸減少右移的位數，逐漸逼近除數，當100 >>> 4（100 / 16）時等于6，大于等于5。

這時，我們可以肯定商是大于16（2的四次方）的某個數（或者說，100至少包含16個5）。

我們使用被除數 = 被除數 - 16 * 除數等于還剩下的沒有除干凈的數。目前還剩下20。我們再次使用上述的方法，再次逼近除數（獲取20里還有幾個5）。最終得到最后的結果。

代碼

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    
    // 判斷結果是否為負數
    const isNegative = (dividend ^ divisor) < 0
    
    // 統一按正數處理
    dividend = Math.abs(dividend)
    divisor = Math.abs(divisor)
    
    if (dividend === 0) {
        return 0
    }
    
    if (dividend === 2147483648 && divisor === 1) {
        // 避免結果溢出
        return isNegative ? -dividend/divisor : dividend/divisor - 1
    }
    
    let result = 0
    
    for (let i = 31; i >= 0; i--) {
        // 注意這里需要使用無符號右移
        if ((dividend >>> i) >= divisor) {
            result += Math.pow(2, i)
            dividend -= Math.pow(2, i) * divisor
        }
    }
    
    return isNegative ? -result : result
};

云服務器 GPU云服務器 python兩數相除兩數相 Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/106965.html

LeetCode29.兩數相除 JavaScript

摘要：給定兩個整數，被除數和除數。將兩數相除，要求不使用乘法除法和運算符。返回被除數除以除數得到的商。示例輸入輸出示例輸入輸出說明被除數和除數均為位有符號整數。假設我們的環境只能存儲位有符號整數，其數值范圍是。給定兩個整數，被除數 dividend和除數 divisor。將兩數相除，要求不使用乘法、除法和 mod 運算符。返回被除數 dividend 除以除數 divisor 得到的商。...

shiyang6017 2019-08-23 15:16 評論0 收藏0
6-9月技術文章匯總

摘要：分布式的管理和當我在談論架構時我在談啥狀態碼詳解無狀態協議和請求支持哪些方法分層協議棧有哪些數據結構運用場景說說你常用的命令為什么要有包裝類面向對象的特征是啥是啥有什么好處系統設計工程在線診斷系統設計與實現索引背后的數據結構及算法原理軟技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】當我在談論RestFul架構時我在談啥？...

miya 2019-07-30 18:03 評論0 收藏0
兩數相除——不允許使用高級運算

摘要：兩數相除不允許使用高級運算實現兩整數相除，不允許使用乘法除法和取余運算。如果左移一位的除數過大，除數還原。注意處理除法運算中正負號的問題。代碼本題以及其它題目代碼地址地址兩數相除——不允許使用高級運算 Divide Two Integers 實現兩整數相除，不允許使用乘法、除法、和取余運算。如果結果溢出（int范圍為-2147483648 ~ 2147483647），返回MAX_...

_Zhao 2019-07-30 14:26 評論0 收藏0
leetcode29 Divide Two Integers

摘要：題目要求在不使用乘法，除法和求余操作的情況下，計算兩個整數相除的結果。如果溢出了，則返回最大值。在這里核心思路是使用逆向二分法和遞歸的思路來進行計算。在這里我們使用取值范圍更廣的來處理數值溢出的場景。題目要求 Divide two integers without using multiplication, division and mod operator. If it is o...

cnio 2019-08-16 10:32 評論0 收藏0
leetcode 29 Divide Two Integers

摘要：很容易想到，我們每次用被除數減去除數，進行減法的次數就是最終結果。這道題的采取了一種類似二分查找的思想。除了這些，這道題還要注意一些邊界情況的判斷，例如除數或被除數為，值溢出等。題目詳情 Divide two integers without using multiplication, division and mod operator.If it is overflow, retu...

馬龍駒 2019-08-15 14:49 評論0 收藏0