分而治之，分治算法（divide and conquer），是计算机科学中非常重要的算法之一。该算法的核心思想可概括为，分解与合并。即把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
可采用分治算法解答的问题的基本特征
- 该问题缩小到一定规模能够容易的解决
- 该问题可以分解为若干个规模相同的子问题，即具有最优子结构性质
- 计算得到的子问题的解可以合并
- 该问题分解出的各个子问题相互独立
以上性质中，以第四条最为关键。否则可以采用贪婪算法或动态规划算法完成。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治算法实例
归并排序算法
def merge_sort(alist):
if len(alist)<=1:
return alist
mid=len(alist)//2
left=merge_sort(alist[:mid])
right=merge_sort(alist[mid:])
return merge(left,right)
## 需要另开一个列表存储已排序的序列
def merge(left,right):
l,r=0,0
s=[]
while l<len(left) and r<len(right):
if left[l] < right[r]:
s.append(left[l])
l += 1
else:
s.append(right[r])
r += 1
## 将一个列表合并到已有列表，应当使用extend（比+代价更小）。append只是增加一个元素。
s.extend(left[l:]) if l<len(left)
s.extend(right[r:]) if r<len(right)
return s
查找最长公共前缀字符串
https://leetcode-cn.com/problems/longest-common-prefix/
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
def lcp(start, end):
if start == end:
return strs[start]
mid = (start + end) // 2
lcpLeft, lcpRight = lcp(start, mid), lcp(mid + 1, end)
minLength = min(len(lcpLeft), len(lcpRight))
for i in range(minLength):
if lcpLeft[i] != lcpRight[i]:
return lcpLeft[:i]
return lcpLeft[:minLength]
return "" if not strs else lcp(0, len(strs) - 1)
