Python算法提升

此开源图书由ithaiq原创，创作不易转载请注明出处

基础算法

二分搜索

模板

from typing import List
​
​
def search(nums: List[int], target: int) -> int:
    l, r = 0, len(nums)-1
    while l <= r:
        mid = l+(r-l)//2
        if nums[mid] < target:
            l = mid+1
        elif nums[mid] > target:
            r = mid-1
        else:
            return mid
    return -1
​
​
def search(nums: List[int], target: int) -> int:
    start, end = 0, len(nums)-1
    while start + 1 < end:
        mid = start + (end - start) // 2
        if nums[mid] < target:
            start = mid
        else:
            end = mid
    if nums[start] == target:
        return start
    elif nums[end] == target:
        return end
    else:
        return -1

search-for-range

给定一个包含 n 个整数的已排序数组，要求找出给定目标值 target 的起始和结束位置。如果目标值不在数组中，则返回 [-1, -1]。

解题思路：关键是要找到目标值 target 在数组中第一次出现和最后一次出现的位置，因此可以利用两次二分搜索分别找到第一次和最后一次的位置。

def searchRange(A: List[int], target: int) -> List[int]:
    if len(A) == 0:
        return [-1, -1]
    result = [-1, -1]
    start = 0
    end = len(A) - 1
    while start + 1 < end:
        mid = start + (end - start) // 2
        if A[mid] > target:
            end = mid
        elif A[mid] < target:
            start = mid
        else:
            end = mid
    # 搜索左边的索引
    if A[start] == target:
        result[0] = start
    elif A[end] == target:
        result[0] = end
    else:
        return result
    start = 0
    end = len(A) - 1
    while start + 1 < end:
        mid = start + (end - start) // 2
        if A[mid] > target:
            end = mid
        elif A[mid] < target:
            start = mid
        else:
            start = mid
    # 搜索右边的索引
    if A[end] == target:
        result[1] = end
    elif A[start] == target:
        result[1] = start
    return result
​

search-a-2d-matrix

编写一个高效的算法来判断一个 m x n 的矩阵中是否存在目标值。该矩阵具有如下特性：

  1. 每行的元素从左到右按升序排列。

  2. 每行的第一个元素大于前一行的最后一个元素。

def searchMatrix(matrix: List[List[int]], target: int) -> bool:
    # 思路：将二维数组转为一维数组进行二分搜索
    if not matrix or not matrix[0]:
        return False
    row: int = len(matrix)
    col: int = len(matrix[0])
    start: int = 0
    end: int = row * col - 1
    while start + 1 < end:
        mid: int = start + (end - start) // 2
        # 获取二维数组对应值
        val: int = matrix[mid // col][mid % col]
        if val > target:
            end = mid
        elif val < target:
            start = mid
        else:
            return True
    if matrix[start // col][start % col] == target or matrix[end // col][end % col] == target:
        return True
    return False

first-bad-version

给定 n 个版本号 [1, 2, ..., n]，要找出导致之后所有版本出错的第一个错误的版本。可以通过调用 bool isBadVersion(version) 函数来判断版本号 version 是否出错。实现一个函数来查找第一个错误的版本。尽量减少对调用 API 的次数。

def firstBadVersion(n: int) -> int:
    # 思路：二分搜索
    start: int = 1
    end: int = n
    while start + 1 < end:
        mid: int = start + (end - start) // 2
        if isBadVersion(mid):
            end = mid
        elif not isBadVersion(mid):
            start = mid
    if isBadVersion(start):
        return start
    return end
​

find-minimum-in-rotated-sorted-array

寻找数组中经过旋转后的最小元素。假设数组在预先未知的某个点上进行了旋转（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]）(数组中不存在重复的元素)

def findMin(nums: List[int]) -> int:
    # 思路：将最后一个值作为target，然后往左移动，最后比较start、end的值
    if not nums:
        return -1
    start: int = 0
    end: int = len(nums) - 1
​
    while start + 1 < end:
        mid: int = start + (end - start) // 2
        # 最后一个元素值为 target
        if nums[mid] <= nums[end]:
            end = mid
        else:
            start = mid
    if nums[start] > nums[end]:
        return nums[end]
    return nums[start]
​

find-minimum-in-rotated-sorted-array-ii

寻找数组中经过旋转后的最小元素。假设数组在预先未知的某个点上进行了旋转（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]）(包含重复元素)

