分治法

分治法，顾名思义分而治之分为3个步骤：
分：将一个复杂的问题分成多个性质相同但规模更小的子问题
治：对子问题分别进行处理
合：将子问题的解进行合并，从而得到原问题的解
动态规划和分治法都基于递归思想，区别在于动态规划分解后的子问题有重复，分治法的子问题通常不会重复。
分治法问题具有以下特征：
1、问题规模缩小到一定程度可以很容易被解决
2、问题可以分解为若干个规模较小的相同性质的问题
3、问题的解等于子问题解的合并
4、问题分解的各个子问题相互独立，没有重复。

NO.23 合并k个排序链表
ListNode list = new ListNode()初始化应该空节点，无值
ListNode list = new ListNode(0)初始化应该节点值为0的空节点
将K个链表进行两两合并，每轮过后k个链表被合并成k/2个链表，如果k是奇数，则将最后一个链表单独作为一对。
重复上述过程，得到最终的有序链表共进行log2(k)轮合并
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        amount = len(lists)#需要合并的长度
        interval = 1#间隔从1开始，从此翻倍
        while interval < amount:
            for i in range(0, amount - interval, interval *2):
                lists[i] = self.mergeTwoLists(lists[i], lists[i + interval])#两两合并，两个链表范围是从i以及i+interval
            interval *= 2#间隔翻倍，假如放在里面到最后会超出范围
        return lists[0] if amount > 0 else None#最后返回链表，只剩下一个链表
    
    def mergeTwoLists(self, l1, l2):
        head = point = ListNode(0)#建立节点值为0的空节点
        while l1 and l2:#两个链表比较，较小的连接的链表后面
            if l1.val <= l2.val:
                point.next = l1
                l1 = l1.next#每次结束链表需往后走
            else:
                point.next = l2
                l2 = l2.next
            point = point.next#每次结束结果链表也向后加1
        if not l1:
            point.next = l2
        else:
            point.next = l1
        return head.next#返回头节点的下一个节点

NO.21 合并两个有序链表
方法就是合并K个有序链表里面的函数，整体比较简单，建立空链表后将l1和l2中较小的依次插入，如果其中一个为空时，将剩下的合并到节点后面
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = point = ListNode(0)
        while list1 and list2:
            if list1.val <= list2.val:
                point.next = list1
                list1 = list1.next
            else:
                point.next = list2
                list2 = list2.next
            point = point.next
        
        if not list1:
            point.next = list2
        else:
            point.next = list1
        
        return head.next

NO.215 数组中的第k大元素

法一：排序，然取第k大值
sort(cmp = None, key = None, reverse = False)用于排序，直接对原列表进行排序，会改变原列表的顺序
cmp:可选参数，如果指定了就会使用该参数的方法进行排序
key:指定使用待排序元素中的哪一项进行排序，比如说每个元素有多个数据域是
reverse：默认False，升序排序；若要降序，reverse = True
sorted是建立一个新的数组后排序，不会改变原数组。

法二：快速选择
跟快速排序类似，选择pivot以后递归，但是只用选半边递归，当第k大元素在等于基准值的子数组中时，直接返回该元素
def findKthLargest(self, nums: List[int], k: int) -> int:
        def quick_select(nums, k):
            pivot = random.choice(nums)#随机选择基准值
            small, equal, big = [], [] , []#三路划分
            for num in nums:
                if num < pivot:
                    small.append(num)
                elif num > pivot:
                    big.append(num)
                else:
                    equal.append(num)
            if k <= len(big):#此时值在大于基准值的数组中
                return quick_select(big, k)
            if k > len(big) + len(equal):#
                return quick_select(small, k - len(big) - len(equal))
            return pivot
        return quick_select(nums, k)
此法使用了random包，部分公司面试不行

法三：堆排序
堆heap是一种具体的数据结构，优先级队列priority queue是一种抽象数据结构，可以通过堆、二叉搜索树、链表等多种方式实现优先级队列
堆是一种特殊的完全二叉树，每个上级节点的值都小于等于它的下级节点
add操作：添加元素到末尾，并且调整堆满足结构要求
pop操作：弹出堆顶元素后，将末尾元素移到堆顶，然后继续调整知道满足结构要求。
heapq使用列表实现堆
heapify(x):将无序list x转换成小根堆
heappush(heap, item):将元素插入到序列尾端，然后从堆的最下向上调整，直到满足小顶堆结构
heappop(heap):从序列中弹出最小值
heappushpop(heap, item):先将item元素插入堆heapq中，然后弹出最小元素
heapreplace(heap, item):先弹出最小元素，而后将item插入到heapq序列中
merge(*iterables, key = None, reverse = False):将多个序列合并为一个堆，并且排序
nlargest(n, iterable, key = None):从一个序列中取出最大的n个元素
nsmallest(n, iterable, key = None):从一个序列中取出最小的n个元素
def findKthLargest(self, nums: List[int], k: int) -> int:
        h = []#建立存储堆
        for num in nums:
            heapq.heappush(h, num)#入堆
            if len(h) > k:#如果长度超过
                heapq.heappop(h)#删除
        return h[0]#返回堆顶，即数组的第一个值，即为第k大元素

NO.240 搜索二维矩阵II

法一：暴力搜索，挨个枚举直到找到，返回True
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == target:
                    return True
        return False

法二：将矩阵逆时针旋转45度，类似于搜索二叉树
从矩阵左下角元素matrix[i][j]开始遍历：
如果matrix[i][j] > target:消去最下面一行
如果matrix[i][j] < target：消去最左侧一列
如果matrix[i][j] == target:返回True
否则返回False
#从左下角开始
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        i, j = m - 1, 0
        while i >= 0 and j < n:
            if matrix[i][j] > target:
                i -= 1
            elif matrix[i][j] < target:
                j += 1
            else:
                return True
        return False

从右上角开始
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n - 1
        while i < m and j >= 0:
            if matrix[i][j] > target:
                j -= 1
            elif matrix[i][j] < target:
                i += 1
            else:
                return True
        return False 记下来

bisect() = bisect_right()
bisect_right()与bisect_left()的区别
bisect_right(ls, x)：返回大于x的第一个下标
bisect_left(ls, x)：返回大于等于x的第一个下标
当列表中没有x：返回的是一样的
当列表中只有一个元素等于X：bisect_left(ls, x)返回x的索引，bisect_right(ls, x)返回x的索引+1
当列表中有多个元素等于X：bisect_left(ls, x)返回第一个x的索引，bisect_right(ls, x)返回最右边的那个索引加1