Python编程实践：装饰器与生成器

30、编写一个装饰器，用于检查传递给函数的值是否为正确的类型。

以下是实现该功能的代码：

import functools

def check_types(func):
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        for i, (arg, expected_type) in enumerate(zip(args, func.__annotations__.values())):
            if not isinstance(arg, expected_type):
                raise TypeError(f"Argument {i} of {func.__name__} is not of type {expected_type}")
        for k, v in kwargs.items():
            if k not in func.__annotations__:
                raise TypeError(f"{k} is not a valid keyword argument for {func.__name__}")
            if not isinstance(v, func.__annotations__[k]):
                raise TypeError(f"{k} is not of type {func.__annotations__[k]}")
        return func(*args, **kwargs)
    return wrapper

@check_types
def add(a: int, b: int) -> int:
    return a + b

add(1, 2)

注意，Python 3.5 及以上版本才支持类型提示。

31、编写一个生成斐波那契数列的生成器。

def fibonacci_sequence():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

32、编写一个生成器，用于生成给定列表的所有排列。

from itertools import permutations

def permutation_generator(lst):
    for perm in permutations(lst):
        yield perm

33、编写一个生成 2 的幂的生成器。

以下是生成 2 的幂的生成器代码：

def powers_of_two():
    i = 1
    while True:
        yield i
        i *= 2

pow_gen = powers_of_two()
print(next(pow_gen))  # 1
print(next(pow_gen))  # 2
print(next(pow_gen))  # 4
print(next(pow_gen))  # 8

34、使用 lambda 函数、map 和 filter 对列表中的所有偶数进行平方运算，并仅返回平方值大于 100 的结果。

可以使用以下代码实现：

data = [1, 2, 3, 4, 12, 14, 16]
result = list(filter(lambda x: x > 100, map(lambda x: x**2, filter(lambda x: x % 2 == 0, data))))
print(result)

代码解释：首先使用

filter

函数筛选出列表中的偶数，然后使用

map

函数对这些偶数进行平方运算，最后使用

filter

函数筛选出平方值大于 100 的结果。

35、使用 lambda 函数和 reduce 函数来计算一个列表的列表中所有元素的乘积。

以下是实现该功能的 Python 代码示例：

from functools import reduce

list_of_lists = [[1, 2], [3, 4], [5, 6]]
flattened_list = [element for sublist in list_of_lists for element in sublist]
product = reduce(lambda x, y: x * y, flattened_list)
print(product)

上述代码首先将列表的列表展平为一个一维列表，然后使用

reduce

函数和

lambda

函数计算所有元素的乘积。

36、使用 lambda 函数、map 和 filter 从字符串列表中仅返回长度超过 4 个字母的单词。

可以使用如下代码实现：

words = ['apple', 'cat', 'banana', 'dog']
result = list(filter(lambda x: len(x) > 4, words))
print(result)

该代码首先定义了一个字符串列表，然后使用

filter

函数结合

lambda

函数筛选出长度超过 4 的单词，最后将结果转换为列表并打印。

37、为一个表示二维空间中点的类创建一个单元测试，该类提供计算到原点的距离以及到另一个点的斜率的方法。

以下是一个示例代码，用于创建一个表示二维空间中点的类，并为其提供计算到原点的距离以及到另一个点的斜率的方法，同时创建单元测试来验证这些方法：

import unittest
import math

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def distance_from_origin(self):
        return math.sqrt(self.x ** 2 + self.y ** 2)

    def slope_to_another_point(self, other):
        if other.x - self.x == 0:
            return float('inf')
        return (other.y - self.y) / (other.x - self.x)


class PointTest(unittest.TestCase):
    def test_distance_from_origin(self):
        point = Point(3, 4)
        self.assertEqual(point.distance_from_origin(), 5)

    def test_slope_to_another_point(self):
        point1 = Point(1, 1)
        point2 = Point(3, 3)
        self.assertEqual(point1.slope_to_another_point(point2), 1)

if __name__ == '__main__':
    unittest.main()

在上述代码中，定义了

Point

类，包含

distance_from_origin

和

slope_to_another_point

方法。同时，创建了

PointTest

测试类，继承自

unittest.TestCase

，并定义了两个测试方法来分别测试这两个功能。

38、为一个通过将消息中的字母按给定位置数移位来执行简单加密的函数创建一个单元测试。

以下是一个示例代码，用于为该加密函数创建单元测试：

import unittest

# 简单加密函数
def simple_encrypt(message, shift):
    encrypted = ''
    for char in message:
        if char.isalpha():
            start = ord('A') if char.isupper() else ord('a')
            new_char = chr((ord(char) - start + shift) % 26 + start)
            encrypted += new_char
        else:
            encrypted += char
    return encrypted


class EncryptionTest(unittest.TestCase):
    def test_encryption(self):
        message = 'abc'
        shift = 1
        encrypted = simple_encrypt(message, shift)
        # 这里可以根据预期的加密结果进行断言
        self.assertEqual(len(encrypted), len(message))


if __name__ == '__main__':
    unittest.main()

39、实现一个自定义的栈类，该类能够在常数时间内跟踪栈中的最小元素。

以下是Python实现的代码：

class Stack:
    def __init__(self):
        self.items = []
        self.mins = []
    def push(self, item):
        self.items.append(item)
        if not self.mins or item <= self.mins[-1]:
            self.mins.append(item)
    def pop(self):
        if self.items:
            if self.items[-1] == self.mins[-1]:
                self.mins.pop()
            return self.items.pop()
    def min(self):
        if self.mins:
            return self.mins[-1]
        return None

