数据结构-第一期——数组（Python）

00、前言：

01、一维数组

一维数组的定义和初始化

一维变长数组

一维正向遍历

一维反向遍历

一维数组的区间操作

竞赛小技巧：不用从a[0]开始，从a[1]开始

蓝桥杯真题练习1

读入一维数组

例题一

例题二

例题三

实战训练

实战一：区间修改、区间求和

实战二：异或选数

实战三：修改数组

02、多维数组

二维数组的初始化

二维数组访问

三维数组的初始化

三维数组访问

蓝桥杯真题练习2

读取二维数组

【输入字符串】

【输入数字】

例题一：外卖店优先级

例题二：迷宫

实战训练

实战一：统计子矩阵

实战二：矩阵相乘

实战三：回行取数

00、前言：

什么是数据结构?

每道编程题都有输入数据和输出数据，输入数据是代码处理的对象，输出数据是代码运行的结果。代码在执行过程中需要用一定的方式来存储、处理数据，就是数据结构。

数据结构包含什么？

线性表(数组、链表)、栈和队列、串、多维数组和广义表、哈希、树和二叉树、图、排序等。

基础数据结构：

数组、链表、队列、栈、二叉树。

01、一维数组

把数据连续存储在空间中。
虽然简单，但是在竞赛中至关重要，因为其他数据结构都可以用数组来模拟，即“物理存储上是数组，逻辑上是其他数据结构”。
用数组模拟其他数据结构，不是工程项目的正规做法，但是非常适合算法竞赛，因为这样编码快、不易出错。
某些难题，可以用数组处理数据求得部分分数（暴力法）

一维数组的定义和初始化

a=['']*10    # 定义空数组
b=[0]*10     # 初始化数组
print(a)
print(b)
# ['', '', '', '', '', '', '', '', '', ''],
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

# 也可以利用列表生成式来初始化
c = [0 for i in range( 10)]
d = [i for i in range(1,10)]
print(c)
print(d)
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

PS:列表生成式：[i for i in range(1,10)]

一维变长数组

a= []
for i in range(1,10):
    a.append( i )
print(a)
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

一维正向遍历

s= [0,1,2,3,4,5,6,7,8,9]
for i in s:
    print(i,end=" ")  # # 用空格分隔，同行输出
# 0 1 2 3 4 5 6 7 8 9

s= [0,1,2,3,4,5,6,7,8,9]
for i in range(len(s)):
    print(s[i],end=" ")
# 0 1 2 3 4 5 6 7 8 9

s = ['1','2','3','4']*2
for i in s:
    print(int(i),end=" ")
# 1 2 3 4 1 2 3 4

一维反向遍历

s = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in range(len(s)-1,-1,-1):# 中间的-1表示遍历到最后一个元素，即第一个元素(根据遍历方向决定，不是由数组本身决定)  
    print(s[i], end=" ")
# 9 8 7 6 5 4 3 2 1 0

# 比上面的方法更简洁
s = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for i in s[::-1]: 
    print(i, end=" ")
# 9 8 7 6 5 4 3 2 1 0

一维数组的区间操作

s = [0, 1, 2, 3, 4, 5, 6, 7]
print(min(s)) # 等价于min(s[:])              0
print(max(s[2:5])) # 左闭右开区间：[2,5)      4
print(sum(s[2:]))  #                        27  
print(sum(s[2:-1])) # -1是到倒数第二个，因为是左闭右开区间：[2,7)  20

竞赛小技巧：不用从a[0]开始，从a[1]开始

有时候输入是 $a_1,a_2,......a_n$ ，那不从a[0]开始，从a[1]开始可以和题目下标匹配，在复杂的程序题中不容易出错。具体用法后面例题会有所体现。

# 从a[1]开始
a = [0]+list(map(int,input().split())) # 输入：1 2 3
print(a)
# [0,1,2,3]

PS: map(int,input().split())可输入多个用空格分隔的元素，并转换为int类型

蓝桥杯真题练习1

读入一维数组

知识点：需要读取一维数组的题目的输入描述一般是：输入第一行是一个的总数n，代表数组a的元素个数。①第二行包含n个整数a1,a2,…., an。②接下来n行每行读入一个元素。下面介绍两种情况的输入方法。

情况①：第二行包含n个整数a1,a2,…., an。例如下面例题一、二

# 读入数字
# 法一：
n = map(int,input().split())
a= list(map(int,input().split()))        # 从a[0]开始
# a= [0]+list(map(int,input().split()))  # 从a[1]开始

# 法二：
n = int(input())
a = [int(i) for i in input().split()]     # 从a[0]开始
# a= [0]+[int(i) for i in input().split()]# 从a[1]开始

情况②：接下来n行每行读入一个元素。例如下面例题三

n = int(input())
num = []
for i in range(n):
    num.append(int(input()))

例题一

n,s = map(int,input().split())
a= list(map(int,input().split()))    # 存到列表里

# 打印，查看输出情况
for i in range(n):
    print(a[i],end=" ")

注意：做题的过程中要多打印变量，可以保证出错了可以及时发现。

例题二

n = int(input())
a = [int(i) for i in input().split()] # 从a[0]开始读

题目输入是 $a_1,a_2,......a_n$ ，那就不从a[0]开始，从a[1]开始，可以和题目下标匹配。

n = int(input())
a = [0]+[int(i) for i in input().split()]  # #从a[1]开始读。a[0]不用

例题三

不在同一行读取数据：先创建一个空数组，用for循环+append()添加到数组里。

n = int(input())
num = []
for i in range(n):
    num.append(int(input()))

实战训练

实战一：区间修改、区间求和
【题目描述】
给定一个长度为 N 的数组 a，其初值分别为 a1,a2,…,aN。
现有 Q 个操作，操作有以下两种：
1 l r k，将区间 al,al+1,…ar 的值加上 k。
2 l r，求区间 al,al+1,…,ar 的和为多少。
【输入描述】
输入第 1 行包含两个正整数 N,Q，分别表示数组 a 的长度和操作的个数。
第 2 行包含 N 个非负整数 a1,a2,…,aN，表示数组 a 元素的初值。
第 3∼Q−2 行每行表示一共操作，格式为以下两种之一：
1 l r x
2 l r
其含义如题所述。
$1\leq N,Q \leq 10^5,1\leq l \leq r \leq N,-10^9\leq k,a_i\leq 10^9$
【输出描述】
输出共 Q 行，每行包含一个整数，表示相应查询的答案。
【输入输出样例】
输入
5 5
1 2 3 4 5
2 1 2
1 2 3 1
2 1 3
1 1 5 1
2 1 5
输出
3
8
22

【问题解析】

区间修改和区间求和题目一般使用线段树求解，本文仅用暴力法求解，遍历m次操作，每次对n个数进行操作。

n,m = map( int, input( ).split( ))          # 数组长度，操作个数
a = [0] + list(map(int, input( ).split( ))) # 数组元素
for i in range(m):
    w = list(map( int, input( ).split( )))  # 操作：序号 区间下限 区间上限 (要加上的值)
    if len(w) == 3: # # 区间询问:[L,R]的区间和
        q,L, R = w
        print(sum(a[L:R+1]))
    else: # # 区间修改:把[L,R]的每个元素加上d
        q,L, R, d = w
        for i in range(L,R+1):
            a[i]+=d

暴力法的计算量:O(m*n),循环m次，每次对n个数进行操作。只能通过30%的测试。

暴力法只能通过30%的测试， 100%的测试:1≤n,m≤ $10^{5}$ ，要通过100%的测试的解法见“线段树”： $O(mlog_2n)$ 。

实战二：异或选数
2022年第十三届省赛
【问题描述】给定一个长度为 n 的数列A1，A2，… , An和一个非负整数x，给定m次查询，每次询问能否从某个区间[l，r]中选择两个数使得他们的异或等于x。
【输入格式】输入的第一行包含三个整数n, m, x。第二行包含n个整数A1，A2，… , An。接下来m行，每行包含两个整数li, ri表示询问区间[li, ri] 。
【输出格式】对于每个询问，如果该区间内存在两个数的异或为x则输出yes，否则输出no。
【评测用例规模与约定】对于20%的评测用例，1≤n, m ≤100;对于40%的评测用例，1 ≤n,m≤1000;对于所有评测用例，1 ≤ n, m ≤100000，0 ≤x ＜220，1 ≤ li ≤ri ≤n，0 ≤ Ai<220。

【知识补充】

^（异或运算符）：对应二进制位相等为0,不等为1.

a = 22
b = 10
c = a^b
print(c)        # 26
print(bin(c))   # 0b11100
print(bin(a))   # 0b10110
print(bin(b))   # 0b01010

【问题解析】

暴力法：对每个区间的左右端点进行遍历，每次遍历判断区间内的任意两个数是否存在异或为x，是的话输出“yes”，否则输出“no”。

# 暴力法获取20%测试分
n, m, x = map(int, input ().split ())
a=[0]+list (map(int, input (). split ())) #从a[1]开始
for i in range (m) :
    flag = 0                           # 初始化flag=0，表示不存在异或为x
    L,R = map(int,input().split ())    # 读取区间
    # 遍历区间
    for j in range (L,R):              # 遍历左端点
        for k in range(j+1, R+1):      # 遍历右端点
            if a[j]^a[k] == x:         # 存在异或为x
                flag = 1
    if flag == 1: # 存在异或为x
        print('yes')
    else:         # 不存在异或为x
        print ('no')

对每个区间查询，验算区间内的任意两个数，复杂度0( $n^{2}$ )，共m个查询，总复杂度0( $mn^{2}$ )，比赛限制最多只能循环 $10^7$ 次，20%的测试循环 $100^3=10^6$ 次，40%的测试循环 $1000^3=10^9$ 次，所以只能通过20%的测试。

【正解】通过100%的测试解法应使用“线段树” 解法。

实战三：修改数组
题目描述
给定一个长度为 N 的数组 A=[A1,A2,⋅⋅⋅,AN]，数组中有可能有重复出现的整数。
现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2,A3,⋅⋅⋅,AN。
当修改 Ai 时，小明会检查Ai 是否在 $A_1 \sim A_{i-1}$ 中出现过。如果出现过，则小明会给 Ai 加上 1 ；如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直到 Ai 没有在 $A_1 \sim A_{i-1}$ 中出现过。
当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。
现在给定初始的 A 数组，请你计算出最终的 A 数组。
输入描述
第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。
其中， $1 \leq N \leq 10^5,1 \leq A_i \leq 10^6$ 。
输出描述
输出 N 个整数，依次是最终的 A1,A2,⋅⋅⋅,AN。
输入输出样例
输入
5
2 1 1 3 4
输出
2 1 3 4 5

【问题解析】

暴力法
每遍历一个新的数，就检查前面是否出现过，每一次需要检查前面所有的数共有n个数，每个数检查0(n)次，所以总复杂度是0( $n^{2}$ )的，超时。

n = int(input( ))
A = [int(i) for i in input().split()] # 读入A1,A2,⋅⋅⋅,AN存到列表里
for i in range(1,n):
    while A[i] in A[0:i]: # 检查之前有没有出现过，直到没有出现才退出
        A[i] += 1         # 出现过就+1
for i in A:
    print(i,end =" ")

【正解】通过100%的测试解法应使用“并查集 ” 解法。

点击链接查看该题的并查集解法：数据结构-第七期——并查集的应用（Python）

02、多维数组

二维数组的初始化

# 两个for循环初始化
p = [[0 for i in range(5)]for j in range(2)]

# 一个for循环初始化（推荐）
p = [[0]*5 for i in range(2)]
# [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

二维数组访问

s=[[1,2,3],[4,5,6]]
# 遍历子数组元素
for i in range(2):     # 子数组
    for j in range(3): # 子数组元素
        print(s[i][j],end=" ")
# 1 2 3 4 5 6

三维数组的初始化

p = [[[0 for _ in range(3)]for __ in range(4)]for ___ in range(2)]
p = [[[0]*3 for __ in range(4)]for ___ in range(2)]
print(p)
# [[[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]], [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]]

# 三维列表（维度：2,3,4）存放0-23
n,m,k = 2,3,4
p = [[[i+k*j+k*m*l for i in range(k)]for j in range(m)]for l in range(n)]
print(p)
# [[[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11]], [[12, 13, 14, 15], [16, 17, 18, 19], [20, 21, 22, 23]]]

三维数组访问

a = [[[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11]], [[12, 13, 14, 15], [16, 17, 18, 19], [20, 21, 22, 23]]]
for i in range(2):
    for j in range(3):
        for k in range(4):
            print(a[i][j][k],end=" ")
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

蓝桥杯真题练习2

读取二维数组

知识点：需要读取二维数组的题目的输入描述一般是：输入第一行是两个的正整数m, n，表示矩阵的行和列。接下来m行每行n个数/字符串（，用空格隔开），表示这个矩阵。下面介绍输入字符串和输入数字的方法。

【输入字符串】

如果输入需要用空格隔开，代码需要加多一个split()。（情况少见）

m,n = map(int,input().split())
a = []
for  i in range(m):
    a.append(list(input().split()))

如果输入不需要用空格隔开，例如下面的例题二。

m,n = map(int,input().split())
a = []
for  i in range(m):
    a.append(list(input()))
# 虽然输入没有隔开，但list会将输入的字符串拆成单字符存到列表

【输入数字】

一般都是要用空格隔开的，并且要转换成整数类型。例如下面的例题一。

n, m= map( int, input( ).split( ))
a=[]
for i in range(m):
    a.append([int(i) for i in input( ).split( )])

例题一：外卖店优先级
2019年第十届蓝桥省赛
仅要求读取数据即可
【输入描述】
第一行包含 3 个整数 N,M,T。
以下 M 行每行包含两个整数 ts,id，表示 ts 时刻编号 id 的外卖店收到一个订单。
其中， $1 \leq N,M,T \leq 10^5,1 \leq ts \leq T,1 \leq id \leq N$ 。
【输入样例】
2 6 6
1 1
5 2
3 1
6 2
2 1
6 2

【代码展示】

n, m, T = map( int, input( ).split( ))
a=[]
priorty = []
for i in range(m):
    a.append([int(i) for i in input( ).split( )])

PS:读入一行并拆开，存放到数组：a.append([int(i) for i in input( ).split( )])

例题二：迷宫
2017年第八届蓝桥杯省赛，填空题，1anqiao0J题号641
仅要求读取数据即可
【问题描述】
给出一个迷宫，问迷宫内的人有多少能走出来。迷宫如右图所示:每个位置上有一个人，共100人。每个位置有指示牌，L表示向左走,R表示向右走，U表示向上走，D表示向下走。开始的时候，直升机把 100 名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。
请你计算一下，最后，有多少玩家会走出迷宫，而不是在里边兜圈子？
【输入描述】
输入10行，每行10个字母（U、D、L、R）
【输入样例】
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
如果你还没明白游戏规则，可以参看下面一个简化的 4×4 迷宫的解说图：

【代码演示】

m,n = map(int,input().split())
mp = []
for  i in range(m):
    a.append(list(input()))
print(mp)
# 也可以用下面的方法
mp =[[''*10] for i in range(10 )] # 初始化二维数组：用来存迷宫
for i in range(10):
    mp[i]=list(input( )) #二维矩阵存迷宫:一次读入一行（一维数组），用空格分隔
    # list将读入的字符串拆开放到列表里
print(mp)

# 演示（这里只输入一行）
# 输入：UDDLUULRUL
# 输出：[['U', 'D', 'D', 'L', 'U', 'U', 'L', 'R', 'U', 'L'], [''], [''], [''], [''], [''], [''], [''], [''], ['']]

正解:DFS搜索

实战训练

实战一：统计子矩阵
2022年第十三届省赛15分lanqiaoOj题号2109
问题描述
给定一个 N×M 的矩阵 A, 请你统计有多少个子矩阵 (最小 1×1, 最大N×M) 满足子矩阵中所有数的和不超过给定的整数 K ?
输入格式
第一行包含三个整数 N,M 和 K.
之后 N 行每行包含 M 个整数, 代表矩阵 A.
输出格式
一个整数代表答案。
样例输入
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
样例输出
19
样例说明
满足条件的子矩阵一共有 19 , 包含:
大小为 1×1 的有 10 个。
大小为 1×2 的有 3 个。
大小为 1×3 的有 2 个。
大小为 1×4 的有 1 个。
大小为 2×1 的有 3 个。
评测用例规模与约定
对于 30% 的数据, N,M≤20.
对于 70% 的数据, N,M≤100.
对于 100% 的数据, 1≤N,M≤500;0≤ $A_{ij}$ ≤1000;1≤K≤250000000.

【处理输入】
Python如何读矩阵?

定义矩阵a[ ][ ]
从a[1][1]读到a[n][m]（不用第零行和第零列,从a[1][1]开始）

【思路】（暴力法）

用i1、i2、 j1、j2框出一个子矩阵
用i、j两重for循环统计子矩阵和

【复杂度】

6个for循环，O(N^6)

【代码演示】

暴力法: 通过30%测试

n, m, k = map(int, input().split())
a = [[0] for i in range(n)]
# print(a) # 多打印，没坏处
a.insert(0,[0]*(m+1))        # 在第0行插入一行0（不用第零行）
for i in range(1, n + 1):    # 每行a[0]不用，即第一列为0（不用第零列）
    a[i].extend(map(int, input().split()))
# print(a)
ans = 0
# 四条边，每次移动一边，需要四个for循环遍历所有可能的矩阵
# 前四个for循环遍历矩阵
for i1 in range(1,n+1):              # 上边
    for i2 in range(i1,n+1):         # 下边
        for j1 in range(1,m+1):      # 左边
            for j2 in range(j1,m+1): # 右边
                sum = 0
                # 对所有可能的矩阵内部进行求和
                for i in range(i1,i2+1):   # 后两个for循环矩阵求和
                    for j in range(j1,j2+1):
                        sum += a[i][j]
                if sum <= k:  # 找出满足要求的矩阵
                    ans += 1
print(ans)

【正解】使用“前缀和 ”来求解，可以通过100%的测试（点击链接可以查看前缀和求解该题）

实战二：矩阵相乘
矩阵相乘lanqiao0J题号1550
题目描述
输入两个矩阵，输出两个矩阵相乘的结果。
输入描述
输入的第一行包含三个整数n,m，k，表示n×m的矩阵和m×k的矩阵。接下来n行，每行m个整数。再接下来m行，每行k个整数。0<n, m, k≤100，0≤矩阵中的每个数≤1000。
输出描述
输出n行，每行k个整数，表示矩阵相乘的结果。
输入输出样例
输入
2 1 3
1
2
1 2 3
输出
1 2 3
2 4 6

【问题解析】

n,m,k = map( int , input( ).split( ))
A =[]
B =[]
C = [[0]*k for i in range(n)]
for i in range(n):   A.append(list(map( int , input( ).split( ))))# 读入a矩阵
for i in range(m):   B.append(list(map( int , input( ).split( ))))# 读入b矩阵
# 三个for循环计算矩阵乘法
for i in range(n):  # 累加n次
    for j in range(m):
        for l in range(k):c[i][l] += A[i][j]*B[j][l]
# 打印矩阵C
for i in range(n):
    for j in range(k):   
        print(C[i][j],end=" ")
    print()            #换行

实战三：回行取数
回形取数lanqiao0J题号1517
题目描述
回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一开始位于矩阵左上角，方向向下。
输入描述
输入第一行是两个不超过 200 的正整数 m,n，表示矩阵的行和列。接下来 m 行每行 n 个整数，表示这个矩阵。
输出描述
输出只有一行，共 mn 个数，为输入矩阵回形取数得到的结果。数之间用一个空格分隔，行末不要有多余的空格。
输入输出样例
输入
3 3
1 2 3
4 5 6
7 8 9
输出
1 4 7 8 9 6 3 2 5

【解题思路】

这道题不是正常的二维数组遍历，而是以一种特殊的方式遍历，所以本题不使用二维数组，用一维数组即可。

初始化：x,y=-1,0，表示还没进入矩阵
每走一步sum就加一,当sum>m*n（总数）时，表示已经遍历完矩阵。
判断是否出错（出界和走到了取过的数），是的话就回到回到出错前调整方向后再走，否则就按照原来的发现继续前进。
走过的数就输出，并标记这个数为已经取过了

【代码演示】

dir = [(1,0),(0,1),(-1,0),(0,-1)]  #4个方向
m, n = map( int, input( ).split( ))
a=[]
for i in range(m): a.append(input( ).split( ))
x, y = -1,0             # 还没有加入矩阵
d=0
# 下面三行可以用 for i in range(m*n): 代替
sum = 0                 # 统计走了多少个数
while sum < m*n:        # 没有走完m*n个数就一直走
    sum = sum + 1
    nx, ny = x + dir[d][0], y + dir[d][1]
    if nx < 0 or nx >= m or ny < 0 or ny >= n or a[nx][ny]==-1:# 出错：走出边界/走到了取过的数
        d =(d +1)%4    # 调整方向。循环链表操作：取余
        x, y = x + dir[d][0], y + dir[d][1] # 回到出错前调整方向后再走
    else:      # 没有出界和取过的数就按照原来方向前进
        x, y = nx, ny
    print(a[x][y], end='')         # 输出当前走到的数
    a[x][y] = -1                   # 标记这个坐标点已经取过

第1行用dir数组表示4个方向，代码简短很多。dir[0]表示向右前进一步，dir[1]表示向上前进一步，dir[2]表示向左前进一步，dir[3]表示向下前进一步。

感谢观看，下期再见！

文章出处登录后可见！

已经登录？立即刷新

数据结构-第一期——数组（Python）

00、前言：

01、一维数组

一维数组的定义和初始化

一维变长数组

一维正向遍历

一维反向遍历

一维数组的区间操作

竞赛小技巧：不用从a[0]开始，从a[1]开始

蓝桥杯真题练习1

读入一维数组

例题一

例题二

例题三

实战训练

实战一 ：区间修改、区间求和

【题目描述】

【输入描述】

【输出描述】

【输入输出样例】

实战二 ：异或选数

实战三：修改数组

题目描述

输入描述

输出描述

输入输出样例

【问题解析】

02、多维数组

二维数组的初始化

二维数组访问

三维数组的初始化

三维数组访问

蓝桥杯真题练习2

读取二维数组

【输入字符串】

【输入数字】

例题一：外卖店优先级

【输入描述】

【输入样例】

例题二：迷宫

实战训练

实战一：统计子矩阵

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

评测用例规模与约定

实战二：矩阵相乘

输入输出样例

实战三 ：回行取数

题目描述

输入描述

输出描述

输入输出样例

感谢观看，下期再见！

相关推荐

实战一：区间修改、区间求和

实战二：异或选数

实战三：回行取数