程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode 29 Divide Two Integers(兩個整數相除)(*)

LeetCode 29 Divide Two Integers(兩個整數相除)(*)

編輯:C++入門知識

LeetCode 29 Divide Two Integers(兩個整數相除)(*)


翻譯

不用乘法、除法、取余操作,將兩個數相除。

如果它溢出了,返回MAX_INT

原文

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

代碼

一心撲到了遞歸上,可惜沒能寫出來…………煩躁至極還是找了別人的答案……

class Solution {
public:
    int divide(int dividend, int divisor) {
        if(!divisor) return INT_MAX;
        if(divisor == 1) return dividend;
        if(divisor == -1) {
            if(dividend == INT_MIN) return INT_MAX;
            else return -dividend;
        }

        bool s1 = dividend < 0;
        bool s2 = divisor < 0;

        unsigned int nom = s1 ? -dividend : dividend;
        unsigned int den = s2 ? -divisor : divisor;

        unsigned int rem = 0;
        unsigned int quot = 0;

        for(int i = 31; i >= 0; --i) {
            rem <<= 1;
            rem |= (nom >> i) & 1;
            if(rem >= den) {
                rem -= den;
                quot |= (1 << i);
            }
        }

        return s1^s2? -quot : quot;
    }
};

再來兩個代碼……(慚愧……)

public class Solution
{
    public int Divide(int dividend, int divisor)
    {
        //1. check overflow: 2 ways of over flow 1) 0 divisor; 2) int.Minvalue/(-1)
        if (divisor == 0 || dividend == int.MinValue && divisor == -1) return int.MaxValue;
        //2. calculate sign
        int sign = dividend > 0 ^ divisor > 0 ? -1 : 1, result = 0;
        long m = Math.Abs((long)dividend), n = Math.Abs((long)divisor);
        //3. looping from 1 to possible maximum pow(2, x) to add into result
        while (m >= n)
        {
            long subN = n;
            for (int subCount = 1; m >= subN; subCount <<= 1, subN <<= 1)
            {
                m -= subN;
                result += subCount;
            }
        }
        return result * sign;
    }
}
public class Solution
{
    public int Divide(int dividend, int divisor)
    {
        if (divisor == 1) return dividend;
        if (dividend == int.MinValue && divisor == -1 || divisor == 0) return int.MaxValue;
        int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1, result = 0;
        long dvd = Math.Abs((long)dividend), dvs = Math.Abs((long)divisor);
        while (dvd >= dvs)
        {
            long sub = dvs;
            int subR = 1;
            while (dvd >= (sub << 1))
            { sub <<= 1; subR <<= 1; }
            dvd -= sub;
            result += subR;
        }
        return sign * result;
    }
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved