美文网首页
Leetcode 29 两数相除

Leetcode 29 两数相除

作者: hekirakuno | 来源:发表于2020-02-01 13:27 被阅读0次

给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:
输入: dividend = 10, divisor = 3
输出: 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
说明:
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数,其数值范围是 [−231, 231 − 1]。本题中,如果除法结果溢出,则返回 231 − 1。

这个题胜率这么低,其实关键还是因为范围界限的判断影响的。只要不越界,其实除法并不难。另外需要注意的还有一点,就是关于时间限制。我之前有一版提交就是超出时间限制导致的问题。这里的优化点在于通过位运算+更加优秀的算法,总之就是减少运算次数

  class Solution {
            public int divide(int dividend, int divisor) {
            if(dividend==0){
                return 0;
            }
            long AbsDividend  = Math.abs((long)dividend);
            long AbsDivisor = Math.abs((long)divisor);
            long ans = 0;
            for(int i = 31; i >= 0; i--) {
                //比较dividend是否大于divisor的(1<<i)次方,不要将dividend与(divisor<<i)比较,而是用 (dividend>>i)与divisor比较,
                //效果一样,但是可以避免因(divisor<<i)操作可能导致的溢出,如果溢出则会可能dividend本身小于divisor,但是溢出导致dividend大于divisor
                if((AbsDividend >> i) >= AbsDivisor) {
                    ans = ans+(1<<i);
                    AbsDividend = AbsDividend-(AbsDivisor<<i);
                }
            }
            int c = dividend^divisor;
            if(c>=0){
                if(Math.abs(ans)>=Integer.MAX_VALUE){
                    return Integer.MAX_VALUE;
                }
                return (int)ans;
            }else{
                return -(int)ans;
            }
        }
  }

相关文章

  • LeetCode-29-两数相除

    LeetCode-29-两数相除 题目 给定两个整数,被除数 dividend 和除数 divisor。将两数相除...

  • LeetCode 29. 两数相除

    29. 两数相除 题目来源:https://leetcode-cn.com/problems/divide-two...

  • 29. 两数相除

    29. 两数相除 题目链接:https://leetcode-cn.com/problems/divide-two...

  • [leetcode] 29 两数相除

    leetcode 29 link Given two integers dividend and divisor,...

  • LeetCode 29——两数相除

    1. 题目 2. 解答 2.1. 方法一 题目要求不能使用乘法、除法和除余运算,但我们可以将除法转移到对数域。 这...

  • [LeetCode]29、两数相除

    题目描述 给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mo...

  • Leetcode 29 两数相除

    给定两个整数,被除数 dividend 和除数 divisor。将两数相除,要求不使用乘法、除法和 mod 运算符...

  • leetcode 29 - 两数相除

    来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/divide...

  • LeetCode - #29 两数相除

    前言 我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。微博:@故胤...

  • 每天进步一点点【2019.8.23】

    一、两数相除【leetcode 29】 题目描述:给定两个整数,被除数 dividend 和除数 divisor。...

网友评论

      本文标题:Leetcode 29 两数相除

      本文链接:https://www.haomeiwen.com/subject/ubztxhtx.html