数据结构与算法题解

数据结构与算法题解：旨在使用Python语言解决面试中常见的算法编程题（持续更新）。
更多用Python实现的算法参见 TheAlgorithms/Python

编者：袁宵

人生苦短，我用 Python

算法题

在 m*n 的乘法表中找到第k小的数的值

def find_Kth_Number(m, n, k):
    """
    在 m*n 的乘法表中找到第k小的数的值
    :param m: 乘法表行数
    :param n: 乘法表列数
    :param k: 第k小的数
    :return: 第k小的数的值
    输入: m = 3, n = 3, k = 5
    输出: 3
    解释:
    乘法表:
    1	2	3
    2	4	6
    3	6	9
    第5小的数字是 3 (1, 2, 2, 3, 3).
    """
    left = 1
    right = m * n
    while left < right:
        count = 0
        mid = left + (right - left) // 2
        for i in range(1, m + 1):
            if mid > n * i: # mid大于n*i，那么这一行的数都算进去
                count += n
            else:
                count += mid // i # mid在第i行排的次序
        if count < k:
            left = mid + 1
        else:
            right = mid
    return left

if __name__ == "__main__":
    m, n, k = list(map(int, input().split(" ")))
    print(find_Kth_Number(m, n, k))

查找数组中元素的最大值与最小值

def GetMaxAndMin(array):
    """
    查找数组中元素的最大值与最小值
    :param array: 数组
    :return: 数组中的最大值和最小值
    使用二分查找思想
    时间复杂度 3n/2 - 2，空间复杂度 1
    """
    array_len = len(array)
    if array is None or array_len == 0:
        return None
    array_max = array[0]
    array_min = array[0]
    # 两两分组，把较小的数放在左半部分，较大的数放在右半部分
    for i in range(0, array_len - 1, 2):
        if array[i] > array[i+1]:
            array[i], array[i+1] = array[i+1], array[i]
    # 在各个分组中的左半部分找最小值
    for i in range(0, array_len, 2):
        if array_min > array[i]:
            array_min = array[i]
    # 在各个分组中的右半部分找最大值
    for i in range(1, array_len, 2):
        if array_max < array[i]:
            array_max = array[i]
    # 如果数组元素个数是奇数个，最后一个元素被分为一组，需要特殊处理
    if array_len % 2 == 1:
        if array_min > array[-1]:
            array_min = array[-1]
        elif array_max < array[-1]:
            array_max = array[-1]
    return (array_min, array_max)

if __name__ == "__main__":
    array = list(map(int, input().strip().split()))
    print(GetMaxAndMin(array))

def GetMaxAndMin(array):
    """
    查找数组中元素的最大值与最小值
    :param array: 数组
    :return: (最小值,最大值) 元组
    使用二分查找思想
    时间复杂度 3n/2 - 2
    """
    array_len = len(array)
    if array is None or array_len == 0:
        return None

    def _recursive_operation(array, left, right):
        mid = (left + right) // 2 # 求中点
        if left == right: # left 和 right 间只有一个元素
            return (array[mid], array[mid])
        if left + 1 == right: # left 和 right 间只有两个个元素
            if array[left] > array[right]:
                return (array[right], array[left])
            else:
                return (array[left], array[right])
        # 递归计算左半部分
        left_array = _recursive_operation(array, left, mid)
        # 递归计算右半部分
        right_array = _recursive_operation(array, mid+1, right)
        # 总的最小值
        array_min = left_array[0] if left_array[0] < right_array[0] else right_array[0]
        # 总的最大值
        array_max = left_array[1] if left_array[1] > right_array[1] else right_array[1]
        return (array_min, array_max)

    return _recursive_operation(array, 0, array_len-1)

if __name__ == "__main__":
    array = list(map(int, input().strip().split()))
    print(GetMaxAndMin(array))

查找旋转数组中的最小元素

"""
有一个数组X[0...n-1]，现在把它分为两个子数组：X1[0...m] 和 X2[m+1...n-1]，
交换者两个子数组，使数组X由X1X2变成X2X1，求变换后数组X的最小值。
例如 X=[1,2,3,4,5,6,7,8,9]，X1=[1,2,3,4,5]，X2=[6,7,8,9]，
交换后，X=[6,7,8,9,1,2,3,4,5]
"""
def GetMin(array):
    """
    查找旋转数组中的最小元素
    :param array: 旋转数组
    :return: 最小值
    时间复杂度 :大部分情况 log2N，极端情况 N
    最容易想到的是直接遍历法，但是没有用到旋转数组的特性，时间复杂度为N。
    可以用二分法解决。
    """
    array_len = len(array)
    if array is None or array_len == 0:
        return None
    left = 0
    right = array_len - 1

    def _recursive_operation(array, left, right):
        mid = (left + right) // 2 # 求中点
        # 判断 array[mid] 是否为最小值
        if (mid - 1) >= left and array[mid] < array[mid - 1]:
            return array[mid]
        # 判断 array[mid + 1] 是否为最小值
        elif (mid + 1) <= right and array[mid + 1] < array[mid]:
            return array[mid + 1]
        # left 和 right 间只有一个元素
        elif left == right:
            return array[mid]
        # left 和 right 间只有两个个元素
        elif left + 1 == right:
            return array[left] if array[right] > array[left] else array[right]
        # 如果 array[right] > array[mid]，则最小值一定在数组左半部分
        elif array[right] > array[mid]:
            return _recursive_operation(array, left, mid)
        # 如果 array[mid] > array[left]，则最小值一定在数组右半部分
        elif array[mid] > array[left]:
            return _recursive_operation(array, mid, right)
        else: # array[right] == array[mid] 且 array[mid] == array[left]，
            # 无法确定最小值所在位置，只能对左右两部分分别查找
            # 递归计算左半部分
            left_min = _recursive_operation(array, left, mid)
            # 递归计算右半部分
            right_min = _recursive_operation(array, mid+1, right)
            # 总的最小值
            array_min = left_min if left_min < right_min else right_min
        return array_min

    return _recursive_operation(array, left, right)

if __name__ == "__main__":
    array = list(map(int, input().strip().split()))
    print(GetMaxAndMin(array))

生成旋转数组

