汕头企业网站怎么做,漳州微网站建设,wordpress照片加水印,网页搜索功能目录
00、前言#xff1a;
01、一维数组
一维数组的定义和初始化
一维变长数组
一维正向遍历 一维反向遍历
一维数组的区间操作 竞赛小技巧#xff1a;不用从a[0]开始#xff0c;从a[1]开始
蓝桥杯真题练习1
读入一维数组
例题一
例题二
例题三
实战训…目录
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[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[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,al1,...ar 的值加上 k。2 l r求区间 al,al1,...,ar 的和为多少。 【输入描述】 输入第 1 行包含两个正整数 N,Q分别表示数组 a 的长度和操作的个数。 第 2 行包含 N 个非负整数 a1,a2,...,aN表示数组 a 元素的初值。 第 3∼Q−2 行每行表示一共操作格式为以下两种之一 1 l r x2 l r 其含义如题所述。 【输出描述】 输出共 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 wprint(sum(a[L:R1]))else: # # 区间修改:把[L,R]的每个元素加上dq,L, R, d wfor i in range(L,R1):a[i]d
暴力法的计算量:O(m*n),循环m次每次对n个数进行操作。只能通过30%的测试。
暴力法只能通过30%的测试 100%的测试:1≤n,m≤ 要通过100%的测试的解法见“线段树”。 实战二 异或选数 2022年第十三届省赛 【问题描述】给定一个长度为 n 的数列A1A2... , An和一个非负整数x给定m次查询每次询问能否从某个区间[lr]中选择两个数使得他们的异或等于x。 【输入格式】输入的第一行包含三个整数n, m, x。第二行包含n个整数A1A2... , An。接下来m行每行包含两个整数li, ri表示询问区间[li, ri] 。 【输出格式】对于每个询问如果该区间内存在两个数的异或为x则输出yes否则输出no。 【评测用例规模与约定】对于20%的评测用例1≤n, m ≤100;对于40%的评测用例1 ≤n,m≤1000;对于所有评测用例1 ≤ n, m ≤1000000 ≤x 2201 ≤ li ≤ri ≤n0 ≤ Ai220。 【知识补充】
^异或运算符对应二进制位相等为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 # 初始化flag0表示不存在异或为xL,R map(int,input().split ()) # 读取区间# 遍历区间for j in range (L,R): # 遍历左端点for k in range(j1, R1): # 遍历右端点if a[j]^a[k] x: # 存在异或为xflag 1if flag 1: # 存在异或为xprint(yes)else: # 不存在异或为xprint (no)
对每个区间查询验算区间内的任意两个数复杂度0()共m个查询总复杂度0() 比赛限制最多只能循环次20%的测试循环次40%的测试循环次所以只能通过20%的测试。
【正解】通过100%的测试解法应使用“线段树” 解法。 实战三修改数组 题目描述 给定一个长度为 N 的数组 A[A1,A2,⋅⋅⋅,AN]数组中有可能有重复出现的整数。 现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2,A3,⋅⋅⋅,AN。 当修改 Ai 时小明会检查Ai 是否在 中出现过。如果出现过则小明会给 Ai 加上 1 如果新的 Ai 仍在之前出现过小明会持续给 Ai 加 1 直 到 Ai 没有在中出现过。 当 AN 也经过上述修改之后显然 A 数组中就没有重复的整数了。 现在给定初始的 A 数组请你计算出最终的 A 数组。 输入描述 第一行包含一个整数 N。 第二行包含 N 个整数 A1,A2,⋅⋅⋅,AN。 其中。 输出描述 输出 N 个整数依次是最终的 A1,A2,⋅⋅⋅,AN。 输入输出样例 输入 5
2 1 1 3 4输出 2 1 3 4 5 【问题解析】 暴力法 每遍历一个新的数就检查前面是否出现过每一次需要检查前面所有的数共有n个数每个数检查0(n)次所以总复杂度是0()的超时。
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 [[[ik*jk*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 的外卖店收到一个订单。 其中。 【输入样例】 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 如果你还没明白游戏规则可以参看下面一个简化的 4x4 迷宫的解说图 【代码演示】
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≤≤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]*(m1)) # 在第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,n1): # 上边for i2 in range(i1,n1): # 下边for j1 in range(1,m1): # 左边for j2 in range(j1,m1): # 右边sum 0# 对所有可能的矩阵内部进行求和for i in range(i1,i21): # 后两个for循环矩阵求和for j in range(j1,j21):sum a[i][j]if sum k: # 找出满足要求的矩阵ans 1
print(ans)
【正解】使用“前缀和 ”来求解可以通过100%的测试点击链接可以查看前缀和求解该题 实战二矩阵相乘 矩阵相乘lanqiao0J题号1550 题目描述 输入两个矩阵输出两个矩阵相乘的结果。 输入描述 输入的第一行包含三个整数n,mk表示n×m的矩阵和m×k的矩阵。接下来n行每行m个整数。再接下来m行每行k个整数。0n, m, k≤1000≤矩阵中的每个数≤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就加一,当summ*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 # 还没有加入矩阵
d0
# 下面三行可以用 for i in range(m*n): 代替
sum 0 # 统计走了多少个数
while sum m*n: # 没有走完m*n个数就一直走sum sum 1nx, 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, nyprint(a[x][y], end) # 输出当前走到的数a[x][y] -1 # 标记这个坐标点已经取过
第1行用dir数组表示4个方向代码简短很多。dir[0]表示向右前进一步dir[1]表示向上前进一步dir[2]表示向左前进一步dir[3]表示向下前进一步。
感谢观看下期再见
