当前位置：首页 > news >正文

LeetCode Divide Two Integers

news 来源：原创 2024/5/3 13:58:08

原题链接在这里：https://leetcode.com/problems/divide-two-integers/

题目：

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

题解：

与Pow(x, n)类似.

从dividend里一个一个减divisor一直到余下的数小于divisor停止，算算一共减了多少个divisor, 就是答案。

但如此会超时，所以不能一个一个减掉divisor, 要减得更快. 可以把divisor呈指数增长. 若一空需要减掉k个divisor, k = 2^a+2^b+2^c. 表示公式就是dividend = divisor * (2^a+2^b+2^c);

e.g 28/3 => 28/3 = (2^3+2^0), answer = 2^3+2^0=9.

Note: 1. 这道题最火大的是overflow，不但要考虑Math.abs()时的溢出，因为Integer.MIN_VALUE 的绝对值比 Integer.MAX_VALUE 的绝对值大一。

2. 还要考虑一种特殊的corner case: dividend = Integer.MIN_VALUE, divisor = -1, 此时res = Integer.MAX_VALUE +1,所以cast时会出错，要特殊处理。

3. 当以2的幂次方增长时，就用如下方式来写：

1 while(){
2     sum+=sum;
3     pow+=pow;
4 }

Time Complexity: O(log_divisor(dividend)). Space: O(1).

AC Java:

 1 public class Solution {
 2     public int divide(int dividend, int divisor) {
 3         if(divisor == 0){
 4             return Integer.MAX_VALUE;
 5         }
 6         boolean isNeg = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
 7         long res = 0;
 8         long a = Math.abs((long)dividend);
 9         long b = Math.abs((long)divisor);
10         
11         while(a >= b){
12             long sum = b;
13             long pow = 1;
14             while(sum + sum <= a){
15                 sum += sum;
16                 pow += pow;
17             }
18             a -= sum;
19             res += pow;
20         }
21         
22         res = isNeg ? (-res) : res;
23         if(res > Integer.MAX_VALUE){
24             return Integer.MAX_VALUE;
25         }
26         return (int)res;
27     }
28 }