def swap(array, left, right):
    while left < right:
        array[right], array[left] = array[left], array[right]
        left += 1
        right -= 1

def rotateArray(array, division_location):
    """
    生成旋转数组
    :param array: 顺序数组
    :param division_location: 旋转的位置
    :return: 旋转数组
    先分别把两个子数组内容交换，然后再把整个数组内容交换。
    """
    if len(array) <= 1:
        return array
    swap(array, 0, division_location)
    swap(array, division_location+1, len(array) - 1)
    swap(array, 0, len(array) - 1)

if __name__ == "__main__":
    division_location = int(input())
    array = list(map(int, input().strip().split()))
    rotateArray(array, division_location)
    print(array)

找出数组中第k小的数

def find_small_k_number(array, k):
    """
    找出数组中第k小的数
    :param array: 整数数组
    :return: 第k小的数
    部分快速排序方法
    """

    def quick_sort_operation(array, left, right, k):
        i = left
        j = right
        split_elem = array[i]
        # 把大于等于split_elem的数放在数组右边，把小于split_elem的数放在数组左边
        while i < j:
            while i < j and array[j] >= split_elem:
                j -= 1
            array[i] = array[j]
            while i < j and array[i] < split_elem:
                i += 1
            array[j] = array[i]
        # 当i=j时，i就是split_elem插入数组的位置，且表示该split_elem就是数组中排行第i的数
        array[i] = split_elem
        # 小于split_elem的数字个数
        left_sub_array_item_number = i - left
        # 如果小于split_elem的数字个数恰好为 k-1，那么 i 对应的位置就是第k小数字的位置
        if left_sub_array_item_number == k - 1:
            return array[i]
        # 如果小于split_elem的数字个数大于 k-1，那么只需在array[low, i-1] 中继续寻找
        elif left_sub_array_item_number > k - 1:
            return quick_sort_operation(array, left, i - 1, k)
        # 在array[i+1, high]中寻找第 k - left_sub_array_item_number - 1 的数字
        else:
            return quick_sort_operation(array, i + 1, right, k - left_sub_array_item_number - 1)

    return quick_sort_operation(array, 0, len(array) - 1, k)


if __name__ == "__main__":
    k = int(input())
    array = list(map(int, input().strip().split()))
    print(find_small_k_number(array, k))

找出数组前3大的数

def findTop3(array):
    """
    查找数组中前三大的数
    :param array: 长度不小于3的数组
    :return: (num1, num2, num3) 数组中值最大的3个数组成的元组
    时间复杂度: O(N)
    """
    if len(array) < 3:
        return -1
    r1 = r2 = r3 = - 2**31
    for item in array:
        if item > r1:
            r3 = r2
            r2 = r1
            r1 = item
        elif item > r2:
            r3 = r2
            r2 = item
        elif item > r1:
            r3 = item
    return (r1, r2, r3)

if __name__=="__main__":
    array = list(map(int, input().strip().split(" ")))
    print(findTop3(array))

找出数组前K大的数

def heap_adjust(array, start, end):
    """调整堆为小顶堆"""
    temp = array[start]
    child = 2 * start
    while child <= end:
        if child < end and array[child] > array[child + 1]:
            child += 1
        if temp <= array[child]:
            break
        array[start] = array[child]
        start = child
        child = start * 2
    array[start] = temp

def findTopK(array, K):
    """
    找出数组中前K大的数
    :param array: 数组
    :param K: 前K大的数
    :return: (num1,..,numK) 前K大的数组成的元组
    当K和数组长度比较大的时候，适合用“堆”方法找出数组中前K大的数
    时间复杂度 O(N*log_2 K)
    """
    if len(array) < K:
        return -1
    top_k_heap = [0] + array[0:K]  # 添加辅助位置0
    top_k_heap_len = K
    # 现在的待排序序列构建成一个小顶堆
    for start in range(top_k_heap_len // 2, 0, -1):  # 对 input_list_len // 2 个父亲节点处理
        heap_adjust(top_k_heap, start, top_k_heap_len)

    for item in array[K:]:
        if item > top_k_heap[1]:
            top_k_heap[1] = item
            heap_adjust(top_k_heap, 1, top_k_heap_len)
    # 逐步将堆结构转换为排序好的数列

    # 逐步将每个最小值的根结点与末尾元素交换，并且再调整其成为小顶堆
    for end in range(top_k_heap_len, 1, -1):  # 遍历次数，需要找到 input_list_len - 1 次最值来交换
        top_k_heap[1], top_k_heap[end] = top_k_heap[end], top_k_heap[1]  # 交换最值
        heap_adjust(top_k_heap, 1, end - 1)  # 重新调整堆

    del top_k_heap[0] # 删除辅助位置0
    return tuple(top_k_heap)


if __name__=="__main__":
    K = int(input())
    array = list(map(int, input().strip().split(" ")))
    print(findTopK(array, K))

找三个有序数组的公共元素

def find_common(ar1, ar2, ar3):
    """
    找三个有序数组的公共元素
    """
    i, j, k = 0, 0, 0
    n1, n2, n3 = len(ar1), len(ar2), len(ar3)
    while i < n1 and j < n2 and k < n3:
        if ar1[i] == ar2[j] and ar2[j] == ar3[k]:
            print(ar1[i])
            i += 1
            j += 1
            k += 1
        elif ar1[i] < ar2[j]:
            i += 1
        elif ar2[j] < ar3[k]:
            j += 1
        else:
            k += 1


if __name__ == '__main__':
    ar1 = list(map(int, input().split()))  # 2 5 12 20 45 85
    ar2 = list(map(int, input().split()))  # 16 19 20 85 200
    ar3 = list(map(int, input().split()))  # 3 4 15 20 39 72 85 190
    find_common(ar1, ar2, ar3)  # 20 85

求数组中两个元素的最小距离

def min_distance(array, num1, num2):
    """
    求数组中两个元素的最小距离
    :param array: 数组
    :param num1: 元素1
    :param num2: 元素2
    :return: 最小距离
    时间复杂度 O(N)
    动态规划方法，把每次遍历的结果都记录下来。
    这里利用了最小距离一定是依次遍历数组时最近访问的两个位置（局部性）。
    """
    if len(array) < 2 or num1 not in array or num2 not in array:
        return -1

    min_d = 2 ** 31
    last_position_1 = -1
    last_position_2 = -1

    for idx, item in enumerate(array):
        if num1 == item:
            last_position_1 = idx
            if last_position_2 >= 0:
                min_d = min(min_d, last_position_1 - last_position_2)
        if num2 == item:
            last_position_2 = idx
            if last_position_1 >= 0:
                min_d = min(min_d, last_position_2 - last_position_1)
    return min_d


if __name__ == "__main__":
    num1, num2 = list(map(int, input().strip().split(" ")))
    array = list(map(int, input().strip().split(" ")))
    print(min_distance(array, num1, num2))

异或法

def swapTwoInteger(a, b):
    """
    使用异或操作交换整数值
    :param a: int
    :param b: int
    :return: (b, a)
    """
    a = a ^ b
    b = a ^ b
    a = a ^ b
    return a, b
if __name__ == "__main__":
    a, b = list(map(int, input().strip().split(" ")))
    print(swapTwoInteger(a, b))

def findDuplicateNumber(array):
    """
    查找数组中重复的整数
    :param array: n-1 个整数组成的未排序的数组序列，其元素是1到n中不同的整数。
    :return: 数组序列中重复的整数
    时间复杂度：n，空间复杂度 1
    """
    array_len = len(array)
    # a = 1^2^3..(m)^(m)..^n
    a = array[0]
    i = 1
    while i < array_len:
        a = a ^ array[i]
        i += 1
    # b = 1^2^3..^n
    b = 1
    i = 2
    while i < array_len:
        b = b ^ i
        i += 1
    # a ^ b = (1^1)^(2^2)...(m^m^m)...^(n^n) = m
    return a ^ b


if __name__ == "__main__":
    array = list(map(int, input().strip().split()))
    print(findDuplicateNumber(array))

def findMissedNumber(array):
    """
    查找数组中丢失的整数
    :param array: n-1 个整数组成的未排序的数组序列，其元素是1到n中不同的整数。
    :return: 数组序列中缺失的整数
    时间复杂度：n，空间复杂度 1
    """
    array_len = len(array)
    # a = 1^2^3..(m-1)^(m+1)..^n
    a = array[0]
    i = 1
    while i < array_len:
        a = a ^ array[i]
        i += 1
    # b = 1^2^3..^n
    b = 1
    i = 2
    while i < array_len + 2:
        b = b ^ i
        i += 1
    # a ^ b = (1^1)^(2^2)...(m-1)^(m-1)^m^(m+1)^(m+1)^...^(n^n) = m
    return a ^ b


if __name__ == "__main__":
    array = list(map(int, input().strip().split()))
    print(findMissedNumber(array))

def find_single(array):
    """
    找出特殊数组中的任意一个特殊的数
    :param array: 一个数组，除了三个数是唯一的，其余的数出现偶数次
    :return: 任意一个特殊的数
    """
    i = 0
    # 遍历数字二进制位的每一位
    while i < 32:
        result1 = result2 = count1 = count2 = 0
        # 遍历数组的每个数字，并根据数字的第i为是否为1进行分类
        for item in array:
            if (item >> i) & 1 == 1:
                result1 ^= item
                count1 += 1
            else:
                result2 ^= item
                count2 += 1
        # 如果result1某次计数count1为奇数且result2的结果不为零
        # 说明result1结果里面只包含了一个出现次数为1的数
        if count1 % 2 == 1 and result2 != 0:
            return result1
        if count2 % 2 == 1 and result1 != 0:
            return result2
    return -1

if __name__ == "__main__":
    array = list(map(int, input().strip().split(" ")))
    print(find_single(array))

求数组连续最大和

def max_sub_array(array):
    """
    求数组连续最大和
    :param array: 数组
    :return: 数组连续最大和
    时间复杂度 O(N) 空间复杂度 O(1)
    """
    n = len(array)
    n_sum= array[0] # 到第i个数的最大累加和
    sub_max = array[0] # 累加和end中的最大值
    i = 1
    while i < n:
        n_sum = array[i] if n_sum <= 0 else array[i] + n_sum
        sub_max = n_sum if n_sum > sub_max else sub_max
        i += 1
    return sub_max

if __name__ == "__main__":
    array = list(map(int, input().strip().split(" ")))
    print(max_sub_array(array))

求数组连续最大和，以及最大子数组的位置

def max_sub_array_location(array):
    """
    求数组连续最大和
    :param array: 数组
    :return: 数组连续最大和，最大子数组的位置
    时间复杂度 O(N) 空间复杂度 O(1)
    """
    n = len(array)
    n_sum = 0
    sub_max = -2 ** 31
    start_location = 0
    end_location = 0

    i = 0
    while i < n:
        # 到第i个数的最大累加和
        if n_sum <= 0:
            n_sum = array[i]
            start_location = i
        else:
            n_sum = array[i] + n_sum
        # 累加和end中的最大值
        if n_sum > sub_max:
            sub_max = n_sum
            end_location = i
        i += 1
    return (sub_max, start_location, end_location)


if __name__ == "__main__":
    array = list(map(int, input().strip().split(" ")))
    print(max_sub_array_location(array))

数组旋转

def rotateArray(array):
    """
    逆时针旋转n*n矩阵45度
    """
    lens = len(array[0])
    # 打印二维数组的上半部分
    i = lens - 1
    while i > 0:
        row = 0
        col = i
        while col < lens:
            print(array[row][col], end=" ")
            row += 1
            col += 1
        print("")
        i -= 1
    # 打印二维数组下半部分（包括对角线）
    i = 0
    while i < lens:
        row = i
        col = 0
        while row < lens:
            print(array[row][col], end=" ")
            row += 1
            col += 1
        print("")
        i += 1


if __name__ == "__main__":
    array_row = int(input())
    array = []
    for i in range(array_row):
        array.append(list(map(int, input().strip().split(" "))))
    rotateArray(array)

判断区间[a, b]与[c, d]是否相交，如果相交那么相交部分的长度L是多少？

如果区间相交，那么区间最大的开始端一定小于最小的结束端，且相交的长度就是最小结束端减去最大开始端的值。

$$L = min(b, d) - max(a, c)$$

找出数组中和为S的两个数字

1. 首先对数组进行排序，时间复杂度为（N*log2N）。
2. 然后令i = 0，j = n-1，看arr[i] + arr[j] 是否等于Sum，如果是，则结束。如果小于Sum，则i = i + 1；如果大于Sum，则 j = j – 1。这样只需要在排好序的数组上遍历一次，就可以得到最后的结果，时间复杂度为O（N）。两步加起来总的时间复杂度O（N*log2N）

找出数组中和为S的三个数字：首先还是先对数组进行排序，然后遍历数组元素arr[i]，找到和为S-arr[i]的两个数即可。

def getSumNumFromSortedList(sorted_list, target):
    left = 0
    right = len(sorted_list) - 1
    while left <= right:
        temp_sum = sorted_list[left] + sorted_list[right]
        if temp_sum == target:
            return [left, right]
        elif temp_sum < target:
            left += 1
        else:
            right -= 1
    raise ValueError("Non-existent!")

if __name__ == "__main__":
    nums = list(map(int, input().strip().split()))
    target = int(input())
    print(getSumNumFromSortedList(nums, target))

注意与“两数字和”区分：

"""
LeetCode 第 1 号问题：两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
时间复杂度 O(n) 空间复杂度  O(n)
"""

def twosum(num_list, target):
    record = dict()
    for i, item in enumerate(num_list):
        complement = target - item
        if complement in record:
            return [record[complement], i]
        record[item] = i

if __name__ == "__main__":
    nums = list(map(int, input().strip().split()))
    target = int(input())
    print(twosum(nums, target))

def find_two_odd_numbers_of_elements(array):
    """
    找出数组中两个出现次数为奇数个数的数(这两个数不相等)
    :param array: 整数数组
    :return: (num1, num2) 数组中两个出现次数为奇数个数的元素
    """
    # (item0 ^ item0)...a^b...(itemN^itemN) = a^b
    a_xor_b = 0
    for item in array:
        a_xor_b ^= item
    i = a_xor_b
    # 找到a和b二进制表示首次不相同的位置（从右往左），该位置的异或值为1
    # 异或值中一定存在1的证明：a!=b -> a^b!=0 -> 1 in bin(a_xor_b)
    position = 0
    while i & 1 == 0:
        position += 1
        i = i >> 1
    # 选取position位置都为1的元素来异或求值，这样a和b只会取到其中一个，
    # 其它数只会取到偶数个，而偶数个数的相同数异或值为0，0与x异或为x,
    # 故最终的异或值为 a 或 b
    a_item = 0
    for item in array:
        item_positon = item >> position
        if (item_positon & 1) == 1:
            a_item ^= item
    # b = a ^ (a ^ b)
    b_item = a_item ^ a_xor_b
    return (a_item, b_item)

if __name__ == "__main__":
    array = list(map(int, input().strip().split()))
    print(find_two_odd_numbers_of_elements(array))

寻找最多的覆盖点

def max_cover(a, L):
    """
    寻找最多的覆盖点
    :param a: 长度为n的数组，表示坐标轴上从左到右的点a[0],a[1],...,a[n-1]
    :param L: 木棒长度L
    :return: 木棒最多能覆盖的坐标轴点的个数
    """
    count = 2
    max_count = 1
    start = 0
    n = len(a)
    i = 0
    j = 1
    while i < n and j < n:
        while (j < n) and (a[j] - a[i] <= L):
            j += 1
            count += 1
        j -= 1
        count -= 1
        if count > max_count:
            start = i
            max_count = count
        i += 1
        j += 1
    # 输出覆盖的节点
    # i = start
    # while i < start + max_count:
    #     print(a[i])
    #     i += 1
    return max_count


if __name__ == '__main__':
    a = list(map(int, input().split()))  # 7 8 10 11 12 13 15 16 17 19 25
    L = int(input())  # 8
    print(max_cover(a, L))  # 7

字符串匹配之KMP算法

字符串匹配的KMP算法

图解kmp算法-通俗易懂kmp算法

def kmp(S, P):
    """
    knut-Morris-Pratt String Matching Algorithms
    :param S: Source string
    :param P: Pattern string
    :return: Matching position
    时间复杂度 O(len(S)+len(P))
    """
    def _next(P, P_length):
        k = 0
        next_list = [0 for _ in range(P_length)]
        next_list[0] = k
        for i in range(1, P_length):
            while k > 0 and P[k] != P[i]:
                k = next_list[k - 1]
            if P[k] == P[i]:
                k += 1
            next_list[i] = k
        return next_list

    S_len = len(S)
    P_len = len(P)
    k = 0
    next_list = _next(P, P_len)
    for i in range(S_len):
        while k > 0 and P[k] != S[i]:
            k = next_list[k - 1]
        if P[k] == S[i]:
            k += 1
        if k == P_len:
            return i - k + 1
    return - 1

if __name__ == "__main__":
    S = "dabxabxababxabwabxad"
    P = "abxabwabxad"
    location = kmp(S, P)
    print(location)

编辑距离算法

动态规划-用编辑距离解释

def editorial_distance(strA, strB):
	strA_length = len(strA)
	strB_length = len(strB)
	distance_array = [[0] * (strB_length+1) for _ in range(strA_length+1)]

	for i in range(strA_length+1):
		distance_array[i][0] = i

	for j in range(strB_length+1):
		distance_array[0][j] = j

	for i in range(1, strA_length+1):
		for j in range(1, strB_length+1):
			if strA[i-1] == strB[j-1]:
				distance_array[i][j] = distance_array[i-1][j-1]
			else: # 在插入、删除、替换操作中保留最优解
				distance_array[i][j] = min([distance_array[i-1][j]+1,  distance_array[i][j-1]+1, distance_array[i-1][j-1]+1])

	return distance_array[-1][-1]


if __name__=='__main__':
	strA = "mouuse"
	strB = "mouse"
	print(editorial_distance(strA, strB))

Leetcode 583. 两个字符串的删除操作

为了求得最少删除次数，我们可以求出串 s1 和串 s2 最长公共子序列，我们记为 lcs。如果我们能求得 lcs 的值，我们可以轻易地求出答案，为 m + n - 2*lcs。这里 m 和 n 分别是给定字符串 s1s1 和 s2s2 的长度。

class Solution:
    """
    时间复杂度：O(m*n)。我们需要填充大小为m * n的数组dp。m和n分别是s1和s2字符串的长度。
    空间复杂度：O(m*n)。使用了大小为m∗n的dp数组。
    """
    def minDistance(self, word1: str, word2: str) -> int:
        word1 = "#" + word1
        word2 = "#" + word2
        dp_matrix = [[0] * len(word2) for i in range(len(word1))]
        for i in range(1, len(word1)):
            for j in range(1, len(word2)):
                if word1[i] == word2[j]:
                    dp_matrix[i][j] = dp_matrix[i - 1][j - 1] + 1
                else:
                    dp_matrix[i][j] = max(dp_matrix[i - 1][j], dp_matrix[i][j - 1])
        longest_common_sequence_length = dp_matrix[-1][-1]
        return len(word1) + len(word2) - 2 * longest_common_sequence_length - 2

最长公共子序列

• 动态规划解最长公共子序列(LCS)(附详细填表过程)
• 算法导论——-最长公共子序列LCS（动态规划）

def get_longest_common_sequence_path(path_matrix, X_list):
    """
    :param path_matrix: 动态规划矩阵
    :param X_list: 其中一个字符串
    :return: 最长公共子序列路径
    """
    result_list = list()
    i = len(path_matrix) - 1
    j = len(path_matrix[0]) - 1
    while path_matrix[i][j] != "0":
        if path_matrix[i][j] == "left_upper":
            result_list.append(X_list[i])
            i -= 1
            j -= 1
        elif path_matrix[i][j] == "upper":
            i -= 1
        else:
            j -= 1

    result_list.reverse()
    return result_list

def longest_common_sequence(X_list, Y_list):
    X_list.insert(0, "")
    Y_list.insert(0, "")
    dp_matrix = [[0] * len(Y_list) for i in range(len(X_list))]
    path_matrix = [["0"] * len(Y_list) for i in range(len(X_list))]
    for i in range(1, len(X_list)):
        for j in range(1, len(Y_list)):
            if X_list[i] == Y_list[j]:
                dp_matrix[i][j] = dp_matrix[i - 1][j - 1] + 1
                path_matrix[i][j] = "left_upper"
            elif dp_matrix[i - 1][j] >= dp_matrix[i][j - 1]:
                dp_matrix[i][j] = dp_matrix[i - 1][j]
                path_matrix[i][j] = "upper"
            else:
                dp_matrix[i][j] = dp_matrix[i][j - 1]
                path_matrix[i][j] = "left"
    longest_common_sequence_length = dp_matrix[-1][-1]
    longest_common_sequence_path = get_longest_common_sequence_path(path_matrix, X_list)
    return longest_common_sequence_path

if __name__=='__main__':
    X_list = list("ACCGGTCGAGTGCGCGGAAGCCGGCCGAA")
    Y_list = list("GTCGTTCGGAATGCCGTTGCTCTGTAAA")
    longest_common_sequence_path = longest_common_sequence(X_list,Y_list)
    # "G,T,C,G,T,C,G,G,A,A,G,C,C,G,G,C,C,G,A,A"
    print(",".join(longest_common_sequence_path))

Leetcode 718. 最长重复子数组

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        A.insert(0, "")
        B.insert(0, "")
        A_len = len(A)
        B_len = len(B)
        dp_matrix = [[0] * (B_len) for _ in range(A_len)]
        for i in range(1, A_len):
            for j in range(1, B_len):
                if A[i] == B[j]:
                    dp_matrix[i][j] = dp_matrix[i-1][j-1]+1

        return max(max(row) for row in dp_matrix)

最长公共连续子字符串

def longest_common_continuous_substring(A_str, B_str):
    """
    最长公共连续子字符串
    :param A_str: 字符串A，长度为m
    :param B_str: 字符串B，长度为n
    :return: 字符串A和字符串B公共的连续最长的字符串列表
    时间复杂度：O(m*n) 空间复杂度：O(m*n)
    """
    A_str = "#" + A_str
    B_str = "#" + B_str
    A_str_len = len(A_str)
    B_str_len = len(B_str)
    dp_matrix = [[0] * (B_str_len) for _ in range(A_str_len)]
    for i in range(1, A_str_len):
        for j in range(1, B_str_len):
            if A_str[i] == B_str[j]:
                dp_matrix[i][j] = dp_matrix[i-1][j-1]+1

    substring_max_length_list = [max(row) for row in dp_matrix]
    substring_max_length = max(substring_max_length_list)
    result = []
    for idx, num in enumerate(substring_max_length_list):
        if num == substring_max_length:
            result.append(A_str[idx - num + 1:idx + 1])
    return result

if __name__=='__main__':
    A_str = "ABCBDEFBWD"
    B_str = "BCBWD"
    # ['BCB', 'BWD']
    print(longest_common_continuous_substring(A_str, B_str))

Trie树（字典树，单词查找树）

• Trie树实现 https://github.com/hankcs/pyhanlp/blob/master/tests/book/ch02/trie.py
• Trie树理论知识 数据结构与算法—Trie树

class Node(object):
    def __init__(self, value) -> None:
        self._children = {}
        self._value = value

    def _add_child(self, char, value, overwrite=False):
        child = self._children.get(char)
        if child is None:
            child = Node(value)
            self._children[char] = child
        elif overwrite:
            child._value = value
        return child


class Trie(Node):
    def __init__(self) -> None:
        super().__init__(None)

    def __contains__(self, key):
        return self[key] is not None

    def __getitem__(self, key):
        state = self
        for char in key:
            state = state._children.get(char)
            if state is None:
                return None
        return state._value

    def __setitem__(self, key, value):
        state = self
        for i, char in enumerate(key):
            if i < len(key) - 1:
                state = state._add_child(char, None, False)
            else:
                state = state._add_child(char, value, True)


if __name__ == '__main__':
    trie = Trie()
    # 增
    trie['自然'] = 'nature'
    trie['自然人'] = 'human'
    trie['自然语言'] = 'language'
    trie['自语'] = 'talk	to oneself'
    trie['入门'] = 'introduction'
    assert '自然' in trie
    # 删
    trie['自然'] = None
    assert '自然' not in trie
    # 改
    trie['自然语言'] = 'human language'
    assert trie['自然语言'] == 'human language'
    # 查
    assert trie['入门'] == 'introduction'

并查集

并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。

"""
输入：
第一行表示表示用户互动矩阵的行数（用户个数）
矩阵（i, j）的每一个值表示用户i与j互动的次数，当次数大于3时互为豆油瓶。
输出：
矩阵对应的豆油瓶个数。

例子1：
输入：
3
0 4 0
4 0 0
0 0 0
输出：（用户1和2互动次数超过3次，互为豆油瓶，用户3没有互动，自成一个豆油瓶）
2
"""

class Solution:
    """
    并查集解法
    """
    def findDouYouNum(self, array):
        if not array:
            return 0
        n = len(array[0])
        self.count = n
        self.father_list = [i for i in range(n)]
        self.size_list = [1 for _ in range(n)]

        for i in range(0, n - 1):
            for j in range(i+1, n):
                if array[i][j] >= 3:
                    self.union(i, j)
        return self.count

    def find(self, i):
        while(i != self.father_list[i]):
            i = self.father_list[i]
        return i

    def union(self, i, j):
        p = self.find(i)
        q = self.find(j)
        if p == q:
            return
        if self.size_list[p] < self.size_list[q]:
            self.father_list[p] = q
            self.size_list[q] += self.size_list[p]
        else:
            self.father_list[q] = p
            self.size_list[p] += self.size_list[q]
        self.count -= 1


if __name__=="__main__":
    n = int(input())
    array = [[] for _ in range(n)]
    for i in range(n):
        array[i] = list(map(int, input().strip().split(" ")))
    s = Solution()
    print(s.findDouYouNum(array))

2048小游戏

"""
2048合并规则：
1. 相邻会碰撞的两个相同数字合并且只会触发一次合并；
2. 优先合并移动方向顶部的位置，比如 [2, 2 ,2 , 2] 行向右合并为 [0, 0, 4, 4]
输入：
第1行是2048块的滑动方向键。1：上、2：下、3：左、4：右。
接下来4 x 4的数字矩阵用空格分割，0表示该位置没有数字。
输出：
用户按下房间键红后的矩阵值。

示例
输入：
1
0 0 0 2
0 0 0 2
0 0 4 8
0 0 4 8
输出：
0 0 8 4
0 0 0 16
0 0 0 0
0 0 0 0
"""

def MoveUp():
    for j in range(0, 4):
        for i in range(0, 3):
            if Num[i][j] != 0:
                continue
            for k in range(i+1, 4):
                if Num[k][j] != 0:
                    Num[i][j], Num[k][j] = Num[k][j], Num[i][j]
                    break

def MoveDown():
    for j in range(0, 4):
        for i in range(3, 0, -1):
            if Num[i][j] != 0:
                continue
            for k in range(i-1, -1, -1):
                if Num[k][j] != 0:
                    Num[i][j], Num[k][j] = Num[k][j], Num[i][j]
                    break

def MoveLeft():
    for i in range(0, 4):
        for j in range(0, 3):
            if Num[i][j] != 0:
                continue
            for k in range(j+1, 4):
                if Num[i][k] != 0:
                    Num[i][j], Num[i][k] = Num[i][k], Num[i][j]
                    break

def MoveRight():
    for i in range(0, 4):
        for j in range(3, 0, -1):
            if Num[i][j] != 0:
                continue
            for k in range(j-1, -1, -1):
                if Num[i][k] != 0:
                    Num[i][j], Num[i][k] = Num[i][k], Num[i][j]
                    break

def move(direction):
    if direction == 1:
        MoveUp()
        for i in range(0, 3):
            for j in range(0, 4):
                if Num[i][j] == Num[i + 1][j]:
                    Num[i][j] <<= 1
                    Num[i + 1][j] = 0
        MoveUp()
    elif direction == 2:
        MoveDown()
        for i in range(3, 0, -1):
            for j in range(0, 4):
                if Num[i][j] == Num[i - 1][j]:
                    Num[i][j] <<= 1
                    Num[i - 1][j] = 0
        MoveDown()
    elif direction == 3:
        MoveRight()
        for i in range(0, 4):
            for j in range(3, 0, -1):
                if Num[i][j] == Num[i][j - 1]:
                    Num[i][j] <<= 1
                    Num[i][j - 1] = 0
        MoveRight()
    else:
        MoveLeft()
        for i in range(0, 4):
            for j in range(0, 3):
                if Num[i][j] == Num[i][j - 1]:
                    Num[i][j] <<= 1
                    Num[i][j - 1] = 0
        MoveLeft()

if __name__=="__main__":
    direction = int(input())
    Num = [[] for i in range(4)]
    for i in range(4):
        Num[i] = list(map(int, input().strip().split()))
    move(direction)
    print(Num)

单调栈

def largestRectangleArea(heights):
    """
    Leetcode 84：柱状图中最大的矩形
    :type heights: List[int]
    :rtype: int
    """
    stack = list()
    res, i = 0, 0
    while i < len(heights):
        if not stack or heights[i] >= heights[stack[-1]]:
            stack.append(i)
            i += 1
        else:
            k = stack.pop()
            current_s = heights[k] * ((i - stack[-1] - 1) if stack else i)
            res = max(res, current_s)

    while stack:
        k = stack.pop()
        current_s = heights[k] * ((i - stack[-1] - 1) if stack else i)
        res = max(res, current_s)
    return res


if __name__ == '__main__':
    heights = list(map(int, input().split(" ")))
    print(largestRectangleArea(heights))

迷宫

class Maze:
    """
    给定N*M的迷宫，需要走左上角走到右下角，只能向右或者向下移动。
    在迷宫中0表示没有路，1表示有路。是否存在一条可行的路径？
    例子：
    迷宫行数（列数）4
    迷宫
    1 0 0 0
    1 1 0 1
    0 1 0 0
    1 1 1 1
    解法
    1 0 0 0
    1 1 0 0
    0 1 0 0
    0 1 1 1
    """
    def __init__(self, maze):
        self.maze = maze # 迷宫
        self.N = len(maze)
        self.sol = [[0] * self.N for _ in range(self.N)] # 存储结果
    # 打印从起点到终点的路线
    def print_solution_matrix(self):
        for i in range(self.N):
            print(" ".join(map(str, self.sol[i])))
    # 判断x和y是否是一个合理的单元
    def is_safe(self, x, y):
        return x >= 0 and x < self.N and y >= 0 and y < self.N \
               and self.maze[x][y] == 1
    # 使用回溯的方法找到一条从左上角到右下角的路径
    def get_path(self, x, y):
        # 达到目的地
        if x == self.N - 1 and y == self.N - 1:
            self.sol[x][y] = 1
            return True
        # 判断maze[x][y]是否是一个可走的单元
        if self.is_safe(x, y):
            # 标记当前单元为1，表示可走
            self.sol[x][y] = 1
            # 向右走一步
            if self.get_path(x + 1, y):
                return True
            # 向下走一步
            if self.get_path(x, y + 1):
                return True
            # 标记当前单元为0，表示这条路不可行，然后回溯
            self.sol[x][y] = 0
            return False
        return False


if __name__ == '__main__':
    n = int(input())
    maze = list()
    for _ in range(n):
        maze.append(list(map(int, input().split())))

    rat = Maze(maze)
    if rat.get_path(0, 0):
        rat.print_solution_matrix()
    else:
        print("不存在可达路径")

杂项

def schedule(R, O, M):
    """
    给定一台有M个存储空间的机器，有n个请求需要在这台机器上运行，
    第i个请求计算需要占用R[i]的空间，计算结果需要占O[i]个空间（O[i]<R[i]）。
    判断这n个请求是否能全部完成？若能，给出这个n个请求的按排顺序。
    """
    # 按照 R[i] - O[i] 由大到小进行排序
    # 可以使用归纳法证明，按照这个顺序执行的成功可能性最大。
    R_O = list(zip(R, O))
    R_O.sort(key=lambda item: -(item[0] - item[1]))
    R = [item[0] for item in R_O]
    O = [item[1] for item in R_O]
    left = M  # 剩余可用的空间数
    lens = len(R)
    i = 0
    while i < lens:
        if left < R[i]:  # 剩余的空间无法继续处理第i个请求
            return False
        else:  # 剩余的空间能继续处理第i个请求，处理完后将占用O[i]个空间
            left -= O[i]
        i += 1
    print("按照如下请求序列可以完成：")
    print(R_O)
    return True


if __name__ == '__main__':
    n = int(input())  # 8
    M = int(input())  # 50
    R = list(map(int, input().split()))  # 10 15 23 20 6 9 7 16
    O = list(map(int, input().split()))  # 2 7 8 4 5 8 6 8
    print(schedule(R, O, M))  # True

leetcode873. 最长的斐波那契子序列的长度

• https://coordinate.wang/index.php/archives/2098/
• https://blog.csdn.net/weixin_37373020/article/details/81559842

背包问题

背包问题九讲 催添翼

def zero_one_bag_problem(bag_v, n_weight, n_vol):
    """
    零一背包问题
    :param bag_v: 背包体积
    :param n_weight: 物品价值
    :param n_vol: 物品体积
    :return: 包能装的物品最大总价值
    时间复杂度 O(NV)，空间复杂度O(NV)
    """
    # 填充没有价值的物品
    n_weight.insert(0, 0)
    n_vol.insert(0, 0)
    array = [[0] * (bag_v + 1) for _ in range(len(n_weight))]
    # 遍历物品N
    for i in range(1, len(n_weight)):
        # 遍历不同被包容量V
        for j in range(1, bag_v + 1):
            # 如果当前背包容量不能够装下第i件物品
            if j < n_vol[i]:
                array[i][j] = array[i - 1][j]
            else:
                array[i][j] = max(array[i - 1][j], array[i - 1][j - n_vol[i]] + n_weight[i])
    # 打印运算过程
    # for i in range(len(n_weight)):
    #     print(array[i])
    return array[-1][-1]


if __name__ == '__main__':
    bag_v = int(input())  # 12
    n_vol = list(map(int, input().strip().split(" ")))  # 1 3 2 6 2
    n_weight = list(map(int, input().strip().split(" ")))  # 2 5 3 10 4
    print(zero_one_bag_problem(bag_v, n_weight, n_vol))  # 21

def zero_one_bag_problem(bag_v, n_weight, n_vol):
    """
    零一背包问题
    :param bag_v: 背包体积
    :param n_weight: 物品价值
    :param n_vol: 物品体积
    :return: 包能装的物品最大总价值
    时间复杂度 O(NV)，空间复杂度O(V)
    """

    array = [0] * (bag_v + 1) # 填充0，方便表示
    # 依次遍历每个物品N
    for i in range(len(n_vol)):
        # 从大到小遍历遍历背包容量V（当背包容量小于物品容量时直接跳过）
        for j in range(bag_v, n_vol[i] - 1, -1):
                array[j] = max(array[j], array[j-n_vol[i]] + n_weight[i])
    return array[-1]


if __name__ == '__main__':
    bag_v = int(input())  # 12
    n_vol = list(map(int, input().strip().split(" ")))  # 1 3 2 6 2
    n_weight = list(map(int, input().strip().split(" ")))  # 2 5 3 10 4
    print(zero_one_bag_problem(bag_v, n_weight, n_vol))  # 21

def full_bag_problem(bag_v, n_weight, n_vol):
    """
    完全背包问题
    :param bag_v: 背包体积
    :param n_weight: 物品价值
    :param n_vol: 物品体积
    :return: 包能装的物品最大总价值
    时间复杂度 O(NV)，空间复杂度O(V)
    """

    array = [0] * (bag_v + 1) # 填充0，方便表示
    # 依次遍历每个物品N
    for i in range(len(n_vol)):
        # 从大到小遍历遍历背包容量V（当背包容量小于物品容量时直接跳过）
        for j in range(n_vol[i], bag_v + 1):
                array[j] = max(array[j], array[j-n_vol[i]] + n_weight[i])
    return array[-1]


if __name__ == '__main__':
    bag_v = int(input())  # 15
    n_vol = list(map(int, input().strip().split(" ")))  # 5 4 7 2 6
    n_weight = list(map(int, input().strip().split(" ")))  # 12 3 10 3 6
    print(complete_bag_problem(bag_v, n_weight, n_vol))  # 36

Leetcode 416：分割等和子集

from typing import List


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        size = len(nums)

        # 特判，如果整个数组的和都不是偶数，就无法平分
        s = sum(nums)
        if s & 1 == 1:
            return False

        # 二维 dp 问题：背包的容量
        target = s // 2
        dp = [[False for _ in range(target + 1)] for _ in range(size)]

        # 先写第 1 行：看看第 1 个数是不是能够刚好填满容量为 target
        for i in range(target + 1):
            dp[0][i] = False if nums[0] != i else True
        # i 表示物品索引
        for i in range(1, size):
            # j 表示容量
            for j in range(target + 1):
                if j >= nums[i]:
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
                else:
                    dp[i][j] = dp[i - 1][j]

        return dp[-1][-1]


if __name__ == '__main__':
    nums = [1, 5, 11, 5]
    print(Solution().canPartition(nums))

二分查找

当数组“有序”时，考虑用二分查找。

def binary_search_recursion(lst, val, start, end):
    #递归二分查找
    if start > end:
        return None
    mid = (start + end) // 2
    if lst[mid] < val:
        return binary_search_recursion(lst, val, mid + 1, end)
    if lst[mid] > val:
        return binary_search_recursion(lst, val, start, mid - 1)
    return mid


def binary_search_loop(lst, val):
    #循环二分查找
    start, end = 0, len(lst) - 1
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] < val:
            start = mid + 1
        elif lst[mid] > val:
            end = mid - 1
        else:
            return mid
    return None

