AlgoPress | AlgoPress

题目描述

https://leetcode.cn/problems/divide-two-integers

给定两个整数，被除数dividend和除数divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数dividend除以除数divisor得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例1:

输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例2:

输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2

提示：

被除数和除数均为 32 位有符号整数。
除数不为0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231− 1]。本题中，如果除法结果溢出，则返回 231− 1。

思路：减法模拟（超时）

直接用减法模拟，会超时

csharp

public class Solution {
    public int Divide(int dividend, int divisor) {

        if(dividend < 0){
            return -Divide(-dividend, divisor);
        }
        if(divisor < 0){
            return -Divide(dividend, -divisor);
        }

        int result = 0;
        while(dividend >= divisor){
            dividend -= divisor;
            result++;
        }
        return result;
    }
}

思路2：官方

csharp

public class Solution {
    public int Divide(int dividend, int divisor) {
        // 考虑被除数为最小值的情况
        if (dividend == int.MinValue) {
            if (divisor == 1) {
                return int.MinValue;
            }
            if (divisor == -1) {
                return int.MaxValue;
            }
        }
        // 考虑除数为最小值的情况
        if (divisor == int.MinValue) {
            return dividend == int.MinValue ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (dividend == 0) {
            return 0;
        }
        
        // 一般情况，使用二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        bool rev = false;
        if (dividend > 0) {
            dividend = -dividend;
            rev = !rev;
        }
        if (divisor > 0) {
            divisor = -divisor;
            rev = !rev;
        }
        
        int left = 1, right = int.MaxValue, ans = 0;
        while (left <= right) {
            // 注意溢出，并且不能使用除法
            int mid = left + ((right - left) >> 1);
            bool check = quickAdd(divisor, mid, dividend);
            if (check) {
                ans = mid;
                // 注意溢出
                if (mid == int.MaxValue) {
                    break;
                }
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return rev ? -ans : ans;
    }

    // 快速乘
    public bool quickAdd(int y, int z, int x) {
        // x 和 y 是负数，z 是正数
        // 需要判断 z * y >= x 是否成立
        int result = 0, add = y;
        while (z != 0) {
            if ((z & 1) != 0) {
                // 需要保证 result + add >= x
                if (result < x - add) {
                    return false;
                }
                result += add;
            }
            if (z != 1) {
                // 需要保证 add + add >= x
                if (add < x - add) {
                    return false;
                }
                add += add;
            }
            // 不能使用除法
            z >>= 1;
        }
        return true;
    }
}

复习：20220712

主要思路：

通过相减被除数，模拟除法。
如果直接循环，效率比较低，比如 int.MaxValue / 1 会超时，通过翻倍被除数，然后商也增加翻倍的机制来加速
题目的最大值最小值使用 32 为整形的最大最小值，统一使用负号来处理，可以覆盖范围
开始增加越界的处理，主要是被除数为1/-1的计算

csharp

public class Solution {
    public int Divide(int dividend, int divisor) {
        //越界处理
        if(divisor == 1){
            return dividend;
        }
        if(divisor == -1){
            if(dividend == int.MinValue){
                return int.MaxValue;
            }
            return -dividend;
        }
        //获取符号
        bool negative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
        //转化为负数处理
        dividend = dividend > 0 ? -dividend : dividend;
        divisor = divisor > 0 ? -divisor : divisor;
        //开始扣减
        int result = 0;
        while(dividend <= divisor){ //因为是负数，所以用<=来计算
            int times = 1;
            int d = divisor;
            //Console.WriteLine("times:{0},d:{1}",times,d);
            while(dividend - d <= d){ //如果剩余的数有两倍的d
                d = d + d;
                times = times + times;
            }
            dividend = dividend - d; //扣减已经计算的倍数值
            result += times; //累计结果次数
        }
        return negative ? -result : result;
    }
}

题目描述 #

思路：减法模拟（超时） #

思路2：官方 #

复习：20220712 #

题目描述

思路：减法模拟（超时）

思路2：官方

复习：20220712