”分治法“经典题型集锦-python实现_python分治算法题目

基本思想：

将一个问题分解为多个规模比较小的子问题，这些子问题互相独立并与原问题解决方案相同，递归求解这些子问题，然后将这些子 问题的解合并得到原问题的解。

分治法求解的基本步骤：

1、将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

2、明确最小子问题，递归最终的结束条件；

3、划分子问题，调用递归方法；

4、合并回溯后的结果

分治经典问题

（1）二分查找

（2）归并排序

（3）快速排序

（4）汉诺塔

（5）大整数乘法

（6）Strassen矩阵乘法

（7）线性时间选择

（8）最接近点对问题

（9）循环赛日程表

（10）棋盘覆盖

------------------------------------------------------精美的分割线-------------------------------------------------------

1、二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        def binarySearch(left,right):
            
            # 分治结束条件
            if left > right:
                return -1
            middle = int((right+left)/2)
 
            # 如果容易越界，可以改进写法  middle = int((right-left)/2+left)
            if nums[middle] == target:
                return middle
            # 问题划分为左边查找，或者右边查找，缩小范围
            if nums[middle]>target:
                return binarySearch(left,middle-1)
            else:
                return binarySearch(middle+1,right)
 
        last_n = len(nums)-1
        def binarySearch_2(left,right):
            '''
            改进版本，如果有重复的值，返回索引最小的那个
            :param left:
            :param right:
            :return:
            '''
            # 分治结束条件
            if left > right:
                if left <= last_n and nums[left] == target:
                    return left
                else:
                    return -1
            middle = int((right-left)/2+left)
            # 问题划分为左边查找，或者右边查找，缩小范围
            if nums[middle]>=target:
                return binarySearch_2(left,middle-1)
            else:
                return binarySearch_2(middle+1,right)
        return binarySearch_2(0,last_n)
if __name__ == '__main__':
    nums = [-1,0,3,3,3,5,9,12]
    target = 15
    s = Solution()
    r = s.search(nums, target)
    print(r)
 
    target = -2
    r = s.search(nums, target)
    print(r)
 
    target = -1
    r = s.search(nums, target)
    print(r)
 
    target = 3
    r = s.search(nums, target)
    print(r)

2、归并排序

执行过程：

• 把长度为n的输入序列分为两个长度为n/2的子序列；

• 对于这两个子序列分别采用归并排序；

• 将两个排序好的子序列合并为一个最终的排序序列。

#-*- coding: UTF-8 -*-
def merge_sort(arr):
    n = len(arr)
    # 结束条件，如果只有一个值的时候，返回自己本身
    if n<2:
        return arr
    # 划分的中间值
    middle = int(n/2)
    # 划分为左右两个子列表，分别排序
    son_arr1=merge_sort(arr[:middle])
    son_arr2=merge_sort(arr[middle:])
 
    # 进行合并，返回的是两个有序的序列
    len_1 = len(son_arr1)
    len_2 = len(son_arr2)
    i=0
    j=0
    result = []
    while i<len_1 or j<len_2:
        if i==len_1:
            # son_arr2还有内容没合并
            result.append(son_arr2[j])
            j+=1
        elif j==len_2:
            result.append(son_arr1[i])
            i += 1
        else:
            if son_arr1[i]>son_arr2[j]:
                result.append(son_arr2[j])
                j+=1
            else:
                result.append(son_arr1[i])
                i += 1
    return result
if __name__ == '__main__':
    arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    sort_arr = merge_sort(arr)
    print("排序后的结果:{}".format(sort_arr))

 

3、快速排序

执行过程：

• 从数列中挑出一个元素，称为 “基准”（pivot）；

• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准 就处于数列的中间位置。这个称为分区（partition）操作；

• 递归地把小于基准值元素的子数列和大于基准值元素的子数列进行快速排序。

# -*- coding: UTF-8 -*-
def quick_sort(arr, start=0, end=None):
    if end is None:
        end = len(arr) - 1
    if start >= end:
        return arr
    print('基准值',arr[start])
    pivot = start  # 令第一个位置的数为基准
    # 希望结果：比基准值的数放左边，比基准值大的数放右边，基准值在中间
    index = start + 1  # 从第二个数开始，和基准数比较
    # index 是从左到右，第个比基准大的位置，如果有发现比基准值小的数，则和这个位置交换顺序，index+1
 
    # 一轮遍历，找到比基准值小的数，就和第个比基准大的位置index上的数交换
    for i in range(index, end + 1):
        if arr[i] < arr[pivot]:
            if i != index: # 如果如果当前的数还是比基准值小的，那么直接移动；如果i!=index则表明有找到比较大的值，需要对换
                # 进行交换数据
                tmp = arr[index]
                arr[index]=arr[i]
                arr[i]=tmp
            index+=1
    # 此时基准还在第一个位置，需要和第index-1个数交换，index上的数是比基准大的
    tmp = arr[pivot]
    arr[pivot] = arr[index-1]
    arr[index-1]=tmp
 
    pivot = index-1 # 这是当前基准的位置，已经移到中间去了
    print(arr)
    quick_sort(arr,start,pivot-1)
    quick_sort(arr,pivot+1,end)
    return arr
 
if __name__ == '__main__':
    arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    sort_arr = quick_sort(arr)
    print("快排后的结果:{}".format(sort_arr))

4、汉诺塔

约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到右边的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
现在我们改变游戏的玩法，不允许直接从最左(右)边移到最右(左)边(每次移动一定是移到中间杆或从中间移出)，也不允许大盘放到下盘的上面。
Daisy已经做过原来的汉诺塔问题和汉诺塔II，但碰到这个问题时，她想了很久都不能解决，现在请你帮助她。现在有N个圆盘，她至少多少次移动才能把这些圆盘从最左边移到最右边？

过程分析

如果只是要算移动次数，可以推导出要给公式。假设有10个盘子需要移动，移动次数是f(10)；那么移动上面9个盘子到最右边的移动次数是f(9)，剩下一个最大的盘子在最左边，先把最大盘子移动中间移动1次，再把9个盘子移动到最左边也需要移动f(9)次，再把中间最大的盘子移动的最右边移动1次，接下来把最左边的9个盘子移动到最右边又是f(9)次。那么f(n)=3*f(n-1)+2，f(1)=2。那么就可以很容易得到你要的答案，比如f(2)=8，f(3)=26 ....，代码略。

如果允许直接从最左边移动到最右边，同样是三根柱子，又怎么推导？f(1)=1，直接移动到最右边；f(2)=3,第一个放中间，第二个放最右边，中间的移动到最右边；如果有n个盘子，先把n-1个盘子放到中间柱子，第n个盘子再移动到最右边，再把中间n-1个盘子移动到最右边，那么f(n)=2*f(n-1)+1。展开后用等比公式很容易得到${\color{Red} f(n)=2^{n}-1}$。继续拓展的话，考虑四根柱子，怎么算？

回到该题，最简单的三根柱子，不允许从最左移动到最右，如果要有中间过程，打印出怎么移动盘子的要怎么实现？那么可以用分治的思想，进行步骤分解。

def hanio_detail(start,end,n):
    '''
    3根柱子，不能从最左边直接移动到最右边
    :param start:
    :param end:
    :param n:
    :return:
    '''
    def print_h(start,end,num):
        print("{}，柱子{} --> 柱子{}".format(num,start,end))
    
    if n==1:
        print_h(start,2,n)
        print_h(2,end,n)
        return 2
    count = hanio_detail(start,end,n-1) # 先移动n-1个盘子到最右边
    count +=1
    print_h(start,2,n)
 
    count += hanio_detail(end,start,n-1) # 将n-1移动到最左边
    count+=1
    print_h(2,end,n)
 
    count += hanio_detail(start,end,n - 1)  # 将n-1移动到最右边
 
    return count
 
if __name__ == '__main__':
    r = hanio_detail(1,3,2)
    print(r)

5、大整数乘法

题目来源：http://poj.org/problem?id=2389

题目描述：输入两个大整数n1,n2（不超过40位数），计算两个大整数的乘积。（假设python也会精度溢出，不能用int表示超过2^32的数）

#-*- coding: UTF-8 -*-
def big_mul(str1,str2):
    def big_mul_zero(str1,str2,zeroNum):
        """
        大树相乘，zeroNum表示右多少个零
        :param str1:
        :param str2:
        :param zeroNum:
        :return:
        """
        n2=len(str2)
        # 结束条件
        if n2==1:
            num2=int(str2)
            n1 = len(str1)
            result = "0"*zeroNum
            carry=0 # 进位
            for idx in range(n1,0,-1):
                tmp = int(str1[idx-1]) * num2 + carry
                carry = tmp // 10
                c = str(tmp%10)
                result = c+result
            if carry>0:
                result = str(carry)+result
            return result
        str_last=str2[-1]
        # 分治，先算个位和大数相乘的结果，然后再迭代算剩下的结果
        big_num1=big_mul_zero(str1, str2[:-1], zeroNum + 1)
        big_num2=big_mul_zero(str1, str_last, zeroNum)
        return big_add(big_num1,big_num2)
    def big_add(str1,str2):
        """
        大树相加，各个位数和进位相加
        12345
        +
        23455
        :param str1:
        :param str2:
        :return:
        """
        n1 = len(str1)
        n2 = len(str2)
        i=n1-1
        j=n2-1
        result = ""
        carry = 0  # 进位
        while i>=0 or j>=0:
            if i<0:
                new_1=0
                new_2=int(str2[j])
                j-=1
            elif j<0:
                new_1 = int(str1[i])
                new_2 = 0
                i -= 1
            else:
                new_1=int(str1[i])
                new_2=int(str2[j])
                i-=1
                j-=1
            new_r = new_1+new_2 +carry
            carry = new_r //10
            result = str(new_r%10)+result
        if carry > 0:
            result = str(carry) + result
        return result
    if len(str2)<len(str1):
        tmp = str1
        str1=str2
        str2=tmp
    return big_mul_zero(str1,str2,0)
if __name__ == '__main__':
    import random
    for i in range(10):
        num1=random.randint(1,10000000000000000000000)
        num2=random.randint(1,100000000000000000000000000000000000000)
        print("num1",num1)
        print("num2",num2)
        str1 = str(num1)
        str2 = str(num2)
        print("真实值："+str(num1*num2))
        r = big_mul(str1,str2)
        print("计算值："+r)
        print("=="*30)
    # print(r)
    # print("12345679011110987654321")
    # print("22"+("0"*0))

6、Strassen矩阵乘法

略

7、线性时间选择

问题描述：给定线性无序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素。

问题分析：普通的排序算法，在最坏的情况下一般都需要O(n^2)的时间复杂度，如果数据集的取值范围给定且不是浮点数的话，我觉得用计数排序是最快能找得到Top K问题的解的，两个一层循环就能搞定。但是不能满足计数排序下要怎么办呢，线性时间选择用的思想是快速排序的思想，找一个基准值，将列表一分为二，左边比基准值小，右边比基准值大。如果左边的数量比k大，说明第k小的元素在左边，只需要继续遍历左边再进行快排操作即可；如果左边数量比k小，则说明第k小的元素在右边。

考虑优化问题：如果快排每次随机选择的数都是最小的，k选择n，则需要O(n^2)的时间复杂度。那么怎么优化呢，就是考虑快排这个基准值怎么选择的问题。在快排开始前，先对序列进行分组，每组5个数共n/5组，分别对每组做插入排序，然后找出每组的中位数，按照大小排序放在列表的开头。从这些中位数中再次选择一个中位数，作为快排起始的基准值。

总结：

线性时间选择其实就是————>>快速排序的加强版，

快速排序中的基准元素变为————>>分组后取得的各组中位数的中位数。

代码后续补充。。。

 

8、最接近点对问题

问题描述：n个点在公共空间中，求出所有点对的欧几里得距离最小的点对。

 

9、循环赛日程表

问题描述：一年一度的欧洲冠军杯马上就要打响，在初赛阶段采用循环制，设共有n队参加，初赛共进行（n-1）天，每队要和其他各队进行一场比赛。要求每队每天只能进行一场比赛，并且不能轮空。请按照上述需求安排比赛日程，决定每天各队的对手。

 

10、棋盘覆盖

问题描述：在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

如下是一种覆盖方式：C*2，B,D*2