分治法

• 简化思维逻辑
原始问题往往非常复杂，例如排序问题。假设原始我们需要考虑对 1000 个数进行排序，那么利用分治思想我们可以分别对左右的 500 个数进行排序，然后考虑合并两个有序数组。当然，排序 500 个数看起来仍然不容易，但是我们可以继续分治下去，最终我们只需要考虑 1~2 个数的排序策略，这就是经典的归并排序的思想。

• 分布式算法
虽然在算法学习的过程中少有接触多进程和分布式等思想。但是随着 CPU core 越来越多，能够被分治法拆解的问题显然更方便进行并行计算，从而节省总体时间。因此分治思想在工程实现上具有重要的意义。

• 效率优化（并行计算情况下）
虽然我们不常用并行解决算法问题，但是在某些情况下仍然能够帮助我们节省计算代价，代表就是快速幂算法。

• 分解（Divide）
将问题划分为若干子问题，子问题的形式与愿问题一样，只是规模更小。

• 解决（Conquer）
如果子问题的规模足够小，则停止递归，直接求解。

• 合并（Combine）
将子问题的解组合成原问题的解。

最大连续数列

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:

        def cal(nums, start, end):
            if start >= end:
                return (nums[end], nums[end], nums[end])

            mid = (start + end) // 2
            leftRet = cal(nums, start, mid)
            rightRet = cal(nums, mid + 1, end)

            leftLarge =  max(leftRet[0], sum(nums[start: mid + 1]) + rightRet[0])
            rightLarge = max(rightRet[1], sum(nums[mid + 1: end + 1]) + leftRet[1])
            wholeLarge = max(leftRet[2], rightRet[2], leftLarge, rightLarge, leftRet[1] + rightRet[0])
            return(leftLarge, rightLarge, wholeLarge)

        ret = cal(nums, 0, len(nums) - 1)
        return ret[2]

搜索二维矩阵

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:

        def divide(i, j, k, l):
            if any(w < 0 for w in [i, j, k, l]) or any(w >= len(matrix) for w in [i, k]) or any(w >= len(matrix[0]) for w in [j, l]):
                return False
            if i > k or j > l:
                return False
            if target < matrix[i][j] or target > matrix[k][l]:
                return False
            if i == k and j == l:
                return target == matrix[i][j]

            midRow = (i + k) // 2
            midCol = (j + l) // 2
            return divide(i, j, midRow, midCol) or divide(i, midCol + 1, midRow, l) or divide(midRow + 1, j, k, midCol) or divide(midRow + 1, midCol + 1, k, l)

        return divide(0, 0, len(matrix) - 1, len(matrix[0]) - 1)

至少有 K 个重复字符的最长子串

class Solution(object):
    def longestSubstring(self, s, k):
        if not s:
            return 0
        for c in set(s):
            if s.count(c) < k:
                return max(self.longestSubstring(t, k) for t in s.split(c))
        return len(s)

为运算表达式设计优先级

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

示例 1:

输入: "2-1-1"
输出: [0, 2]
解释: 
((2-1)-1) = 0 
(2-(1-1)) = 2
示例 2:

输入: "2*3-4*5"
输出: [-34, -14, -10, -10, 10]
解释: 
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10