「leetcode」29.两数相除

googollee 发布于2019-08-26 11:00 / 1389人阅读

摘要：原题给定两个整数，被除数和除数。将两数相除，要求不使用乘法除法和运算符。返回被除数除以除数得到的商。右移位，等价于，除以的次方。当除以时，结果相较于除数会非常的小。我们使用循环逐渐减少右移的位数，逐渐逼近除数，当时等于，大于等于。

原题

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

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3

示例 2:

输入: dividend = 7, divisor = -3
输出: -2

说明：

被除数和除数均为 32 位有符号整数。

除数不为 0。

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

思路

解题思路来自评论区的foxleezh大神。题目中明确不能使用/, 我们可以右移模拟除法，右移可以等价于下面的等式

右移1位，等价于，除以2的1次方。

右移2位，等价于，除以2的2次方。

右移3位，等价于，除以2的3次方。

a / 2 === a >> 1
a / 4 === a >> 2
a / 8 === a >> 3

被除数 / 除数 === 商……余数 等价于 ➡️ 被除数 === (商 * 除数) + 余数 等价于 ➡️ (被除数 - 余数) / 商 === 除数

假设，我们的被除数等于100，除数等于5。

根据等式(被除数 - 余数) / 商 == 除数，我们首先要找到，100除以多少最接近于除数（或者说，除以多少时会大于等于除数）。

当100除以2^31时，结果相较于除数会非常的小。我们使用循环逐渐减少右移的位数，逐渐逼近除数，当100 >>> 4（100 / 16）时等于6，大于等于5。

这时，我们可以肯定商是大于16（2的四次方）的某个数（或者说，100至少包含16个5）。

我们使用被除数 = 被除数 - 16 * 除数等于还剩下的没有除干净的数。目前还剩下20。我们再次使用上述的方法，再次逼近除数（获取20里还有几个5）。最终得到最后的结果。

代码

/**
 * @param {number} dividend
 * @param {number} divisor
 * @return {number}
 */
var divide = function(dividend, divisor) {
    
    // 判断结果是否为负数
    const isNegative = (dividend ^ divisor) < 0
    
    // 统一按正数处理
    dividend = Math.abs(dividend)
    divisor = Math.abs(divisor)
    
    if (dividend === 0) {
        return 0
    }
    
    if (dividend === 2147483648 && divisor === 1) {
        // 避免结果溢出
        return isNegative ? -dividend/divisor : dividend/divisor - 1
    }
    
    let result = 0
    
    for (let i = 31; i >= 0; i--) {
        // 注意这里需要使用无符号右移
        if ((dividend >>> i) >= divisor) {
            result += Math.pow(2, i)
            dividend -= Math.pow(2, i) * divisor
        }
    }
    
    return isNegative ? -result : result
};

混合云超融合服务器 python两数相除两数相 Leetcod LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/106965.html

LeetCode29.两数相除 JavaScript

摘要：给定两个整数，被除数和除数。将两数相除，要求不使用乘法除法和运算符。返回被除数除以除数得到的商。示例输入输出示例输入输出说明被除数和除数均为位有符号整数。假设我们的环境只能存储位有符号整数，其数值范围是。给定两个整数，被除数 dividend和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。返回被除数 dividend 除以除数 divisor 得到的商。...

shiyang6017 2019-08-23 15:16 评论0 收藏0
6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0
两数相除——不允许使用高级运算

摘要：两数相除不允许使用高级运算实现两整数相除，不允许使用乘法除法和取余运算。如果左移一位的除数过大，除数还原。注意处理除法运算中正负号的问题。代码本题以及其它题目代码地址地址两数相除——不允许使用高级运算 Divide Two Integers 实现两整数相除，不允许使用乘法、除法、和取余运算。如果结果溢出（int范围为-2147483648 ~ 2147483647），返回MAX_...

_Zhao 2019-07-30 14:26 评论0 收藏0
leetcode29 Divide Two Integers

摘要：题目要求在不使用乘法，除法和求余操作的情况下，计算两个整数相除的结果。如果溢出了，则返回最大值。在这里核心思路是使用逆向二分法和递归的思路来进行计算。在这里我们使用取值范围更广的来处理数值溢出的场景。题目要求 Divide two integers without using multiplication, division and mod operator. If it is o...

cnio 2019-08-16 10:32 评论0 收藏0
leetcode 29 Divide Two Integers

摘要：很容易想到，我们每次用被除数减去除数，进行减法的次数就是最终结果。这道题的采取了一种类似二分查找的思想。除了这些，这道题还要注意一些边界情况的判断，例如除数或被除数为，值溢出等。题目详情 Divide two integers without using multiplication, division and mod operator.If it is overflow, retu...

马龙驹 2019-08-15 14:49 评论0 收藏0