程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> leetcode筆記:Divide Two Integers

leetcode筆記:Divide Two Integers

編輯:關於C++

一. 題目描述

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

If it is overflow, return MAX_INT.

二. 題目分析

題目的意思簡單明了,就是要求不使用乘法、除法和取余mod,輸入兩個整數,輸出除法操作的結果。

出去乘除法,剩下的只有加減法和位運算,這是不難想到的,而直接使用減法,對被除數逐次減去除數大小的值,記錄被減次數,肯定是可以得出和除法操作一樣的結果,但該方法比較傻瓜,且會超時,時間復雜度為O(n)。

使用位運算可以做到O(logn)的復雜度,但要一步想到具體操作卻也不那麼簡單,首先,我們知道任何一個整數都可以表示成以2的冪為底的一組基的線性組合,即num = flag0 * 2^0 + flag1 * 2^1 + flag2 * 2^2 + ... + flagn * 2^n 其中,flag0, flag1, flag2, ..., flagn 取值為0 & 1

基於以上事實,如果令:dividend / divisor = num,則有:

dividend = divisor * num = divisor * (flag0 * 2^0 + flag1 * 2^1 + flag2 * 2^2 + ... + flagn * 2^n)

對於除數,使用移位操作<<使其每次翻倍,從而減少減法求商的次數。以下是步驟:

當被除數大於除數時,對除數乘2(代碼中使用變量step用於記錄每次除數乘2),直到step大於被除數為止。記錄移位操作的次數i。 如果被除數大於除數,那麼被除數減去step。直到被除數小於除數。保存結果。 輸出結果result。

注:

byte:128~127 (1Byte)
short :32768~32767 (2Bytes)
int:-2147483648~2147483647 (4Bytes)
long:-9223372036854774808~9223372036854774807 (8Bytes)

三. 示例代碼

class Solution {
public:
    int divide(int dividend, int divisor) {
        if (dividend == 0 || divisor == 0) return 0;
        if (dividend == INT_MIN && divisor == -1) return INT_MAX; // 溢出
        bool negative = (dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0);
        long positiveDividend = abs(long(dividend));
        long positiveDivisor = abs(long(divisor));
        long result = 0;

        while (positiveDividend >= positiveDivisor) // 被除數大於除數
        {
            long step = positiveDivisor;
            for (int i = 0; positiveDividend >= step; ++i, step <<= 1)
            {
                positiveDividend = positiveDividend - step;
                result += 1 << i;
            }
        }
        return negative ? -result : result;
    }
};

四. 小結

使用位運算來解決此類問題,是挺容易想到的,但是具體如何操作又是另外一回事。

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