#LeetCode:29. Divide Two Integers

這題因為有強制限制不可以用乘法、加法、餘數來做,所以我們可以改成利用二進位與位元運算的方式去做除法。一般我們在做除法時算完所得出的解,它其中的每個位數所代表的意思是:將除數根據所位於的進位制(ex. 十進位、二進位)去位移了該位數,然後找出在該位數到底乘以多少後,最大能夠小於等於目前被除數的數值,底下舉個例子。

  • 10654 除以 3 等於 3551
    • 第一位的 3 ,是將 3 依照十進位制移到千位數(即 3000),找出在 0 ~ 9 中 3000 乘上的數字還可以小於 10654 的答案,即是 3 ,並且 10654 – 3000 * 3 = 1654。
    • 第二位的 5 ,是將 3 依照十進位制移到百位數(即 300),找出在 0 ~9 中 300 乘上的數字還可以小於 1654 的答案,即是 5 ,並且 1654 – 300 * 5 = 154。
    • 第三位的 5 ,是將 3 依照十進位制移到十位數(即 30),找出在 0 ~ 9 中 30 乘上的數字還可以小於 154 的答案,即是 5 ,並且 154 – 30 * 5 = 4。
    • 第四位的 1 ,是將 3 依照十進位制移到個位數(即 3),找出在 0 ~ 9 中 3 乘上的數字還可以小於 4 的答案,即是 1 ,並且 4 – 3 * 1 = 1。

但是這中間要做位移會用到被禁止使用的乘法,且要找出 0 ~ 9 去乘的動作也避不掉乘法,但是如果將兩邊改用二進位後,位移的部分就可以使用位元運算子(Bitwise Operator)中的 Shift ,並且因為二進位只會有 0 跟 1 ,所以只要知道位移完的數值有沒有小於剩下的數字即可,底下再舉個例子。

  • 10654(10100110011110) 除以 3(11) 等於 3551(110111011111)
    • 第一位的 1 ,是將 11 依照二進位制移到千億位數(即 1100000000000),找出位移完後的數字有沒有小於 10100110011110 ,有即是 1 ,並且 10100110011110 – 1100000000000 = 1000110011110。
    • 第二位的 1 ,是將 11 依照二進位制移到百億位數(即 110000000000),找出位移完後的數字有沒有小於 1000110011110 ,有即是 1 ,並且 1000110011110 – 110000000000 = 10110011110。
    • 第三位的 0 ,是將 11 依照二進位制移到十億位數(即 11000000000),找出位移完後的數字有沒有小於 10110011110 ,沒有即是 0 。
    • 第四位的 1 ,是將 11 依照二進位制移到億位數(即 1100000000),找出位移完後的數字有沒有小於 10110011110 ,有即是 1 ,並且 10110011110 – 1100000000 = 1010011110。
    • 第五位的 1 ,是將 11 依照二進位制移到千萬位數(即 110000000),找出位移完後的數字有沒有小於 1010011110 ,有即是 1 ,並且 1010011110 – 110000000 = 100011110。
    • 第六位的 1 ,是將 11 依照二進位制移到百萬位數(即 11000000),找出位移完後的數字有沒有小於 100011110 ,有即是 1 ,並且 100011110 – 11000000 = 1011110。
    • 第七位的 0 ,是將 11 依照二進位制移到十萬位數(即 1100000),找出位移完後的數字有沒有小於 1011110 ,沒有即是 0 。
    • 第八位的 1 ,是將 11 依照二進位制移到萬位數(即 110000),找出位移完後的數字有沒有小於 1011110 ,有即是 1 ,並且 1011110 – 110000 = 101110。
    • 第九位的 1 ,是將 11 依照二進位制移到千位數(即 11000),找出位移完後的數字有沒有小於 101110 ,有即是 1 ,並且 101110 – 11000 = 10110。
    • 第十位的 1 ,是將 11 依照二進位制移到百位數(即 1100),找出位移完後的數字有沒有小於 10110 ,有即是 1 ,並且 10110 – 1100 = 1010。
    • 第十一位的 1 ,是將 11 依照二進位制移到十位數(即 110),找出位移完後的數字有沒有小於 1010 ,有即是 1 ,並且 1010 – 110 = 100。
    • 第十二位的 1 ,是將 11 依照二進位制移到個位數(即 11),找出位移完後的數字有沒有小於 100 ,有即是 1 ,並且 100 – 11 = 1。

大致上的做法這樣做即可。其他比較需要注意的地方是要先用迴圈找到最高是幾位,以及雖然在 32-bit 整數裡唯一會 Overflow 的除法 -2147483648 除以 -1 ,所以只有這個答案會是直接拿32-bit 整數最大值做答案,但是其實要做 -2147483648 除以其他數字都還是很困難,所以還是用 64-bit 整數解這題會比較方便。

C++(12ms)

/*******************************************************/
/* LeetCode 29. Divide Two Integers                    */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2018/10/24                                 */
/*******************************************************/
#include <cstdlib>
#include <climits>

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

    bool hasSign = ((dividend < 0) != (divisor < 0));
    long long int p = abs((long long int)dividend);
    long long int q = abs((long long int)divisor);

    if(p < q) return 0;

    int maxShiftDigit = 0;
    while((q << maxShiftDigit) <= p) ++maxShiftDigit;

    int result = 0;
    for(int i = maxShiftDigit - 1 ; i >= 0 ; --i){
      unsigned int shiftValue = q << i;
      if(shiftValue <= p){
        result += (1 << i);
        p -= shiftValue;
      }
    }

    return hasSign ? -result : result;
  }
};
廣告

Comment

There is no comment on this post. Be the first one.

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: