数据结构编程实践20讲(Python版)—01数组

写在前面

数据结构是计算机科学中的一个重要概念，用于组织和存储数据，以便于高效的访问和修改。不同的数据结构适用于不同类型的应用场景，选择合适的数据结构对于算法的性能至关重要。

常见的数据结构可以分为线性和非线性两大类。

• 线性数据结构包括数组、链表、栈和队列，适合存储顺序关系的数据。数组提供随机访问能力，而链表则在插入和删除操作上更具灵活性。栈和队列分别实现后进先出（LIFO）和先进先出（FIFO）的访问模式。
• 非线性数据结构包括树和图。树结构（如二叉树、AVL树和B树）用于表示层次关系，广泛应用于搜索和排序。图则用于表示复杂的连接关系，适合网络、社交图等场景。

此外，散列结构（如哈希表和哈希集合）提供了快速的查找和插入操作，字典和集合则用于存储键值对和不重复元素。高级数据结构如Trie和并查集则解决特定问题，如字符串匹配和动态连通性。

该系列中所给的问题并不是最复杂的，同时给的解法的时间复杂度不一定是最优的，因为本系列主要讲解数据结构。

01 数组

S1 说明

数组是一种数据结构，用于存储固定大小的元素集合。每个元素在数组中的位置由一个索引（或下标）唯一标识。通常从零开始。数组中的所有元素类型相同，提供随机访问和直接存取的能力。

S2 举例

在Python中，数组可以通过列表、array模块或NumPy库实现。选择哪种实现方式取决于具体的需求，例如数据类型的统一性、性能需求以及可用的库。对于一般的应用，列表通常足够用；而对于科学计算，NumPy数组则提供了更高效的操作。

• 列表

a = [1, 2, 3, 8, 11]# 多维
b = [[1, 2, 1, -1, -2]]
c = [[1, 2, 1, -1, -2], [1, 2]]

• 自带的array模块

import array
my_array = array.array('i', [1, 4, 9, 64, 121])  # 'i'表示整型# 多维
rows = 3
cols = 3
multi_array = [array.array('i', [826] * cols) for _ in range(rows)]

• Numpy库

import numpy as np
my_array1 = np.array([2, 6, 12, 72, 132])# 多维
my_array2 = np.array([[2, 6, 12, 72, 132], [0, 2, 6, 56, 110]])

S3 问题：二维网格中的最小路径

给定一个$m\times n$ 的网格$grid$，其中 $grid[i][j]$表示到达该位置的代价。需要找到从$(0,0)$到$(m-1,n-1)$的最小路径和，只能往下、右两个方向移动。现有网格如下：

求解思路

1. 题目中的网格代价可以用二维数组表示：

grid_cost = [[3, 2, 2, 1], [4, 3, 1, 2], [1, 2, 4, 2], [3, 2, 3, 2]]

2. 利用动态规划算法求解：

• 状态定义：定义$dp[i][j]$为到达$(i,j)$的最小路径和
• 状态转移：从上方和左方转移到$(i,j)$，因此
  $$dp[i][j]=grid[i][j]+min(dp[i-1][j],dp[i][j-1])$$
• 边界条件：
  • 起始点：$dp[0][0]=grid[0][0]$
  • 第一行(根据条件，只能从左边过来)：$dp[0][j]=dp[0][j-1]+grid[0][j]$
  • 第一列(根据条件，只能从上边过来)：$dp[i][0]=dp[i-1][0]+grid[i][0]$
• 结果：最终的结果为$dp[m-1][n-1]$

Python3程序

def minPathSum(grid):m, n = len(grid), len(grid[0])dp = [[0] * n for _ in range(m)]  # 存储最小路径和dp[0][0] = grid[0][0]# 初始化第一行for j in range(1, n):dp[0][j] = dp[0][j - 1] + grid[0][j]# 初始化第一列for i in range(1, m):dp[i][0] = dp[i - 1][0] + grid[i][0]# 填充 dp 表for i in range(1, m):for j in range(1, n):dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]# 获取最小路径和min_sum = dp[m - 1][n - 1]return min_sum# 示例输入
grid_cost = [[3, 2, 2, 1],[4, 3, 1, 2],[1, 2, 4, 2],[3, 2, 3, 2]
]min_sum  = minPathSum(grid_cost)
print(f"最小路径和: {min_sum}")# 最小路径和: 14