你可以使用以下方式测试这个类：

s = Stack()
s.push(5)
s.push(7)
s.push(3)
s.push(1)
print(s.min()) # 输出: 1
s.pop()
print(s.min()) # 输出: 3

40、实现一个自定义队列类，该类支持最大容量，并在队列满时自动丢弃最旧的元素。

以下是实现该功能的 Python 代码：

class Queue:
    def __init__(self, size):
        self.size = size
        self.items = []

    def enqueue(self, item):
        if len(self.items) == self.size:
            self.items.pop(0)
        self.items.append(item)

    def dequeue(self):
        if self.items:
            return self.items.pop(0)
        return None

你可以使用以下方式测试这个队列类：

q = Queue(3)
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())  # 输出: 1
q.enqueue(4)
print(q.dequeue())  # 输出: 2

41、实现一个自定义的链表类，该类具有一个用于反转元素顺序的函数。

以下是实现代码：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    def reverse(self):
        prev = None
        curr = self.head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        self.head = prev

    def print_list(self):
        curr = self.head
        while curr:
            print(curr.data)
            curr = curr.next

llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.append(4)
print("Original list:")
llist.print_list()
llist.reverse()
print("Reversed list:")
llist.print_list()

42、实现一个二叉搜索树类，该类提供插入、删除和搜索元素的方法。

以下是实现代码：

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, data):
        new_node = Node(data)
        if self.root is None:
            self.root = new_node
            return
        curr = self.root
        while True:
            if data < curr.data:
                if curr.left is None:
                    curr.left = new_node
                    break
                else:
                    curr = curr.left
            elif data > curr.data:
                if curr.right is None:
                    curr.right = new_node
                    break
                else:
                    curr = curr.right
            else:
                break

    def search(self, data):
        curr = self.root
        while curr:
            if data < curr.data:
                curr = curr.left
            elif data > curr.data:
                curr = curr.right
            else:
                return curr
        return None

    def delete(self, data):
        if self.root is None:
            return
        parent = None
        curr = self.root
        while curr and curr.data != data:
            parent = curr
            if data < curr.data:
                curr = curr.left
            else:
                curr = curr.right
        if curr is None:
            return

43、实现一个支持向字典树中插入、搜索和删除单词的字典树类。

以下是实现支持插入、搜索和删除单词的字典树类的代码：

class Trie:
    def __init__(self):
        self.root = {}
        self.end_symbol = '*'

    def insert(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                current[letter] = {}
            current = current[letter]
        current[self.end_symbol] = True

    def search(self, word):
        current = self.root
        for letter in word:
            if letter not in current:
                return False
            current = current[letter]
        if self.end_symbol in current:
            return True
        return False

    def remove(self, word):
        current = self.root
        letters = list(word)
        for i, letter in enumerate(letters):
            if letter not in current:
                return
            if len(current[letter]) > 1 or i == len(letters) - 1:
                del current[letter][self.end_symbol]
                return
            current = current[letter]

可以使用以下方式测试该类：

# 示例用法

# 创建一个 Trie 类的实例
# 插入单词
# 检查单词是否存在
# 删除单词
# 再次检查单词是否存在
# 输出结果

44、给定一个按升序排列的整数列表和一个目标值，使用

binary_search

函数在列表中查找目标值的索引。如果未找到目标值，则打印“Target not found”。

以下是实现该功能的代码示例：

def binary_search(lst, target):
    low = 0
    high = len(lst) - 1
    while low <= high:
        mid = (low + high) // 2
        if lst[mid] == target:
            return mid
        elif lst[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    print("Target not found")
    return -1

lst = [1, 2, 3, 4, 5]
target = 3
index = binary_search(lst, target)
print(index)  # 2
target = 6
index = binary_search(lst, target)  # Target not found

45、给定一个整数列表，使用bubble_sort函数将列表按升序排序，并打印排序后的列表。然后，提示用户输入一个目标值，并使用linear_search函数在排序后的列表中查找目标值的索引。如果未找到目标值，则打印“Target not found”。

以下是实现该功能的Python代码：

# 冒泡排序函数
def bubble_sort(lst):
    for i in range(len(lst)):
        for j in range(len(lst)-1):
            if lst[j] > lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst

# 线性搜索函数
def linear_search(lst, target):
    for i, val in enumerate(lst):
        if val == target:
            return i
    print('Target not found')
    return -1

# 主程序
lst = [3, 2, 5, 1, 4]

# 排序列表
sorted_lst = bubble_sort(lst)
print(sorted_lst)

# 提示用户输入目标值
target = int(input('请输入一个目标值: '))

# 查找目标值的索引
index = linear_search(sorted_lst, target)
if index != -1:
    print(index)

46、编写一个使用动态规划在加权图中找到最短路径的 Python 程序。

以下是使用动态规划在加权图中找到最短路径的 Python 程序：

from collections import defaultdict

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def add_edge(self, u, v, w):
        self.graph[u].append((v, w))

    def shortest_path(self, start, end):
        dp = {node: float('inf') for node in self.graph}
        dp[start] = 0
        for node in dp:
            for neighbor, weight in self.graph[node]:
                dp[neighbor] = min(dp[neighbor], dp[node] + weight)
        return dp[end] if dp[end] != float('inf') else 'Path not found'


g = Graph()

# 添加边
g.add_edge('A', 'B', 2)

# 添加边
g.add_edge('A', 'C', 3)

# 添加边
g.add_edge('B', 'D', 1)

# 添加边
g.add_edge('C', 'D', 4)

print(g.shortest_path('A', 'D'))  # 3