[Leetcode] Divide Two Integers 整數(shù)整除

張春雷發(fā)布于2019-08-14 12:46 / 695人閱讀

摘要：位操作法復雜度時間空間思路我們設想，本來應該的得到余，那么如果我們把忽略余數(shù)后分解一下，，也就是，也就是把商分解為，所以商的二進制是。我們可以不斷的將乘的一次方，二次方，等等，直到找到最大那個次方，在這里是的四次方。

Divide Two Integers

Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.

位操作法 復雜度

時間 O(N) 空間 O(1)

思路

我們設想87 / 4，本來應該的得到21余3，那么如果我們把87忽略余數(shù)后分解一下，87 = 4 * 21 = 4 * 16 + 4 * 4 + 4 * 1，也就是87 = 4 * (1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0)，也就是把商分解為27 = 1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0，所以商的二進制是10101。我們可以不斷的將4乘2的一次方，二次方，等等，直到找到最大那個次方，在這里是2的四次方。然后，我們就從四次方到零次方，按位看商的這一位該是0還是1。

代碼

public class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == Integer.MIN_VALUE && (divisor == 1 || divisor == -1)){
            return divisor == 1 ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        }
        return (int)divideLong(dividend, divisor);
    }
    
    public long divideLong(long dd, long dv){
        boolean isPos = (dd > 0 && dv > 0) || (dd < 0 && dv < 0); 
        dd = Math.abs(dd);
        dv = Math.abs(dv);
        int digits = 0;
        // 通過將除數(shù)乘2，乘4，乘8，一直乘下去，找到商的最高的次方
        // 比如87/4=21，商的最高次方是4，即2^4=16，即4 * 16 < 87
        while(dv <= dd){
            dv <<= 1;
            digits++;
        }
        // 重置除數(shù)，把最高次方減1得到實際最高位，剛才循環(huán)中多加了一次
        long res = 0;
        dv >>= digits;
        digits--;
        // 看商的每一位是否應該為1
        while(digits >= 0){
            if(dd >= (dv << digits)){
                dd -= dv << digits;
                res += 1 << digits;
            }
            digits--;
            System.out.println(res);
        }
        return isPos ? res : - res;
    }
}

GPU云服務器云服務器 java整數(shù)整除 Integers Divide LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64698.html

leetcode29 Divide Two Integers

摘要：題目要求在不使用乘法，除法和求余操作的情況下，計算兩個整數(shù)相除的結果。如果溢出了，則返回最大值。在這里核心思路是使用逆向二分法和遞歸的思路來進行計算。在這里我們使用取值范圍更廣的來處理數(shù)值溢出的場景。題目要求 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

摘要：很容易想到，我們每次用被除數(shù)減去除數(shù)，進行減法的次數(shù)就是最終結果。這道題的采取了一種類似二分查找的思想。除了這些，這道題還要注意一些邊界情況的判斷，例如除數(shù)或被除數(shù)為，值溢出等。題目詳情 Divide two integers without using multiplication, division and mod operator.If it is overflow, retu...

馬龍駒 2019-08-15 14:49 評論0 收藏0
[LeetCode] 29. Divide Two Integers

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...

fai1017 2019-08-16 13:30 評論0 收藏0
leetcode-29. Divide Two Integers

摘要：題目解析用加減法實現(xiàn)除法用減法，每次累加被減部分，累加商，以一個固定的倍數(shù)遞增坑注意循環(huán)的跳出便捷，的情況要注意。應用累加思想，可以用在提速上，效率提高如果，則是負的，則是正的題目解析：用加減法實現(xiàn)除法用減法，每次累加被減部分，累加商，以一個固定的倍數(shù)遞增坑：注意 while循環(huán)的跳出便捷，= 的情況要注意。應用：累加思想，可以用在提速上，效率提高 Given two ...

darkbaby123 2019-07-30 17:19 評論0 收藏0
LeetCode刷題——29. Divide Two Integers（Part 2靠大家）

摘要：上篇文章寫了以我自己的思路來解決這個問題，但是運行時間過長，看了上的高效寫法是使用位運算的解法，當初我自己寫這個問題是也想到了可以用位運算快一點，但是因為基礎差，對位運算的掌握不牢靠，還是選擇使用了減法的思路，在此將上高效解法做一個思路分析上篇文章寫了以我自己的思路來解決這個問題，但是運行時間過長，看了leetcode 上的高效寫法是使用位運算的解法，當初我自己寫這個問題是也想到了可...

JouyPub 2019-08-16 15:27 評論0 收藏0