來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/divide-two-integers
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

題目

給定兩個(gè)整數(shù)，被除數(shù) dividend 和除數(shù) divisor。將兩數(shù)相除，要求不使用乘法、除法和 mod 運(yùn)算符。

返回被除數(shù) dividend 除以除數(shù) divisor 得到的商。

示例 1:

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

示例 2:

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

說(shuō)明:

被除數(shù)和除數(shù)均為 32 位有符號(hào)整數(shù)。
除數(shù)不為 0。
假設(shè)我們的環(huán)境只能存儲(chǔ) 32 位有符號(hào)整數(shù)，其數(shù)值范圍是 [?231,  231 ? 1]。本題中，如果除法結(jié)果溢出，則返回 231 ? 1。

方法-遞歸具體看getResult

   func divide(_ dividend: Int, _ divisor: Int) -> Int {
     
        if abs(dividend) < abs(divisor) {
            
            return 0
        }
        let sign: Double = ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0)) ? 1 : -1
        var result: Double = 0
        
        if abs(divisor) == 1 {
            
            result = sign * Double(abs(dividend))
            if result > pow(2, 31) - 1 {
                result = pow(2, 31) - 1
            }else if result < -pow(2, 31) {
                result = pow(2, 31)
            }
            return Int(result)
        }
    
        if abs(dividend) == abs(divisor) {
            return Int(sign)
        }
    
        var newDividend = abs(dividend)
        var newDivisor = abs(divisor)
        
    result = Double(getResult(newDividend, newDivisor, Int(sign)))

        if result > pow(2, 31) - 1
        {
            result = pow(2, 31) - 1
        }else if result < -pow(2, 31) {
            result = pow(2, 31)
        }
        return Int(result)
    }

       
   func getResult(_ dividend: Int, _ divisor: Int, _ sign: Int) -> Int {
        
        var newDivisor = abs(divisor)

        var result = 0
        
        while newDivisor <= dividend {
            
            if result == 0 {
                result += sign
            }else {
                result += result
            }
            if (newDivisor + newDivisor) > dividend {
                result += getResult(dividend - newDivisor, divisor, sign)
            }
            newDivisor += newDivisor

        }
        
        return result
    }

之前 的方法都超時(shí)了，這個(gè)方法也只擊敗了70%的用戶。但是我實(shí)在想不起來(lái)，不使用乘法、除法和 mod 運(yùn)算符還能怎么優(yōu)化。先這樣吧。

image.png