[Swift]LeetCode29.两数相除|DivideTwoIntegers

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9894980.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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.

给定两个整数，被除数 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]。本题中，如果除法结果溢出，则返回 2^31 − 1。

8ms

 1 class Solution {
 2     func divide(_ dividend: Int, _ divisor: Int) -> Int {
 3         if divisor == Int32.min {
 4             return dividend == Int32.min ? 1 : 0    
 5         }
 6         var dividend = dividend
 7         var divisor = divisor
 8         var hasSign = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)
 9         var extra = 0
10         if dividend == Int32.min {
11             if divisor == -1 {
12                 return Int(Int32.max)
13             } else if divisor > 0 {
14                 dividend += divisor
15             } else {
16                 dividend -= divisor
17             }
18             extra += 1
19         }
20         
21         
22         let result = dividePositive(abs(dividend), abs(divisor)) + extra
23         return hasSign ? -result : result
24     }
25     
26     func dividePositive(_ dividend: Int, _ divisor: Int) -> Int {
27         var first = dividend
28         var second = divisor
29         var power = 0
30         var result = 0
31         
32         while (first - second >= second) {
33             second <<= 1
34             power += 1
35         }
36         
37         while first >= second {
38             result += (1 << power)
39             first -= second
40             while power > 0 && first < second {
41                 power -= 1
42                 second >>= 1
43             }
44         }
45         return result
46     }
47 }

16ms

 1 class Solution {
 2      func divide(_ dividend: Int, _ divisor: Int) -> Int {
 3         var quocient : Int = 0
 4         var currentDivident = abs(dividend)
 5         let currentDivisor = abs(divisor)
 6         
 7         if currentDivisor == 1 {
 8             if divisor < 0 {
 9                 currentDivident *= -1
10             }
11             if dividend < 0 {
12                 currentDivident *= -1
13             }
14             currentDivident = analiseLimits(quocient: currentDivident)
15             return currentDivident
16         }
17         
18         var iCount = 0
19         
20         for i in 1...currentDivident {
21             if (currentDivident - currentDivisor * i) >= 0 {
22                 quocient += i
23                 iCount = i
24                 currentDivident -= currentDivisor * i
25             } else {
26                 break
27             }
28         }
29         
30         while currentDivident >= currentDivisor {
31             while currentDivident >= currentDivisor * iCount {
32                 quocient += iCount
33                 currentDivident -= currentDivisor * iCount
34             }
35             iCount -= 1
36             if iCount == 0 {
37                 break
38             }
39         }
40         
41         
42         quocient = invert(quocient: quocient, dividend: dividend, divisor: divisor)
43         quocient = analiseLimits(quocient: quocient)
44         
45         return quocient
46     }
47     
48     func invert(quocient: Int, dividend: Int, divisor: Int) -> Int {
49         var newQuocient = quocient
50         if dividend < 0 {
51             newQuocient *= -1
52         }
53         if divisor < 0{
54             newQuocient *= -1
55         }
56         return newQuocient
57     }
58     
59     func analiseLimits(quocient: Int) -> Int {
60         var newQuocient = quocient
61         if quocient > 2147483647 {
62             print(quocient)
63             newQuocient = 2147483647
64         } else if quocient < -2147483648 {
65             newQuocient = -2147483648
66         }
67         return newQuocient
68     }
69 }

20ms

 1 class Solution {
 2     func divide(_ dividend: Int, _ divisor: Int) -> Int {
 3         if divisor == 0 {
 4             return Int.max - 1
 5         }
 6         
 7         let isNegative = (dividend < 0) != (divisor < 0)
 8         var dividend = abs(dividend)
 9         var divisor = abs(divisor)
10         var count = 0
11         
12         while dividend >= divisor {
13             var shift = 0
14             
15             while dividend >= (divisor << shift) {
16                 shift += 1
17             }
18             
19             dividend -= divisor << (shift - 1)
20             count += 1 << (shift - 1)
21         }
22         if count >= 2147483648 && !isNegative{
23             return 2147483647
24         }
25         return isNegative ? -count : count
26     }
27 }

20ms

 1 class Solution {
 2     func divide(_ dividend: Int, _ divisor: Int) -> Int {
 3         let isNegative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)
 4         guard dividend != divisor else { return 1 }
 5         guard dividend != 0 else { return 0 }
 6         var y = abs(divisor)
 7         var x = abs(dividend)
 8         if dividend == Int(Int32.max), y == 1 {
 9             return isNegative ? -Int(Int32.max) : dividend
10         }
11         if dividend == Int(Int32.min), y == 1 {
12             return isNegative ? Int(Int32.min) : Int(Int32.max)
13         }
14         guard y != x else { return -1 }
15         var count = 0
16         while (x > y) {
17             var i = 1
18             var j = 0
19             while (x >= y << 1) {
20                 y = y << 1
21                 i = i << 1
22                 j += 1
23             }
24             x -= y
25             y = y >> j
26             count += i
27         }
28         return isNegative ? -count : count
29     }
30 }

20ms

 1 class Solution {
 2     func divide(_ dividend: Int, _ divisor: Int) -> Int {
 3         if dividend == -2147483648 && divisor == -1 {return 2147483647}
 4         var flag:Int = 1,ans:Int = 0
 5         if dividend == 0 {return 0}
 6         else if divisor == 1 {return dividend}
 7         else if divisor == -1 {return -dividend}
 8         
 9         var long_dividend:Int64 = Int64(dividend)
10         var long_divisor:Int64 = Int64(divisor)
11         
12         if long_dividend < 0 && divisor < 0
13         {
14             long_dividend = -long_dividend
15             long_divisor = -long_divisor
16         }
17         else if long_dividend < 0 || long_divisor < 0
18         {
19             flag = -1
20             long_dividend = abs(long_dividend)
21             long_divisor = abs(long_divisor)
22         }
23         
24         if long_dividend < long_divisor {return 0}
25         var k:Int = 1
26         var tmp:Int64 = long_divisor
27         while (tmp << 1 < long_dividend && tmp << 1 > 0)
28         {
29             tmp <<= 1
30             k <<= 1
31         }
32         ans += k
33         long_dividend -= tmp
34         
35         while (long_dividend >= long_divisor)
36         {
37             while (tmp > long_dividend)
38             {
39                 k >>= 1
40                 tmp >>= 1
41             }
42             long_dividend -= tmp
43             ans += k
44         }
45         return flag * ans
46     }
47 }

24ms

 1 class Solution {
 2     func divide(_ dividend: Int, _ divisor: Int) -> Int {
 3         let sign: Int64 = (dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0) ? 1 : -1
 4         let lDividend = dividend < 0 ? -Int64(dividend) : Int64(dividend)
 5         let lDivisor = divisor < 0 ? -Int64(divisor) : Int64(divisor)
 6         var result: Int64 = 0
 7         var left: Int64 = 1
 8         var right: Int64 = lDividend
 9         var middle: Int64 = 0
10         
11         while left <= right {
12             middle = (left + right) / 2
13             if middle * lDivisor <= lDividend {
14                 result = middle
15                 left = middle + 1
16             } else {
17                 right = middle - 1
18             }
19         }
20         
21             if Int(result * sign) >= 2147483648 {
22                 return 2147483647
23             } else {
24                 return Int(result * sign)
25             }
26     }
27 }

24ms

 1 class Solution {
 2     func divide(_ dividend: Int, _ divisor: Int) -> Int {
 3         if dividend == 0{
 4             return 0;
 5         }
 6         var isNeed = false
 7         var dividend = dividend;
 8         var divisor = divisor;
 9         if dividend > 0 && divisor < 0{
10             isNeed = true
11             divisor = 0 - divisor;
12         }else if dividend < 0 && divisor > 0{
13             isNeed = true
14             dividend = 0 - dividend;
15         }else if dividend < 0 && divisor < 0{
16             divisor = 0 - divisor;
17             dividend = 0 - dividend;
18         }
19         if divisor == 1{
20             
21             if isNeed {
22                 return Int(Int32(0 - dividend));
23             }else{
24                 if dividend >= 2^31{
25                     return Int(Int32.max)
26                 }
27                 return Int(Int32(dividend));
28             }
29         }
30         var i = 0;
31         while divisor <= dividend {
32             var temp = divisor;
33             var cnt = 1;
34             while dividend >= temp{
35                 temp = temp<<1
36                 cnt = cnt<<1
37             }
38             i += (cnt>>1)
39             dividend -= (temp>>1)
40         }
41         if isNeed {
42             return Int(0 - i);
43         }else{
44             return Int(i);
45         }
46     }
47 }

28ms

 1 class Solution {
 2     func divide(_ dividend: Int, _ divisor: Int) -> Int {
 3         if divisor == 0 || (dividend == -Int(INT32_MAX) - 1 && divisor == -1) {
 4             return Int(INT32_MAX)
 5         }
 6         
 7         var a = abs(dividend), b = abs(divisor), res = 0
 8         let sign = (dividend > 0 && divisor > 0 || dividend < 0 && divisor < 0) ? 1 : -1
 9         if b == 1 {
10             return a * sign
11         }
12         
13         
14         while a >= b {
15             var m = b, n = 1
16             while (a >= (m << 1)) {
17                 m <<= 1
18                 n <<= 1
19             }
20             res += n
21             a -= m
22         }
23         
24         return res * sign
25     }
26 }

32ms

 1 class Solution {
 2     func divide(_ dividend: Int, _ divisor: Int) -> Int {
 3         
 4         guard dividend != 0 else {
 5             return 0
 6         }
 7         
 8         guard divisor != 0 else {
 9             return Int(Int32.max)
10         }
11         
12         guard divisor != 1 else {
13             return dividend
14         }
15         
16         guard divisor != -1 else {
17             if dividend == Int32.min {
18                 return Int(Int32.max)
19             }
20             
21             return dividend * -1
22         }
23         
24         let isNegative = ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0))
25         
26         var tmpDividend = abs(dividend)
27         let tmpDivisor = abs(divisor)
28         var result = 0
29         var fac = 1
30         var incDivisor = tmpDivisor
31         
32         while tmpDividend >= tmpDivisor {
33             if tmpDividend < incDivisor {
34                 incDivisor = tmpDivisor
35                 fac = 1
36             }
37             
38             tmpDividend -= incDivisor
39             
40             result += fac
41             
42             incDivisor += incDivisor
43             fac += fac
44         }
45         
46         return isNegative ? result * -1 : result
47     }
48 }

44ms

 1 class Solution {
 2     func divide(_ dividend: Int, _ divisor: Int) -> Int {
 3         
 4         /// 被除数为0，结果肯定是0
 5         guard dividend != 0 else {
 6             return 0
 7         }
 8         
 9         /// 除数为0，返回32位最大值
10         guard divisor != 0 else {
11             return Int(Int32.max)
12         }
13         
14         /// 除数为1，直接返回
15         guard divisor != 1 else {
16             return dividend
17         }
18         
19         /// 除数为-1
20         guard divisor != -1 else {
21             /// 被除数为-1，结果会越界，则返回32位最大值
22             if dividend == Int32.min {
23                 return Int(Int32.max)
24             }
25             
26             /// 直接取反
27             return dividend * - 
                       
                    
                     
                      



鲜花




握手




雷人




路过




鸡蛋