原文轉載自「劉悦的技術博客」v3u.cn/a_id_159
北京的疫情一波未平一波又起,由此看來,戰“疫”將是一場曠日持久的戰爭,絕不能掉以輕心、輕易言勝。病毒隨時都會死灰復燃,以生命為代價換來的經驗教訓值得我們每一個人久久深思。筆者所在的小區也開始組織居民批量進行核酸檢測,本以為會是一幅摩肩接踵,水泄不通的場景,卻出人意料的井然有序、有層有次,效率非常高。原來檢疫部門採取了一種特別的策略:每五個人用一組試劑盒,進行快篩,分分鐘搞定了幾百人的社區檢測。
這裏解釋一下病毒核酸檢測的原理,檢測人員提取小區居民的鼻腔拭子或者咽拭子(就是用一根棉籤在咽喉處或者鼻腔深處刮取一些分泌物),然後將該棉籤放入試劑盒,以病毒獨特的基因序列檢測靶標,通過PCR擴增,使我們選擇的這段靶標DNA序列指數級增加,每一個擴增出來的DNA序列,都可與我們預先加入的一段熒光標記探針結合,產生熒光信號,擴增出來的靶基因越多,累計的熒光信號就越強。説白了就是試劑盒熒光反映變色越強烈,説明病毒體量和活性越強。
而五人一組共用一個試劑盒測試,如果結果呈陽性,再對其中四個人分別測試即可。 由於絕大部分人都是健康的,所以這樣可以提高五倍的檢測量,從而檢測更多的人,很明顯這次檢疫使用到了類似歸併的“分治法”來解決問題,提高效率。
分治法,即“分而治之”,出自清·俞樾《羣經平議·周官二》“巫馬下士二人醫四人”:“凡邦之有疾病者,疕瘍者造焉,則使醫分而治之,是亦不自醫也。” 其核心思想是:將一個難以直接解決的大問題,分拆成一些規模較小的相同問題,隨後各個擊破,分而治之。可以理解為:如果原問題可以分割成n個子問題,1<n<=原問題,且這些子問題均可解並且利用這些子問題的解求出原問題的解,那麼分治方法就是可行的。由分治法產生的子問題往往是原問題的較小模式,這就為使用遞歸算法提供了遍歷。反覆應用分治手段,可以使子問題與原問題類型一致而其規模卻不斷縮小,最終使子問題縮小到很容易直接求出其解。這自然導致遞歸的使用。所以分治與遞歸經常同時應用在算法解決方案中。
核酸檢測正好契合分治算法的使用場景:該問題的規模只要縮小到一定的規模就可以容易的解決。該問題可以分解為若干個規模較小的相同問題(檢測是否陽性)。
而我們在技術面試中,可以利用分治算法解決的經典問題如下:
歸併排序
def merge_sort(lst):
# 從遞歸中返回長度為1的序列
if len(lst) <= 1:
return lst
middle = len(lst) / 2
# 1.分解:通過不斷遞歸,將原始序列拆分成 n 個小序列
left = merge_sort(lst[:middle])
right = merge_sort(lst[middle:])
# 進行排序與合併
return merge(left, right)
def merge(left, right):
i, j = 0, 0
result = []
# 2.解決:比較傳入的兩個子序列,對兩個子序列進行排序
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 3.合併:將排好序的子序列合併
result.extend(left[i:])
result.extend(right[j:])
return result
複製代碼
快速排序
def quickSort(listx):
if len(listx)<=1:
return listx
pivot = listx[len(listx)//2] #取列表中中間的元素為被比較數pivot
listl = [x for x in listx if x < pivot] #<pivot的放在一個列表
listm = [x for x in listx if x ==pivot] #=pivot的放在一個列表
listr = [x for x in listx if x > pivot] #>pivot的放在一個列表
left = quickSort(listl) #遞歸進行該函數
right = quickSort(listr) #遞歸進行該函數
return left + listm + right #整合
print(quickSort([9,3, 6, 8, 9, 19, 1, 5])) #[1, 3, 5, 6, 8, 9, 9, 19]
複製代碼
折半查找
def binary_search(lis, key):
low = 0
high = len(lis) - 1
time = 0
while low < high:
time += 1
mid = int((low + high) / 2)
if key < lis[mid]:
high = mid - 1
elif key > lis[mid]:
low = mid + 1
else:
# 打印折半的次數
print("times: %s" % time)
return mid
print("times: %s" % time)
return False
複製代碼
二叉樹的最大深度問題
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
left = self.maxDepth(root.left) + 1
right = self.maxDepth(root.right) + 1
return left if left > right else right
複製代碼
計算x 的 n 次冪問題
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if not n:
return 1
if n < 0:
return 1 / self.myPow(x, -n)
if n % 2:
return (x * self.myPow(x, n - 1))
return self.myPow(x * x, int(n / 2))
複製代碼
當然了,分治算法也並非無懈可擊,回到核酸檢測的場景,這種做法在最樂觀情況下,的的確確是提升了五倍的效率,但是在最不樂觀情況下,反而會增大工作量。如果在檢測這些人中一個感染的患者都沒有,那就是最樂觀情況,5人一組檢查一遍就OK了;如果這羣人全部(正確來講是在分組後的每一組中都有至少一個)感染人員,這種極端惡劣的情況下會導致至少增加分組數量的工作量,所以根本問題又變成了在假設一定感染率的情況下,如何確定多少個樣本一組檢測比較好。考慮的因素可能包括,檢測效率,費用,有陽性的時候快速定位等。實際監測的時候,還可以不同地區不同的檢測策略,監測策略也可以根據檢測結果調整。
結語:算法其實在生活中無處不在,很多同學出去面試時往往懼怕做算法題,其實算法也不過就是一種解決問題的方法,目的也僅僅是為了提高效率,如果在生活中多觀察、多思考,也許會對算法能力的提升有一定的幫助。
原文轉載自「劉悦的技術博客」 v3u.cn/a_id_159