LeetCode 29. Divide Two Integers

原创

Dylan Liu

发布于 2025-02-15 17:56:30

860

文章被收录于专栏：dylanliudylanliu

Description

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

The integer division should truncate toward zero, which means losing its fractional part. For example, 8.345 would be truncated to 8, and -2.7335 would be truncated to -2.

Return the quotient after dividing dividend by divisor.

Note: Assume we are dealing with an environment that could only store integers within the 32-bit signed integer range: −2^31, 2^31 − 1. For this problem, if the quotient is strictly greater than 2^31 - 1, then return 2^31 - 1, and if the quotient is strictly less than -2^31, then return -2^31.

Example 1:

Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = 3.33333.. which is truncated to 3.

Example 2:

Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = -2.33333.. which is truncated to -2.

Constraints:

-2^31 <= dividend, divisor <= 2^31 - 1
divisor != 0

Solution

这个题不让用乘除和取余运算符，那就只能用加减运算。

这个题的 edge case 比较多，特别是对于最大最小值的情况下，针对这种情况，可以使用 long 来覆盖掉计算过程中可能发生的越界问题。

另一个就是直接的加减会导致超时，像 2^31/1 的情况，基本的解题思路就是先构造一个 divisor * 2^N的数组，把最差情况下的O(dividend) 的时间复杂度降低到 O(log dividend).

class Solution {
    public int divide(int dividend, int divisor) {
        if (dividend == 0) return 0;
        long dd =(long) dividend;
        long dr = (long) divisor;
        long max = Integer.MAX_VALUE;
        long min = Integer.MIN_VALUE;

        boolean positive = (dd > 0 && dr > 0) || (dd < 0 && dr < 0);
        if (dd < 0) dd = -dd;
        if (dr < 0) dr = -dr;

        if (dd < dr) return 0;

        // 二分法，先构造一个 divisor * 2^N 的数组
        long[][] exp = new long[33][2];
        int index = 0;
        long drTmp = dr;
        long quoTmp = 1;
        while(drTmp <= dd) {
            exp[index][0] = drTmp;
            exp[index][1] = quoTmp;
            drTmp += drTmp;
            quoTmp += quoTmp;
            index++;
        }

        long quo = 0;
        while (index >= 0) {
            if (dd >= exp[index][0]) {
                quo+= exp[index][1];
                dd -= exp[index][0];
            } 
            index--;
        }
        if (!positive) quo = -quo;
        if (quo > max) return (int)max;
        if(quo < min) return (int)min;
        return (int)quo;
    }
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

java