leetcode|中等:29. 两数相除

1.题目

给定两个整数，被除数 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 位有符号整数，其数值范围是 $[−2^{31}, 2^{31} − 1]$。本题中，如果除法结果溢出，则返回 $2^{31} − 1$。

2. 题解

2.1 思路分析

思路1：用减法来模拟乘法
    O(n)会运行超时

思路2: 思路1优化:借鉴计算机网络的流量拥塞控制机制,对被除数进行快速倍增

2.2 代码实现

• 思路1：用减法来模拟乘法

public class Solution {
    public int divide(int dividend, int divisor) {
        // 解决计算结果上溢的问题
        if(dividend==Integer.MIN_VALUE&&divisor==-1){
            return Integer.MAX_VALUE;
        }

        // 判断结果的正负并把负数取绝对值+类型提升int-->long
        System.out.println("dividend="+dividend+",divisor="+divisor);
        boolean positiveFlag = true;
        long dividendLong = dividend;
        long divisorLong = divisor;
        if(dividend<0){
            positiveFlag = !positiveFlag;
            dividendLong = -(long)dividend;
        }
        if(divisor<0){
            positiveFlag = !positiveFlag;
            divisorLong = -(long)divisor;
        }

        System.out.println("dividendLong="+dividendLong+",divisorLong="+divisorLong);

        // 用减法模拟乘法
        long res = 0;
        while (dividendLong>=divisorLong){
            dividendLong -= divisorLong;
            res++;
        }

        // 结果符号修正
        res = positiveFlag?res:-res;
        return (int)res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int in = 3;
        System.out.println(solution.divide(Integer.MIN_VALUE,3));
    }
}

• 思路2: 思路1优化:借鉴计算机网络的流量拥塞控制机制,对被除数进行快速倍增

public class Solution {
    public int divide(int dividend, int divisor) {
        // 解决计算结果上溢的问题
        if(dividend==Integer.MIN_VALUE&&divisor==-1){
            return Integer.MAX_VALUE;
        }

        // 判断结果的正负并把负数取绝对值+类型提升int-->long
        boolean positiveFlag = true;
        long dividendLong = dividend;
        long divisorLong = divisor;
        if(dividend<0){
            positiveFlag = !positiveFlag;
            dividendLong = -(long)dividend;
        }
        if(divisor<0){
            positiveFlag = !positiveFlag;
            divisorLong = -(long)divisor;
        }

        // 用减法模拟乘法+快速倍乘
        long res = 0;
        while (dividendLong>=divisorLong) {
            long base = divisorLong;
            while (dividendLong >= base) {
                dividendLong -= base;
                res += (base/divisorLong);
                base *= 2;
            }
        }

        // 结果符号修正
        res = positiveFlag?res:-res;
        return (int)res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int in = 3;
        System.out.println(solution.divide(Integer.MIN_VALUE,2));
    }
}

2.3 提交结果

• 思路1

• 思路2

参考资料

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