Leetcode(29)-两数相除
2024-10-18 21:45:50
给定两个整数,被除数 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。
思路:两数相除,规定不能用乘法,除法以及取余操作。一开始想是用减法来判断。需要注意的是测试用例。一旦涉及int型,我们要考虑int型的范围为 [−2^31, 2^31 − 1],这样的,INT_MIN除以-1的时候,就会溢出。当然INT_MIN除以1的时候,不会溢出,但是如果用取绝对值的方法,INT_MIN取绝对值就会溢出。所以计算的时候要扩展成long long型的。
另外关于除法的实现,减法的方式,如果被除数太大,除数太小,循环次数太多。所以采用位操作,扩大倍数,以减少循环次数。如果被除数大于除数的两倍,我们可以将除数扩大二倍,我们还需要用一个变量记录当前的商,一开始为1,除数每扩大一次,它也相应的扩大二倍。
int divide(int dividend, int divisor)
{
if (divisor == 0 || (dividend == INT_MIN && divisor == -1))
return INT_MAX;
long long m = abs((long long)dividend), n = abs((long long)divisor), res = 0;
int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;//注意此处异或的作用
if (n == 1) return sign == 1 ? m : -m;
while (m >= n)
{
long long t = n, p = 1;
while (m >= (t << 1))
{
p <<= 1;
t <<= 1;
}
res += p;
m -= t;
}
return sign > 0 ? res : -res;
}
最新文章
- 163邮箱问题:554 DT:SPM 163 smtp5,D9GowACHO7RNWNdXmXs1Bw--.9035S2
- KALI Linux problems &; Study Red Hat | Ubuntu
- js事件监听/鼠标滚轮/行为/冒泡/键盘的兼容性写法
- [译]JavaScript规范-葵花宝典
- 繁华模拟赛 Vicent与游戏
- 从java 转到 c# 知识点
- ZooKeeper是什么?
- ios 图片截取功能 图片拼接功能
- .Net Framework 开发Http协议
- weblogic开机启动-超简单
- java面试基础(一)
- Java中ArrayList和LinkedList区别(转)
- P66 整环的零元
- BZOJ3566: [SHOI2014]概率充电器 树形+概率dp
- 【Django】ORM操作MySQL数据库遇到的一些问题
- JAVA 中CLOB与Clob有区别
- Bioconductor应用领域之基因芯片
- maven的统一版本管理实践
- ADB 源码分析(一) ——ADB模块简述【转】
- 【比赛】HNOI2018 游戏
热门文章
- SAP ERP中权限参数和角色相关表
- SAP IDES登陆的short dump终于不见了
- SAP 中session和外部断点设置的区别
- kafka(三)原理剖析
- 集成多种协议、用于 USBC 端口的快充协议芯片IP2723
- 什么是Etcd,如何运维Etcd ?
- selenium八大元素定位方法
- MySQL调优之索引优化
- js中的事件委托(事件代理)详解
- 类型检查和鸭子类型 Duck typing in computer programming is an application of the duck test 鸭子测试 鸭子类型 指示编译器将类的类型检查安排在运行时而不是编译时 type checking can be specified to occur at run time rather than compile time.