经典算法思想1-分治算法

分而治之，分治算法（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)

---

参考

https://www.cnblogs.com/xsyfl/p/6921687.html