原文轉載自「劉悦的技術博客」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