原文转载自「刘悦的技术博客」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
