问题描述:
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
原问题链接:https://leetcode.com/problems/divide-two-integers/
问题分析
这个问题和之前做过的一些问题有类似的地方。就是在程序里会碰到很多溢出的情况。一种典型的方法就是将当前类型的数值转换成long类型。既然这里不让用乘、除等运算。所以最简单的一种运算就是用循环减法。但是如果dividend很大而divisor很小的情况下,这里执行的速度会非常慢。
所以在这一点上也有一个可以改进的地方,就是移位运算。首先将divisor向左移位,移动一位相当于乘以2。通过判断dividend > (divisor << shift)这样可以得到一个值 1<<shift。这样通过循环可以更快的得出结果。
还有一个要注意的细节就是除数和被除数的符号。如果它们两个的符号不同,我们需要记录下来。具体的实现代码如下:
public class Solution { public int divide(int dividend, int divisor) { if (dividend == 0) { return 0; } boolean neg = (dividend < 0) ^ (divisor < 0); long m = Math.abs((long)dividend), n = Math.abs((long)divisor); long result = 0; while (m >= n) { int shift = 0; while (m > (n << shift + 1)) { shift++; } m -= n << shift; result += (1 << shift); } result = (neg) ? ~(result - 1) : result; result = Math.min(Integer.MAX_VALUE, result); result = Math.max(Integer.MIN_VALUE, result); return (int)result; } }
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
Leetcode:Leetcode提交
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
LeetCode 101:和你一起你轻松刷题(C++)
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
Leetcode:LeetCode解题代码
LeetCode:LeetCode的代码
LeetCode:LeetCode的注释
leetcode:LeetCode问题
leetcode卡leetcode 算法 :smiling_face_with_sunglasses: 9月打卡 问题 困难 标签 Medium Minimax Dynamic Programming Medium Minimax Dynamic Programming Math Hard BackTracking Easy Tree Depth-first Search ...
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...