本文将介绍

三. 数据结构与算法（第 6 - 7 章）

6. 深入数据结构

列表（List）高级用法
列表推导式：
列表推导式是一种简洁地创建列表的方式。它的基本形式是在一个方括号内，包含一个表达式，后面跟着一个for循环，还可以有if条件语句。例如，要创建一个包含 1 到 10 的平方的列表，我们可以用普通的方法：

squares = []
for i in range(1, 11):
    squares.append(i ** 2)
print(squares) 

但使用列表推导式，就可以更简洁地写成：

squares = [i ** 2 for i in range(1, 11)]
print(squares) 

如果我们只想得到其中的偶数的平方，可以加上if条件：

even_squares = [i ** 2 for i in range(1, 11) if i % 2 == 0]
print(even_squares) 

列表的切片（Slicing）技巧：
切片可以用来获取列表中的一部分元素。它的基本语法是list[start:stop:step]。其中start表示起始索引（包含），stop表示结束索引（不包含），step表示步长。例如：

my_list = [10, 20, 30, 40, 50]

获取索引1到3（不包含3）的元素

print(my_list[1:3]) 

获取从开始到索引3（不包含3）的元素

print(my_list[:3])  

获取索引2到最后的元素

print(my_list[2:])  
``

获取整个列表的副本

```python
print(my_list[:])  

每隔一个元素获取，从索引0开始

print(my_list[::2])  

倒序获取整个列表

print(my_list[::-1])  

列表的排序和搜索算法应用：
排序：Python 列表有一个内置的sorted()函数可以对列表进行排序。例如：

my_list = [3, 1, 4, 1, 5, 9, 2, 6]
sorted_list = sorted(my_list)
print(sorted_list) 

也可以使用列表的sort()方法，它会直接修改原列表：

my_list = [3, 1, 4, 1, 5, 9, 2, 6]
my_list.sort()
print(my_list) 

搜索：如果要在列表中查找一个元素，可以使用in关键字。例如：

my_list = [3, 1, 4, 1, 5, 9, 2, 6]
if 4 in my_list:
    print("元素4在列表中")

如果要找到元素的索引，可以使用index()方法（如果元素不存在会报错）：

my_list = [3, 1, 4, 1, 5, 9, 2, 6]
try:
    print(my_list.index(4))
except ValueError:
    print("元素不在列表中")

字典（Dict）的高级用法
字典的遍历技巧：
可以使用for循环遍历字典的键、值或键值对。例如：

my_dict = {'name': 'Alice', 'age': 25, 'city': 'New York'}

遍历键

for key in my_dict:
    print(key)

遍历值

for value in my_dict.values():
    print(value)

遍历键值对

for key, value in my_dict.items():
    print(key, value)

字典的更新和合并：
可以使用update()方法来更新字典。例如：

my_dict = {'name': 'Alice', 'age': 25}
new_info = {'city': 'New York', 'job': 'Engineer'}
my_dict.update(new_info)
print(my_dict) 

如果要合并两个字典，也可以使用这种方法，或者使用字典解包（Python 3.5 及以上版本）：

dict1 = {'a': 1, 'b': 2}
dict2 = {'c': 3, 'd': 4}
merged_dict = {**dict1, **dict2}
print(merged_dict) 

使用字典实现一些数据结构（如计数器）：
例如，我们要统计一个字符串中每个字符出现的次数，可以用字典来实现：

string = "hello world"
char_count = {}
for char in string:
    if char in char_count:
        char_count[char] += 1
    else:
        char_count[char] = 1
print(char_count) 

其他数据结构相关模块（如 collections 模块）
deque（双端队列）：
deque是一种可以在两端高效添加和删除元素的数据结构。使用collections模块中的deque，首先要导入它：

from collections import deque
my_deque = deque([1, 2, 3])

在右端添加元素

my_deque.append(4)

在左端添加元素

my_deque.appendleft(0)
print(my_deque) 

从右端删除元素

my_deque.pop()

从左端删除元素

my_deque.popleft()
print(my_deque) 
defaultdict：

defaultdict是一个字典的变体，当访问不存在的键时，它会自动创建一个默认值。例如：

from collections import defaultdict
my_defaultdict = defaultdict(int)
my_defaultdict['a'] += 1
print(my_defaultdict) 

这里defaultdict(int)表示当访问不存在的键时，默认值为 0（因为int()返回 0），所以我们可以直接对不存在的键进行操作。

7. 算法基础

基本算法思想
递归：
递归是指一个函数在其定义中直接或间接地调用自身。一个简单的例子是计算阶乘。阶乘的定义是n! = n * (n - 1) * (n - 2) *… * 1，用递归实现如下：

def factorial(n):
    if n == 0 or n == 1:
        return 1
    return n * factorial(n - 1)

print(factorial(5)) 

在这个例子中，factorial函数在计算n的阶乘时，会调用自身来计算n - 1的阶乘，直到n为 0 或 1。
贪心算法：
贪心算法是一种在每一步选择中都采取当前状态下的最优决策，希望最终结果是全局最优的算法。例如，找零问题，假设我们有无限数量的面值为10、5和1的硬币，要找给顾客18元。贪心算法的思路是尽可能多地使用面值大的硬币。代码如下：

def make_change(amount):
    coins = [10, 5, 1]
    coin_count = [0, 0, 0]
    for i in range(len(coins)):
        coin_count[i] = amount // coins[i]
        amount %= coins[i]
    return coin_count

print(make_change(18)) 

这里我们先尽可能多地用10元硬币，然后用5元硬币，最后用1元硬币。
动态规划：
动态规划通常用于解决具有重叠子问题和最优子结构性质的问题。例如，计算斐波那契数列，简单的递归方法会有很多重复计算（因为F(n)=F(n - 1)+F(n - 2)，计算F(n - 1)和F(n - 2)时又会重复计算它们的子问题）。动态规划的方法可以避免这些重复计算：

def fibonacci(n):
    if n == 0 or n == 1:
        return n
    dp = [0] * (n + 1)
    dp[0], dp[1] = 0, 1
    for i in 2, n + 1:
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fibonacci(10)) 

这里我们使用一个列表dp来存储已经计算过的斐波那契数，避免了重复计算。
用 Python 解决简单的算法问题（如排序算法、查找算法等）
排序算法实现（除了使用内置的排序函数）：
冒泡排序：
冒泡排序的基本思想是比较相邻的元素，如果顺序不对就交换它们，重复这个过程直到整个列表都有序。代码如下：

def bubble_sort(my_list):
    n = len(my_list)
    for i in range(n):
        for j in range(0, n - i - 1):
            if my_list[j] > my_list[j + 1]:
                my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]
    return my_list

print(bubble_sort([3, 1, 4, 1, 5, 9, 2, 6])) 

插入排序：
插入排序是将未排序的数据插入到已排序的部分合适位置。代码如下：

def insertion_sort(my_list):
    for i in range(1, len(my_list)):
        key = my_list[i]
        j = i - 1
        while j >= 0 and key < my_list[j]:
            my_list[j + 1] = my_list[j]
            j -= 1
        my_list[j + 1] = key
    return my_list

print(insertion_sort([3, 1, 4, 1, 5, 9, 2, 6])) 

查找算法实现（除了使用in关键字和index()方法）：
二分查找（前提是列表已排序）：
二分查找的基本思想是每次将搜索区间缩小一半。代码如下：

def binary_search(my_list, target):
    low, high = 0, len(my_list) - 1
    while low <= high:
        mid = (low + high) // 2
        if my_list[mid] == target:
            return mid
        elif my_list[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

sorted_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(sorted_list, 5))