六十八、快速冪算法、牛頓迭代法、累加數(shù)組+二分查找的變形

「@Author：Runsen」

?

編程的本質(zhì)來源于算法，而算法的本質(zhì)來源于數(shù)學(xué)，編程只不過將數(shù)學(xué)題進(jìn)行代碼化。「---- Runsen」

?

上次介紹了二分查找算法及其四個(gè)變形問題，下面介紹二分法常用的場景和典型的例題。

快速冪算法

題目是來自Leetcode：50. Pow(x, n)，https://leetcode-cn.com/problems/powx-n/

實(shí)現(xiàn) pow(x, n) ，即計(jì)算 x 的 n 次冪函數(shù)。

示例?1:

輸入:?2.00000,?10
輸出:?1024.00000

其實(shí)快速冪相關(guān)的問題，個(gè)人覺得只要你是一名程序員，就必須要掌握快速冪算法。

當(dāng)我們遇到一個(gè)問題需要讓我們求得一個(gè)數(shù) n 的 m 次方，那么最簡單的方法是將 n 乘以 m 次，得到結(jié)果，但是如果我們現(xiàn)在需要計(jì)算的是 2^10000000 這樣的式子呢，顯然如果我們的程序需要計(jì)算 2 的更高次方的時(shí)候這樣的算法，對于算法競賽而言時(shí)間上顯然是不允許的，因此提出了快速冪算法。

其實(shí)在計(jì)算這樣的式子的時(shí)候有大量的運(yùn)算步驟是可以避免的，我們現(xiàn)在拿 次方舉例：

按照上面的計(jì)算式，計(jì)算這樣的式子，我們需要進(jìn)行 8 次計(jì)算。

那么如果我們換一種思路來計(jì)算呢：，我們需要進(jìn)行 2 次計(jì)算。

快速冪實(shí)際上是分治思想的一種應(yīng)用。因此，可以得到：

下面就需要判斷n/2的奇偶的情況。

觀察發(fā)現(xiàn)，當(dāng) n 為奇數(shù)時(shí)，二分后會(huì)多出一項(xiàng) x 。比如：。

當(dāng)n為奇數(shù)，。

當(dāng)n為偶數(shù)，

根據(jù)推導(dǎo)，每次把冪從 n 降至 n//2 ，直至將冪降為 0 。

如果x = 0時(shí)：直接返回0，初始化 res = 1，

n?=?5
x?=?3
res?=?1
while?n:
??if?n?%?2?==?1:
????res?*=?x
??x?*=?x
??n?//=?2
print(res)

243

我們可以使用位運(yùn)算寫成比較高級(jí)的代碼。

快速冪算法如果x等于0，直接返回0。如果小于0 ，x需要取其倒數(shù)，n取其相反數(shù)。

class?Solution:
????def?myPow(self,?x:?float,?n:?int)?->?float:
????????if?x?==?0.0?:?return?0.0
????????res?=?1
????????if?n?0:?x,?n?=?1?/?x,?-n
????????while?n:
????????????if?n?&?1:?res?*=?x
????????????x?*=?x
????????????n?>>=?1
????????return?res

求x的平方根

題目是來自LeetCode 第 69題：x 的平方根，https://leetcode-cn.com/problems/sqrtx/

計(jì)算并返回 x 的平方根，其中 x 是非負(fù)整數(shù)。

#?由于返回類型是整數(shù)，結(jié)果只保留整數(shù)的部分，小數(shù)部分將被舍去。?
#?示例?1:?
#?輸入:?4
#?輸出:?2
#?示例?2:?
#?輸入:?8
#輸出:?2
#說明:?8?的平方根是?2.82842...,?
#?????由于返回類型是整數(shù)，小數(shù)部分將被舍去。

二分查找的下界為 0

這個(gè)題目的話，使用二分查找，low是0，high是數(shù)字 x/2 + 1。我們需要查找一個(gè)數(shù)mid的平方小于等于x。因此，可以進(jìn)行二分查找。需要注意的是返回的是high。

