leetcode|中等:29. 两数相除

jupiter
2022-04-26 / 0 评论 / 571 阅读 / 正在检测是否收录...
温馨提示:
本文最后更新于2022年04月26日,已超过924天没有更新,若内容或图片失效,请留言反馈。

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
提交结果执行用时内存消耗语言提交时间备注
超出时间限制N/AN/AJava2022/04/26 10:10添加备注
  • 思路2
提交结果执行用时内存消耗语言提交时间备注
通过1 ms38.5 MBJava2022/04/26 10:29添加备注

参考资料

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

评论 (0)

打卡
取消