二分插入和查询算法（Python源码）

结论：二分查找最大比较次数为$\lfloor log_2(len(array)) \rfloor + 1$

import bisect

"""Bisection algorithms."""

def insort_right(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the right of the rightmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid # Limit high-end
        else: lo = mid+1
    a.insert(lo, x)

insort = insort_right   # backward compatibility

def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid # Limit high-end
        else: lo = mid+1
    return lo

bisect = bisect_right   # backward compatibility

def insort_left(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the left of the leftmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1 # Limit the low end
        else: hi = mid
    a.insert(lo, x)


def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1 # Limit the low end
        else: hi = mid
    return lo

从 递归 到 动态规划

---

数据结构

双向列表

deque是为了高效实现插入和删除操作的双向列表，适合用于队列和栈

from collections import deque

'append', 'appendleft', 'clear', 'copy', 'count', 'extend', 'extendleft',
 'index', 'insert', 'maxlen', 'pop', 'popleft', 'remove', 'reverse', 'rotate'

计数器（Python源码）

当需要对 list 中的大量数据进行计数时，可以直接使用 Counter ，而不用新建字典来计数。

from collections import Counter

class Counter(dict):
    '''Dict subclass for counting hashable items.  Sometimes called a bag
    or multiset.  Elements are stored as dictionary keys and their counts
    are stored as dictionary values.

    >>> c = Counter('abcdeabcdabcaba')  # count elements from a string

    >>> c.most_common(3)                # three most common elements
    [('a', 5), ('b', 4), ('c', 3)]
    >>> sorted(c)                       # list all unique elements
    ['a', 'b', 'c', 'd', 'e']
    >>> ''.join(sorted(c.elements()))   # list elements with repetitions
    'aaaaabbbbcccdde'
    >>> sum(c.values())                 # total of all counts
    15

    >>> c['a']                          # count of letter 'a'
    5
    >>> for elem in 'shazam':           # update counts from an iterable
    ...     c[elem] += 1                # by adding 1 to each element's count
    >>> c['a']                          # now there are seven 'a'
    7
    >>> del c['b']                      # remove all 'b'
    >>> c['b']                          # now there are zero 'b'
    0

    >>> d = Counter('simsalabim')       # make another counter
    >>> c.update(d)                     # add in the second counter
    >>> c['a']                          # now there are nine 'a'
    9

    >>> c.clear()                       # empty the counter
    >>> c
    Counter()

    Note:  If a count is set to zero or reduced to zero, it will remain
    in the counter until the entry is deleted or the counter is cleared:

    >>> c = Counter('aaabbc')
    >>> c['b'] -= 2                     # reduce the count of 'b' by two
    >>> c.most_common()                 # 'b' is still in, but its count is zero
    [('a', 3), ('c', 1), ('b', 0)]

    '''

链表与数组相互转换

class Linked_list_node:
    def __init__(self, x):
        self.val = x
        self.next = None


def linked_list_to_array(head):
    array = []
    while head:
        array.append(head.val)
        head = head.next
    return array


def array_to_linked_list(array):
    ans = Linked_list_node(0)
    t = ans
    for item in array:
        t.next = Linked_list_node(item)
        t = t.next
    return ans.next


def print_linked_list(head):
    while head:
        print(head.val, end=" ")
        head = head.next
    print("")

if __name__=='__main__':
    array = [1, 3, 5, 7, 9]
    print("array: ", array)

    head = array_to_linked_list(array)
    print("print_linked_list: ")
    print_linked_list(head)

    array2 = linked_list_to_array(head)
    print("array2: ", array2)

Leetcode 206:反转链表

Leetcode 206:反转链表（最详细解决方案！！！）

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def reverseList_1(head):
    pre = None
    cur = head
    while cur != None:
        lat = cur.next
        cur.next = pre
        pre = cur
        cur = lat
    return pre

def reverseList_2(head):
    if not head or not head.next: # 如果输入结点是空，或只有一个结点，返回即可
        return head
    else:
        newHead = reverseList_2(head.next) # 将下一个结点之后的部分逆序
        head.next.next = head  # 反转当前结点
        head.next = None       # 设置当前结点的下一个结点为None
    return newHead

def reverseList_3(head):
    if not head or not head.next:  # 如果输入结点是空，或只有一个结点，返回即可
        return head
    temp = ListNode(0)
    current_p = head
    while current_p:
        c = current_p.next
        current_p.next = temp.next
        temp.next = current_p
        current_p = c
    return temp.next