iT邦幫忙

2025 iThome 鐵人賽

DAY 29
0
自我挑戰組

用java解Leetcode系列 第 29

用java解Leetcode Day29

  • 分享至 

  • xImage
  •  

https://ithelp.ithome.com.tw/upload/images/20251013/201695013F8OipT5Vb.pnghttps://ithelp.ithome.com.tw/upload/images/20251013/20169501IITmvxUHnm.png

  1. Divide Two Integers
    這題要求在不使用乘法、除法和模數運算子的情況下實現兩個整數的除法。
    核心概念:利用減法和位移操作
    除法本質上是重複的減法。例如,10÷3 可以看作是從 10 中減去 3 多少次:

10−3=7 (1 次)

7−3=4 (2 次)

4−3=1 (3 次)

1<3,停止。
商就是 3。

然而,如果僅僅使用簡單的重複減法,當被除數(dividend)很大而除數(divisor)很小時(例如 2^31−1÷1),會導致時間複雜度太高(O( dividend/divisor)),這是不可接受的。

為了提高效率,我們需要利用 位移運算(Bitwise Shift),這能讓我們在對數時間內(O(logN))完成除法。

優化方法:指數級減法
我們希望一次減去多個除數,而不是一個一個地減。由於我們不能用乘法,我們可以利用**左位移操作(<<)**來實現 2 的冪次乘法,例如:

3×2^1=3≪1=6

3×2^2=3≪2=12
具體步驟如下:

  1. 處理邊界條件 (Edge Cases): 特別是溢位情況。
  2. 確定符號 (Sign): 由於位移操作主要適用於正數,我們通常將兩者都轉換為負數(或絕對值),在計算完商後再應用正確的符號。這裡選擇轉換為負數是因為在 32 位元整數範圍內,負數的範圍比正數大( 的絕對值 無法用正數 表示),使用負數可以避免處理 這個特殊的絕對值溢位問題。
  3. 重複減法與位移:
    o 從最大的 倍的 divisor 開始,檢查是否可以從 dividend 中減去。
    o divisor 左移 位(即 )如果仍然 dividend,則執行減法:
     dividend 減去 。
     商 (quotient) 加上 。
    o 不斷重複此過程,直到 dividend 小於 divisor。

上一篇
用java解Leetcode Day28
下一篇
用java解Leetcode Day30
系列文
用java解Leetcode30
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言