python-数据结构和算法

在 python 上实现的基本数据结构和算法

斐波那契

描述:
除了第一个和第二个数,之后的每一个数都是前两个数之和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
def fib(n):
    """
    迭代
    """
    count_, pre, next_ = 0, 0, 1
    while count_ < n:
        print(next_)
        pre, next_ = next_, pre + next_
        count_+=1

fib(8) # 1,1,2,3,5,8,13,21
##################################
def fib_recursive(n):
    """
    二叉递归

    递归此数就是数列对应的值,n > 2 时,n = 8,就是 21 次 ,产生大量重复计算,效率太低。
    """
    if n <= 2:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)
# 或者更加简洁的方式
fib_recursive = lambda n: 1 if n <= 2 else fib_recursive(n - 1) + fib_recursive(n - 2)

#  优化方案:缓存
def cache(func):
    cache = {}
    def wrapper(i):
        if i not in cache:
            cache[i] = func(i)
        return cache[i]
    return wrapper

@cache
def fib_recursive_cache(i):
    if i <= 2:
        return 1
    return fib_recursive_cache(i-1) + fib_recursive_cache(i-2)

fib_recursive(8) #  21
fib_recursive_cache(66) # 27777890035288
##################################
def fib_recursive(n):
    """
    一叉递归(类迭代方式的线性递归)
    """
    count_, pre, next_ = 0, 0, 1
    def fib_inner():
        nonlocal count_, pre , next_
        if count_ >= n:
            return 'done'
        print(next_)    
        pre, next_ = next_, pre + next_
        count_+=1
        fib_inner()
    fib_inner()

fib_recursive(8) #  1,1,2,3,5,8,13,21
##################################
def fib_g(n):
    """
    generator(生成器)
    """
    count_, pre, next_ = 0, 0, 1
    while count_ < n:
        yield next_
        pre, next_ = next_, pre + next_
        count_+=1
    return 'done'

g = fib_g(5)
print(next(g)) # 1
print(next(g))  # 1
print(next(g))  #  2
print(next(g))  # 3
print(next(g))  # 5
print(next(g))  # StopIteration  exception

# 迭代
for item in fib_g(5):
    print(item) # 1,1,2,3,5

参考:
斐波那契数列算法分析

排序算法

冒泡排序

原理: 两两对比,大数沉底。

思路: 外层循环 N-1 次排序,因为第 N-1 次时已经排好序了。
内层循环 N-1-i 次两数对比数。

N:元素个数
i:第几次排序操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def bubble_sort(lst):
    """
    冒泡排序
    :param lst:
    :return:
    """
    size = len(lst)
    for i in range(size):
        for j in range(size - i - 1):
            if lst[j] > lst[j + 1]:
                lst[j], lst[j + 1] = lst[j + 1], lst[j]

快排

原理:

  1. 从数组或者分区中任意挑一个元素作为基准数(base)。
  2. 基于 base 对剩余元素进行分区,大于基准数的放右边分区,否则放左边分区。
  3. 左右两个分区先左后右重复 1 和 2 步骤,直到左或者右分区只有一个数为止,此时这个数就是相对最小数,同时也是当前的基准数。

思路:递归,从最内层的那个递归结束时一层层收集基准数到新的列表里,最终得到排好序的元素列表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def quick_sort(lst):
    """
    快排
    :param lst:
    :return:
    """
    if not lst:
        return

    result = []

    def sort(items):
        left, right = [], []
        base = items[0]

        for i in range(1, len(items)):
            if items[i] > base:
                right.append(items[i])
            else:
                left.append(items[i])
        if left:
            if len(left) == 1:
                result.append(left[0])
            else:
                sort(left)
        result.append(base)
        if right:
            if len(right) == 1:
                result.append(right[0])
            else:
                sort(right)

    sort(lst)

    return result

参考:
数据结构与算法-排序篇-Python描述

链表相交节点

根据最短链表长度 L, 迭代 L 次 + 交/分状态找到所有的相交的节点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def node(l1, l2, result):
    if not l1 or not l2:
        return
    intersect = l1[0] == l2[0]
    for i in range(min(len(l1), len(l2))):
        if intersect and l1[i] != l2[i]:
            result.append(l1[i - 1])
            intersect = False
        elif not intersect and l1[i] == l2[i]:
            result.append(l1[i])
            intersect = True

二分法搜索算法

前提条件:有序列表

  1. 定义搜索区间范围。两个列表索引值,left 和 right,维护每次搜索的范围。
  2. 取区间中间数作为基准数(base),对比搜索的目标。
  3. 目标如果大于 base ,根据 base 更新搜索区间范围,重复 2 步骤直到 base = 搜索目标或者区间范围损坏表示目标不在列表里
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def binary_search(lst, target):
    """
    递归方式对有序整数列表进行二分法查找

    :param lst: 整数列表,必须是有序的
    :param target: 要查找的整数目标
    :return: 目标在列表中的索引位置
    """
    if not lst:
        return None
    # 维护二分查找区间
    index_left, index_mid, index_right = 0, 0, len(lst) - 1

    def search():
        nonlocal index_left, index_mid, index_right
        # 防止无限递归造成栈溢出(目标不在 lst 中)
        if index_right < index_left:
            return None

        index_mid = index_left + (index_right - index_left) // 2

        if target == lst[index_mid]:
            return index_mid
        if target > lst[index_mid]:
            index_left = index_mid + 1
        else:
            index_right = index_mid - 1
        return search()

    return search()


def binary_search_2(list, item):
    """
    迭代

    :param list:
    :param item:
    :return:
    """
    low = 0
    high = len(list) - 1
    while low <= high:
        mid = (high - low) // 2 + low
        guess = list[mid]
        if guess > item:
            high = mid - 1
        elif guess < item:
            low = mid + 1
        else:
            return mid
    return None