S4 问题：图像左右变换

给定一张图片，实现该图片的左右互换。

求解思路

1. 用PIL包读取RGB模式的图片，然后利用numpy获得三维数组
2. 可利用$left\_pixel,right\_pixel=right\_pixel,left\_pixel$实现左右像素互换
3. 三维数组利用matplotlib可视化

Python3程序

import numpy as np
from PIL import Image
import matplotlib.pyplot as pltdef flip_image_horizontally(imagepath):original_image = Image.open(imagepath).convert('RGB')# 读取为RGBrgb_data = np.array(original_image).transpose([2, 0, 1])challels, rows, cols = rgb_data.shape# 读取三维数组for c in range(challels):for i in range(rows):for j in range(cols // 2):# 交换左右像素的 RGB 值rgb_data[c][i][j], rgb_data[c][i][cols - 1 - j] = (rgb_data[c][i][cols - 1 - j], rgb_data[c][i][j])# 可视化plt.imshow(rgb_data.transpose([1, 2, 0]))plt.axis('off')plt.show()if __name__ == '__main__':imagepath = '你的图片路径'flip_image_horizontally(imagepath)

S5 问题：青蛙过河

一只青蛙想要过河。 假定河流被等分为若干个单元格，并且在每一个单元格内有可能放有一块石子，也有可能没有。

现给你石子的位置列表$stones$（用单元格序号表示）， 请判定青蛙能否成功过河（青蛙可以跳上石子，但是不可以跳入水中）即能否在最后一步跳至最后一块石子上。开始时， 青蛙默认已站在第一块石子上，并可以假定它第一步只能跳跃 1 个单位（即只能从单元格 1 跳至单元格 2 ）。

如果青蛙上一步跳跃了$k$个单位，那么它接下来的跳跃距离只能选择为$k-1、k$或$k+1$个单位。 另请注意，青蛙只能向前方（终点的方向）跳跃。

例如：给定$stones=[0,1,3,5,6,8,12,17]$，具体见下图：

按照如下方案跳跃：跳 1 个单位到第 2 块石子(位置1), 然后跳 2 个单位到第 3 块石子(位置3), 接着 跳 2 个单位到第 4 块石子(位置5), 然后跳 3 个单位到第 6 块石子(位置8), 跳 4 个单位到第 7 块石子(位置12), 最后，跳 5 个单位到第 8 个石子（即最后一块石子，位置17）。

求解思路

1. 利用深度优先搜索（DFS）结合记忆化来解决这个问题

• 状态表示
  使用一个递归函数 dfs(position, k)，其中 position 是青蛙当前所在的位置，k 是上一次的跳跃距离。
• 终止条件
  如果 position 是最后一块石头的位置，返回 True。
• 递归
  • 对于每一次跳跃，尝试 k - 1、k 和 k + 1 的跳跃距离。
  • 检查新位置是否在 stones 中，并且是否可以到达。
• 记忆化
  使用一个字典来存储已经访问过的状态，以避免重复计算。

Python3程序

def canCross(stones):stone_set = set(stones)memo = {}# DFS深度优先搜索def dfs(position, k):# 判断终止条件if position == stones[-1]:return True# 判断这个位置是否来过，并且是不是可以到达的if (position, k) in memo:return memo[(position, k)]# 遍历可能的跳跃单位for jump in [k - 1, k, k + 1]:if jump > 0:next_position = position + jump# 有石头，并且可到达if next_position in stone_set and dfs(next_position, jump):# 存储已经访问过的状态memo[(position, k)] = Truereturn Truememo[(position, k)] = Falsereturn Falsereturn dfs(stones[0], 0)if __name__ == '__main__':stones = [0, 1, 3, 5, 6, 8, 12, 17]print(canCross(stones))

结果

True