class?Solution:
????def?mySqrt(self,?x:?int)?->?int:
????????low?=?0?
????????high?=?int(x/2?+?1)
????????while?low?<=?high?:
????????????mid?=?(low?+?high)?//?2
????????????if?mid?**?2?==?x?:
????????????????return?mid
????????????elif?mid?**?2?>?x?:
????????????????high?=?mid?-?1
????????????elif?mid?**?2?????????????????low?=?mid?+?1
????????return?high

還有一種方法是牛頓法, 利用一階線性近似快速尋找最優(yōu)點(diǎn)。

牛頓迭代法是用切線來估計(jì)曲線，我們可以在某個(gè)點(diǎn)上做切線得到切線方程y=f’(x0)(x-x0)+f(x0)，然后找出切線與橫軸的交點(diǎn)，就是下一個(gè)迭代點(diǎn)。

迭代點(diǎn)和零點(diǎn)具體一個(gè)的關(guān)系：

牛頓法的公式具體推導(dǎo)：

最終得到：

比如求3的平方根，就是求曲線f(x)=x^2-3的零點(diǎn)，求導(dǎo)f’(x)=2*x，所以我們首先取x0=2，則x1 = 2 – 1 /4 = 1.75，然后x2 = 1.75 – [(1.75)^2 – 3]/(2*1.75) = 1.73214… 這個(gè)數(shù)就跟根號(hào)3很接近了。

class?Solution:
????def?mySqrt(self,?x:?int)?->?int:
????????if?x?2:
????????????return?x
????????x0?=?x
????????x1?=?x0/2?+?x/(x0*2)?
????????while?abs(x0?-?x1)?>=?1:
????????????x0?=?x1
????????????x1?=?x1?/?2?+?x?/?(x1?*?2)
????????return?int(x1)

有的時(shí)候，需要對平方根的誤差進(jìn)行估算，需要是小數(shù)點(diǎn)后6位，牛頓法瞬間解決。

def?mySqrt(x:?int)?->?int:
????if?x?2:
????????return?x
????x0?=?x
????x1?=?x0?/?2?+?x?/?(x0?*?2)
????while?abs(x0?-?x1)?>=?0.000001:
????????x0?=?x1
????????x1?=?x1?/?2?+?x?/?(x1?*?2)
????return?x1

print(mySqrt(3))
#?1.7320508075688772

寫作業(yè)（累加數(shù)組+二分查找的變形）

阿里云天池賽在線編程：在線編程限時(shí)賽。賽題鏈接：https://tianchi.aliyun.com/oj/9087601630820991/54270154473935464。此題為中等難度題目。

描述：n個(gè)人，他們每個(gè)人需要獨(dú)立做m份作業(yè)。第i份作業(yè)需要花費(fèi)cost[i]的時(shí)間。由于每個(gè)人的空閑時(shí)間不同，第i個(gè)人有val[i]的時(shí)間，這代表他做作業(yè)的總時(shí)間不會(huì)超過val[i]。每個(gè)人都按照順序，從1號(hào)作業(yè)開始，然后做2號(hào)，3號(hào)...... 現(xiàn)在，你需要計(jì)算出他們最多花了多少的時(shí)間。

1<=n<=100000 1<=m<=100000 1<=val[i]<=100000 1<=cost[i]<=100000

示例
樣例?1:

給定`cost=[1,2,3,5]`，`val=[6,10,4]`，返回`15`。
輸入:
[1,2,3,5]
[6,10,4]
輸出
15