def findMin(nums: List[int]) -> int:
    # 思路：跳过重复元素，mid值和end值比较，分为两种情况进行处理
    if not nums:
        return -1
    start: int = 0
    end: int = len(nums) - 1
    while start + 1 < end:
        # 去除重复元素
        while start < end and nums[end] == nums[end - 1]:
            end -= 1
        while start < end and nums[start] == nums[start + 1]:
            start += 1
        mid: int = start + (end - start) // 2
        # 中间元素和最后一个元素比较（判断中间点落在左边上升区，还是右边上升区）
        if nums[mid] <= nums[end]:
            end = mid
        else:
            start = mid
    if nums[start] > nums[end]:
        return nums[end]
    return nums[start]

search-in-rotated-sorted-array

假设一个按照升序排序的数组在未知位置上进行了旋转（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]）。现在需要搜索给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1。(数组中不存在重复的元素)。

def search(nums: List[int], target: int) -> int:
    # 思路：两条上升直线，四种情况判断
    if not nums:
        return -1
    start: int = 0
    end: int = len(nums) - 1
    while start + 1 < end:
        mid: int = start + (end - start) // 2
        # 相等直接返回
        if nums[mid] == target:
            return mid
        # 判断在哪个区间，可能分为四种情况
        if nums[start] < nums[mid]:
            if nums[start] <= target <= nums[mid]:
                end = mid
            else:
                start = mid
        elif nums[mid] < nums[end]:
            if nums[mid] <= target <= nums[end]:
                start = mid
            else:
                end = mid
    if nums[start] == target:
        return start
    elif nums[end] == target:
        return end
    return -1

search-in-rotated-sorted-array-ii

假设一个按照升序排序的数组在未知位置上进行了旋转（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]）。现在需要搜索给定的目标值，判断给定的目标值是否存在于数组中。(数组中存在重复的元素)。

def search(nums: List[int], target: int) -> bool:
    # 思路：两条上升直线，四种情况判断，并且处理重复数字
    if not nums:
        return False
    start: int = 0
    end: int = len(nums) - 1
    while start + 1 < end:
        # 处理重复数字
        while start < end and nums[start] == nums[start + 1]:
            start += 1
        while start < end and nums[end] == nums[end - 1]:
            end -= 1
        mid: int = start + (end - start) // 2
        # 相等直接返回
        if nums[mid] == target:
            return True
        # 判断在哪个区间，可能分为四种情况
        if nums[start] < nums[mid]:
            if nums[start] <= target <= nums[mid]:
                end = mid
            else:
                start = mid
        elif nums[end] > nums[mid]:
            if nums[mid] <= target <= nums[end]:
                start = mid
            else:
                end = mid
    if nums[start] == target or nums[end] == target:
        return True
    return False

排序算法

快速排序

def QuickSort(nums: List[int]) -> List[int]:
    quickSort(nums, 0, len(nums)-1)
    return nums


def quickSort(nums: List[int], start: int, end: int) -> None:
    if start < end:
        pivot = random.randint(start, end)
        nums[end], nums[pivot] = nums[pivot], nums[end]
        left, right = partition(nums, start, end)
        quickSort(nums, start, left)
        quickSort(nums, right, end)

def partition(nums: List[int],start:int,end:int)->Tuple[int, int]:
    pivot = nums[end]
    left,right=start,end-1
    i=left
    while i<=right:
        if nums[i]<pivot:
            nums[i],nums[left]=nums[left],nums[i]
            left+=1
            i+=1
        elif nums[i]>pivot:
            nums[i],nums[right]=nums[right],nums[i]
            right-=1
        else:
            i+=1

    nums[left],nums[end]=nums[end],nums[left]
    return left-1,right+1

动态规划

数据结构

二叉树

链表

栈和队列

算法思维

递归思维

滑动窗口

二叉搜索树

回溯法

上一页Python进阶开发

最后更新于