Python进阶教程：算法与数据结构入门

1
# 列表：有序、可重复
2
fruits = ["苹果", "香蕉", "橙子"]
3
fruits.append("葡萄")
4
print(fruits[0], len(fruits))
5

6
# 字典：键值对、查找 O(1)
7
scores = {"张三": 90, "李四": 85}
8
print(scores["张三"])
9
print(scores.get("王五", "不存在"))

1
# 栈：后进先出（LIFO），用列表实现
2
stack = []
3
stack.append(1)   # 入栈
4
stack.append(2)
5
stack.append(3)
6
print(stack.pop())  # 3 出栈
7
print(stack[-1])    # 2 查看栈顶
8
print(len(stack) == 0)  # 判断是否为空

1
from collections import deque
2

3
# 队列：先进先出（FIFO）
4
queue = deque(["a", "b", "c"])
5
queue.append("d")      # 入队
6
print(queue.popleft()) # a 出队
7
print(queue)           # deque(["b", "c", "d"])

1
def bubble_sort(arr):
2
    n = len(arr)
3
    for i in range(n - 1):
4
        for j in range(n - 1 - i):
5
            if arr[j] > arr[j + 1]:
6
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
7
    return arr
8

9
print(bubble_sort([5, 2, 8, 1, 9]))  # [1, 2, 5, 8, 9]

1
def quick_sort(arr):
2
    if len(arr) <= 1:
3
        return arr
4
    pivot = arr[len(arr) // 2]
5
    left = [x for x in arr if x < pivot]
6
    mid = [x for x in arr if x == pivot]
7
    right = [x for x in arr if x > pivot]
8
    return quick_sort(left) + mid + quick_sort(right)
9

10
print(quick_sort([5, 2, 8, 1, 9]))  # [1, 2, 5, 8, 9]

1
# 二分查找（要求有序，O(log n)）
2
def binary_search(arr, target):
3
    left, right = 0, len(arr) - 1
4
    while left <= right:
5
        mid = (left + right) // 2
6
        if arr[mid] == target:
7
            return mid
8
        elif arr[mid] < target:
9
            left = mid + 1
10
        else:
11
            right = mid - 1
12
    return -1
13

14
nums = [1, 3, 5, 7, 9, 11]
15
print(binary_search(nums, 7))  # 3
16
print(binary_search(nums, 8))  # -1

1
# 递归：函数调用自身
2
def factorial(n):
3
    if n <= 1:
4
        return 1
5
    return n * factorial(n - 1)
6

7
print(factorial(5))  # 120
8

9
# 斐波那契（带缓存避免重复计算）
10
from functools import lru_cache
11
@lru_cache(maxsize=None)
12
def fib(n):
13
    if n < 2:
14
        return n
15
    return fib(n - 1) + fib(n - 2)
16

17
print(fib(50))  # 12586269025

1
# 经典问题：爬楼梯（每次 1 或 2 阶）
2
def climb_stairs(n):
3
    if n <= 2:
4
        return n
5
    dp = [0] * (n + 1)
6
    dp[1], dp[2] = 1, 2
7
    for i in range(3, n + 1):
8
        dp[i] = dp[i - 1] + dp[i - 2]
9
    return dp[n]
10

11
print(climb_stairs(10))  # 89

1
from collections import OrderedDict
2

3
class LRUCache:
4
    """最近最少使用缓存"""
5
    def __init__(self, capacity):
6
        self.cache = OrderedDict()
7
        self.capacity = capacity
8

9
    def get(self, key):
10
        if key not in self.cache:
11
            return -1
12
        self.cache.move_to_end(key)  # 标记为最近使用
13
        return self.cache[key]
14

15
    def put(self, key, value):
16
        if key in self.cache:
17
            self.cache.move_to_end(key)
18
        self.cache[key] = value
19
        if len(self.cache) > self.capacity:
20
            self.cache.popitem(last=False)  # 淘汰最久未用
21

22
cache = LRUCache(2)
23
cache.put(1, "A")
24
cache.put(2, "B")
25
print(cache.get(1))   # A
26
cache.put(3, "C")    # 淘汰 key=2
27
print(cache.get(2))   # -1
28
print(cache.get(3))   # C