解釋:
第一個(gè)人可以完成1號(hào)作業(yè)，2號(hào)作業(yè)，3號(hào)作業(yè)，1+2+3<=6。
第二個(gè)人可以完成1號(hào)作業(yè)，2號(hào)作業(yè)，3號(hào)作業(yè)，無法完成4號(hào)作業(yè)，1+2+3<=10，1+2+3+5>10。
第三個(gè)人可以完成1號(hào)作業(yè)，2號(hào)作業(yè)，無法完成3號(hào)作業(yè)，1+2<=4，1+2+3>4。
1+2+3+1+2+3+1+2=15，返回15。

樣例?2:


給定?`cost=[3,7,3,2,5]`,`val=[10,20,12,8,17,25]`,返回`78`.
輸入:
[3,7,3,2,5]
[10,20,12,8,17,25]
輸出:
78

解釋:
第一個(gè)人可以完成1號(hào)作業(yè)，2號(hào)作業(yè),?3?+?7<=10.
第二個(gè)人可以完成1號(hào)作業(yè)，2號(hào)作業(yè)，3號(hào)作業(yè)，4號(hào)作業(yè)和5號(hào)作業(yè),?3+7+3+2+5<=20
第三個(gè)人可以完成1號(hào)作業(yè)，2號(hào)作業(yè)，無法完成三號(hào)作業(yè),??3+7<=12,3+7+3>12.
第四個(gè)人可以完成1號(hào)作業(yè)，無法完成2號(hào)作業(yè)?,?3<=8,7+3>8.
第五個(gè)人可以完成1號(hào)作業(yè)，2號(hào)作業(yè)，3號(hào)作業(yè)，4號(hào)作業(yè)，無法完成5號(hào)作業(yè),3+7+3+2<=17,3+7+3+2+5>17.
第六個(gè)人可以完成1號(hào)作業(yè)，2號(hào)作業(yè)，3號(hào)作業(yè)，4號(hào)作業(yè)和5號(hào)作業(yè),?3+7+3+2+5<=25
3+7+3+7+3+2+5+3+7+3+3+7+3+2+3+7+3+2+5=78,?返回?78.

「這個(gè)題其實(shí)就是二分查找的變形，查找排序數(shù)組中，第一個(gè)大于目標(biāo)值的前一個(gè)值或者等于目標(biāo)值（數(shù)組中可能不存在目標(biāo)值）」。這個(gè)排序數(shù)組就是cost的累加數(shù)組。

class?Solution:
????"""
????@param?cost:?the?cost
????@param?val:?the?val
????@return:?the?all?cost
????"""
????def?doingHomework(self,?cost,?val):
????????#?Write?your?code?here.
????????sum?=?0
????????sums?=?[]
????????for?i?in?cost:
????????????sum?+=?i
????????????sums.append(sum)
????????result?=?0
????????for?n?in?val:
????????????if?n?!=?-1:
????????????????result?+=?binary_search(sums,?n)
????????return?result

def?binary_search(list,?num):
????if?num?>=?list[-1]:
????????return?list[-1]
????if?num?0]:
????????return?0
????left?=?0
????right?=?len(list)?-?1??#?注意1?low和high用于跟蹤在其中查找的列表部分
????while?left?????????mid?=?left?+?(right-left)?//?2
????????if?list[mid]?<=?num?and?list[mid?+1?]?>?num:
????????????return?list[mid]
????????elif?list[mid]?>?num??and?list[mid-1]?<=?num:
????????????return?list[mid?-1?]
????????elif?list[mid]?????????????left?=?mid?+?1
????????else:
????????????right?=?mid?-1
????return?0

「人生最重要的不是所站的位置，而是內(nèi)心所朝的方向。只要我在每篇博文中寫得自己體會(huì)，修煉身心；在每天的不斷重復(fù)學(xué)習(xí)中，耐住寂寞，練就真功，不畏艱難，奮勇前行，不忘初心，砥礪前行，人生定會(huì)有所收獲，不留遺憾 （作者：Runsen ）」

?

本文已收錄 GitHub，傳送門~^[1] ，里面更有大廠面試完整考點(diǎn)，歡迎 Star。

?

Reference