資訊專欄INFORMATION COLUMN
摘要：很容易想到，我們每次用被除數(shù)減去除數(shù)，進(jìn)行減法的次數(shù)就是最終結(jié)果。這道題的采取了一種類似二分查找的思想。除了這些，這道題還要注意一些邊界情況的判斷，例如除數(shù)或被除數(shù)為，值溢出等。
題目詳情
Divide two integers without using multiplication, division and mod operator.想法
If it is overflow, return MAX_INT.題目要求我們?cè)诓唤柚朔ㄟ\(yùn)算、除法運(yùn)算和模運(yùn)算的基礎(chǔ)上，求出輸入的兩個(gè)整數(shù)相除的結(jié)果。如果溢出，那么返回MAX_INT。其中第一個(gè)參數(shù)是被除數(shù)，第二個(gè)參數(shù)是除數(shù)。
這道題既然不能借助乘、除、模三種運(yùn)算，我們只能運(yùn)用加減法求結(jié)果。
很容易想到，我們每次用被除數(shù)減去除數(shù)，進(jìn)行減法的次數(shù)就是最終結(jié)果。但是這種方法在遇到被除數(shù)很大，而除數(shù)很小的情況時(shí)，運(yùn)算時(shí)間太長(zhǎng)，會(huì)導(dǎo)致超時(shí)。
這道題的采取了一種類似‘二分查找’的思想。對(duì)于每一次運(yùn)算，我們要盡可能找出除數(shù)的倍數(shù)n，使得n倍的除數(shù)盡可能接近被除數(shù)的大小。
如何找到這個(gè)倍數(shù)n呢？我們每次將除數(shù)翻倍，倍數(shù)為1，2，4，8，16...直到除數(shù)的n倍比被除數(shù)大。
這個(gè)時(shí)候我們就用被除數(shù)減去n倍的除數(shù)，繼續(xù)這樣計(jì)算下去。
最后我們得到的所有倍數(shù)的和，就是最后的答案。
除了這些，這道題還要注意一些邊界情況的判斷，例如除數(shù)或被除數(shù)為0，值溢出等。
解法 public int divide(int dividend, int divisor) {
boolean isPositive = true;
if((dividend < 0 && divisor >0) || (dividend > 0 && divisor < 0)){
isPositive = false;
}
long ldividend = Math.abs((long)dividend);
long ldivisor = Math.abs((long)divisor);
if(ldivisor == 0)return Integer.MAX_VALUE;
if(ldividend == 0)return 0;
long lans = ldivide(ldividend, ldivisor);
int ans;
if (lans > Integer.MAX_VALUE){
ans = (isPositive)? Integer.MAX_VALUE : Integer.MIN_VALUE;
} else {
ans = (isPositive) ? (int)lans : -(int)lans;
}
return ans;
}
private long ldivide(long ldividend, long ldivisor) {
if (ldividend < ldivisor) return 0;
long sum = ldivisor;
long multiple = 1;
while ((sum+sum) <= ldividend) {
sum += sum;
multiple += multiple;
}
return multiple + ldivide(ldividend - sum, ldivisor);
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/68841.html
Problem Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer divisi...
摘要：題目解析用加減法實(shí)現(xiàn)除法用減法，每次累加被減部分，累加商，以一個(gè)固定的倍數(shù)遞增坑注意循環(huán)的跳出便捷，的情況要注意。應(yīng)用累加思想，可以用在提速上，效率提高如果，則是負(fù)的，則是正的 題目解析： 用加減法實(shí)現(xiàn)除法 用減法，每次累加被減部分，累加商， 以一個(gè)固定的倍數(shù)遞增 坑： 注意 while循環(huán)的跳出便捷，= 的情況要注意。應(yīng)用：累加思想，可以用在提速上，效率提高 Given two ...
摘要：題目要求在不使用乘法，除法和求余操作的情況下，計(jì)算兩個(gè)整數(shù)相除的結(jié)果。如果溢出了，則返回最大值。在這里核心思路是使用逆向二分法和遞歸的思路來進(jìn)行計(jì)算。在這里我們使用取值范圍更廣的來處理數(shù)值溢出的場(chǎng)景。 題目要求 Divide two integers without using multiplication, division and mod operator. If it is o...
摘要：上篇文章寫了以我自己的思路來解決這個(gè)問題，但是運(yùn)行時(shí)間過長(zhǎng)，看了上的高效寫法是使用位運(yùn)算的解法，當(dāng)初我自己寫這個(gè)問題是也想到了可以用位運(yùn)算快一點(diǎn)，但是因?yàn)榛A(chǔ)差，對(duì)位運(yùn)算的掌握不牢靠，還是選擇使用了減法的思路，在此將上高效解法做一個(gè)思路分析 上篇文章寫了以我自己的思路來解決這個(gè)問題，但是運(yùn)行時(shí)間過長(zhǎng)，看了leetcode 上的高效寫法是使用位運(yùn)算的解法，當(dāng)初我自己寫這個(gè)問題是也想到了可...
摘要：位操作法復(fù)雜度時(shí)間空間思路我們?cè)O(shè)想，本來應(yīng)該的得到余，那么如果我們把忽略余數(shù)后分解一下，，也就是，也就是把商分解為，所以商的二進(jìn)制是。我們可以不斷的將乘的一次方，二次方，等等，直到找到最大那個(gè)次方，在這里是的四次方。 Divide Two Integers Divide two integers without using multiplication, division and m...
閱讀 1809·2021-11-24 10:21
閱讀 1219·2021-09-22 15:25
閱讀 3180·2019-08-30 15:55
閱讀 720·2019-08-30 15:54
閱讀 3468·2019-08-30 14:20
閱讀 1668·2019-08-30 14:06
閱讀 646·2019-08-30 13:11
閱讀 3157·2019-08-29 16:43
