python LeetCode 两数相除
2018-08-21 05:42:22来源:博客园 阅读 ()
近一个月一直在写业务,空闲时间刷刷leetcode,刷题过程中遇到了一道比较有意思的题目,和大家分享。
题目描述:
给定两个整数,被除数 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]。本题中,如果除法结果溢出,则返回 2**31 ? 1。
第一反应是这道题还是挺简单的,用减法实现除法不就好了,python刷题实现甚至可以直接使用range()来实现除法,需要注意的点如下:
1.提前判断结果的正负号
2.结果在[-2**31,2**31-1]中,要判断结果是否移除
3.使用range()来计算除法时,一旦除法可以整除我们要对结果+1,因为len(range(3,7,3))的结果是2,len(range(3,9,3))的结果也是2
代码如下:
class Solution(object): def divide(self, dividend, divisor): """ :type dividend: int :type divisor: int :rtype: int """ below = 1 if dividend < 0 < divisor or divisor < 0 < dividend: below = -1 dividend, divisor = abs(dividend), abs(divisor) if dividend < divisor: return 0 elif divisor == 1: result = dividend * below if result >= 2**31-1: return 2**31-1 return result result = len(range(divisor, dividend, divisor)) if (result+1) * divisor == dividend: result += 1 return result * below
自己写了好多case来测试都是没问题的,代码提交到leetcode,悲剧了。。。内存错误,看来是内存超了。问题出在核心语句len(range(divisor, dividend, divisor))上,怎么既能保证目前代码的简洁性又能降低内存使用呢。我解决办法是使用xrange代替range,简单的说range返回的对象是个list,会开辟一个很大的空间,而xrange不同,返回的是生成器,所以对内存的使用得到了直接的优化。重新提交,果然通过了。
最终代码如下:
class Solution(object): def divide(self, dividend, divisor): """ :type dividend: int :type divisor: int :rtype: int """ below = 1 if dividend < 0 < divisor or divisor < 0 < dividend: below = -1 dividend, divisor = abs(dividend), abs(divisor) if dividend < divisor: return 0 elif divisor == 1: result = dividend * below if result >= 2**31-1: return 2**31-1 return result result = len(xrange(divisor, dividend, divisor)) if (result+1) * divisor == dividend: result += 1 return result * below
希望对大家有所帮助~
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- python3基础之“术语表(2)” 2019-08-13
- python3 之 字符串编码小结(Unicode、utf-8、gbk、gb2312等 2019-08-13
- Python3安装impala 2019-08-13
- 小白如何入门 Python 爬虫? 2019-08-13
- python_字符串方法 2019-08-13
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash