分治题解

Posted by 周思进 on August 16, 2020

最近学习积极性不高啊… 要控制啊 = =

将之前 ARTS 做的三个分治思想的题目单独整在一块再发下,方便后面回顾吧

一、归并排序

思路:
将数组拆分成两半,分别对这两半进行排序,然后将这排序后的两半再进行排序得到最终结果
将数组拆分两半的过程可以使用递归编程方式,直到无法再进行拆分为止

def merge(array: List, start: int, middle: int, end: int):
    len = end - start + 1
    new_array = [0] * len   # 先生成一个对应大小的空列表,方便后面直接通过索引赋值操作
    i = start
    j = middle + 1  # 位置不能搞错
    m = 0

    # print("old_array %s"%(array))

    while (i < middle + 1) and (j < end + 1):
        if (array[i] <= array[j]):
            new_array[m] = array[i]
            i += 1
        else:
            new_array[m] = array[j]
            j += 1
        m += 1

    while (i < middle + 1):
        new_array[m] = array[i]
        i += 1
        m += 1

    while (j < end + 1):
        new_array[m] = array[j]
        j += 1
        m += 1

    # print("new_array %s"%(new_array))
    for i in range(len):
        array[start + i] = new_array[i] #array数组的起始地址需要加上start


def merge_sort(array: List, start: int, end: int):
    if start >= end:
        return

    middle = (start + end) // 2
    merge_sort(array, start, middle)
    merge_sort(array, middle+1, end)

    # print("start :%s, middle : %s,  end %s"%(start, middle, end))
    merge(array, start, middle, end)

二、快速排序

快排的整体思路是先选择一个值,比如直接选择末尾值,然后将数组中的元素与该值进行比较,比这小的放左边, 比这大的放右边,这样操作完之后,选择的这个值在数组中的位置就是明确了的,剩下的就是将左边的数据和右 边的数据通过同样的方法进行操作,可以通过递归方式来完成

这里的重点是如何原地将数值进行左右分区,方式是通过数值交换,思路有点类似双指针,一个指向要被替换 的数值,一个用于遍历数组用,当遍历值比参考值小,则将遍历值与被替换值交换,同时替换指针指向下一个 数值,当遍历到最后一个数值,只需要将最后一个数组与被替换指针再交换下即可。


def partition(array:List, p:int, r:int) -> int:
    pivot = array[r]
    i = p

    for j in range(p, r):
        if array[j] < pivot:
            array[i], array[j] = array[j], array[i]
            i += 1

    array[i], array[r] = array[r], array[i]
    return i


def qsort_c(array:List, p:int, r:int):
    if p >= r:
        return
    
    q = partition(array, p, r)
    qsort_c(array, p, q-1)
    qsort_c(array, q+1, r)


def qsort(array:List, n:int):
    qsort_c(array, 0, n-1)


三、LeetCode-14. 最长公共前缀

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""
        return self.lcp(strs, 0, len(strs)-1)
    
    def lcp(self, strs, l, r):
        if l == r:
            return strs[l]
        
        mid = (l+r) // 2
        left = self.lcp(strs, l, mid)
        right = self.lcp(strs, mid+1, r)

        minlen = min(len(left), len(right))
        for i in range(minlen):
            if left[i] != right[i]:
                return left[:i]
        
        return left[:minlen]