蓝桥杯3----数据结构篇（数组、链表、队列）——python_数据结构篮桥杯网站

数组

一维数组

import os
import sys
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:
        q,L,R=w
        print(sum(a[L:R+1]))
    else:
        q,L,R,d=w
        for i in range(L,R+1):
            a[i]+=d
1
2
3
4
5
6
7
8
9
10
11
12
13

二维数组

mp=[[''*10] for i range(10)]
for i in range(10):
    mp[i]=list(input())
1
2
3

统计子矩阵 2022年第十三届省赛 15分 lanqiaoOj 题号2109

【问题描述】给定一个N×M的矩阵A，请你统计有多少个子矩阵 (最小1×1，最大N×M) ，满足子矩阵中所有数的和不超过给定的整数K?

【输入格式】第一行包含三个整数N, M和K，之后N行每行包含M个整数，代表矩阵A。

【输出格式】一个整数代表答案。

暴力 通过30%测试

import os
import sys
n,m,k=map(int , input().split())
a=[[0] for i  in  range(n)]
a.insert(0, [0]*(m+1))
for i in range(1, n+1):
    a[i].extend(map(int , input().split()))
ans= 0
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 j in range(j1, j2+1):
                        sum+= a[i][j]
                if sum<=k: ans +=1
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

通过30%测试

修改数组 2019年第十届省赛 lanqiaoOJ题号185

【题目描述】
给定一个长度为N的数组A = [A1, A2,…,AN]，数组中有可能有重复出现的整数。现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改A2, A3, …, AN。当修改Ai时，小明会检查Ai是否在A1~ Ai-1中出现过。如果出现过，则小明会给Ai加上1；
如果新的Ai仍在之前出现过，小明会持续给Ai加1，直到Ai没有在A1~Ai-1中出现过。当AN也经过上述修改之后，显然A数组中就没有重复的整数了。现在给定初始的A数组，请你计算出最终的A数组。
【输入】
第一行包含一个整数N(1≤N≤100000)，第二行包含N个整数A1, A2, …, AN (1≤Ai≤1000000)。
【输出】输出N个整数，依次是最终的A1, A2, …, AN
【评测用例规模与约定】
对于 80% 的评测用例，1≤N≤10000
对于所有评测用例，1≤N≤100000，1≤Ai ≤1000000

暴力

import os
import sys
n=int(input())
a=list(map(int , input().split())
for i in range(1,n):
    while a[i] in A[0:i]:
        a[i] +=1
for i in a:
    print(i,end=' ')
1
2
3
4
5
6
7
8
9

矩阵相乘 lanqiaoOJ题号1550

【题目描述】
输入两个矩阵，输出两个矩阵相乘的结果。
【输入描述】
输入的第一行包含三个整数n，m，k，表示n×m的矩阵和m×k的矩阵。接下来n行，每行m个整数。再接下来m行，每行k个整数。0<n,m,k≤100，0≤矩阵中的每个数≤1000。

暴力

链表

Python的列表list，可以当成链表、队列、栈、数组来使用

列表list：连续存储，相当于数组
链表：不连续存储
手写链表的实现

from time import *
class Node():
    def __init__(self,data):
        self.data = data
        self.next = None
class SingleLinkList():
    def __init__(self, node = None):
        self.__head = node
    def right_insert(self,  x , y):
        pre = self.__head
        while pre.data != x:  pre = pre.next
        node = Node(y)
        node.next = pre.next
        pre.next = node
    def print_list(self):
        cur = self.__head
        while cur != None:
            print(cur.data, end=' ')
            cur = cur.next
n = 10
start = time()
a = SingleLinkList(Node(0))
for i in range(1,n):
    a.right_insert(0,i)    
end = time()
print("time=", end - start)
a.print_list()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

自行车停放 lanqiaoOJ题号1518

有n辆自行车依次来到停车棚，除了第一辆自行车外，每辆自行车都会恰好停放在已经在停车棚里的某辆自行车的左边或右边。(e.g.停车棚里已经有3辆自行车，从左到右编号为：3, 5, 1。现在编号为2的第4辆自行车要停在5号自行车的左边，所以现在停车棚里的自行车编号是：3, 2, 5, 1)。
给定n辆自行车的停放情况，按顺序输出最后停车棚里的自行车编号。n≤100000。
【输入描述】
第一行一个整数n。 n≤100000
第二行一个整数a。表示第一辆自行车的编号。
以下 n-1行，每行 3个整数 x, y, z。 z = 0时，表示编号为 x 的自行车恰停放在编号为 y 的自行车的左边。 z = 1时，表示编号为 x 的自行车恰停放在编号为 y 的自行车的右边。
【输出描述】
从左到右输出停车棚里的自行车编号。

class Node():
    def __init__(self,data):
        self.data = data
        self.next = None
class SingleLinkList():
    def __init__(self, node = None):
        self.__head = node
    def left_insert(self,x, y):
        pre = self.__head
        while pre.next.data != x:  pre = pre.next
        node = Node(y)
        node.next = pre.next
        pre.next = node
    def right_insert(self,x, y):
        pre = self.__head
        while pre.data != x:  pre = pre.next
        node = Node(y)
        node.next = pre.next
        pre.next = node
    def print_list(self):
        cur = self.__head
        while cur != None:
            print(cur.data, end=' ')
            cur = cur.next
      
n = int(input())
a = int(input())
node = Node(a)
li = SingleLinkList(node)
for i in range(n-1):
    x,y,z = map(int, input().split())
    if z==0:   li.left_insert(y,x)
    else:      li.right_insert(y,x)
li.print_list()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

测试数据
4
3
1 3 1
2 1 0
5 2 1

约瑟夫环 lanqiao0J题号1111

有n个人围坐在圆桌周围，现从某个位置 k上的人开始报数，报数到m的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再报数到m的人站出来。依次重复下去，直到全部的人都站出来为止。试设计一个程序求出这n个人的出列顺序。

循环链表

n, k,m=map(int,input().split())
a=list(range(1,n+1))
i=k-1
while len(a)>0:
    i=(i+m-1)%len(a)
    print(a.pop(i))
1
2
3
4
5
6

队列

三种方法表示

队列：Queue
列表： list 可以模拟队列，但是一般不用，因为很慢
双端队列：deque

性能：list最慢， Queue较慢，deque比Queue快10倍以上

使用库函数queue

q.put()，从队尾插入
q.get()，从队头删除，并返回
q.qsize()，队列大小
q.empty()，队列是否为空

from queue import *
n = 10
q = Queue()
for i in range(n):   q.put(i)
print(q.qsize())
print(q.empty())

for i in range(n):   
    a=q.get()
    print(a,end=' ')
print()
print(q.qsize())
print(q.empty())
1
2
3
4
5
6
7
8
9
10
11
12
13

使用list

q.append()，从队尾插入
del q[0] 删除队头
len(q) 队列大小
if not q 队列为空

n = 10
q = []
for i in range(n):  q.append(i)
print(q)
print(len(q))

for i in range(n):
    print(q[0],end=' ')  #打印队头
    del q[0]       #删除队头
print(len(q))
if not q: print('empty')
1
2
3
4
5
6
7
8
9
10
11

使用双端队列 deque

append：入队，从队列右端（队尾）插入
appendleft：入队，从队列左端（队头）插入
pop：出队，从队列右端（队尾）删除一个元素，并返回该元素
popleft：出队，从队列左端（队头）删除一个元素，并返回该元素
len() 队列大小
if q 判断空

from collections import *
n = 10
q = deque()
for i in range(n):   q.append(i)
print(len(q))
if q: print('not empty')

for i in range(n):
    a=q.popleft()
    print(a,end=' ')
print()
print(len(q))
if not q: print('empty')
1
2
3
4
5
6
7
8
9
10
11
12
13

例题

【题目描述】
根据输入的操作命令操作队列。
【输入描述】
第一行一个数字 N。 接下来 N 行，每行第一个数字为操作命令：1入队、2出队并输出、3计算队中元素个数并输出。1≤N≤50。
【输出描述】
若干行，每行显示一个 2 或 3 命令的输出结果。注意：2出队命令可能会出现空队出队（下溢），请输出“no”，并退出。

【输入样例】
7
1 19
1 56
2
3
2
3
2
【输出样例】
19
1
56
0
no

from queue import *
n=int(input())
q=Queue()

for i in range(n):
    s=list(map(int , input().split()))
    if(len(s)==2):
        q.put(s[1])
    elif(s[0]==2):
        if not q.empty():
            a=q.get()
            print(a)
        else:
            print('no')
            break;
    else:
        print(q.qsize())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

优先队列

一种特殊的队列：优先队列。
特点：最优数据（最大值或最小值）始终位于队列头部。
效率高：
新数据插入队列后，计算新的最优队头，计算复杂度是O(logn)；
弹出最优的队头后，计算新的最优队头，计算复杂度也是O(logn)

从堆顶弹出最小值
把新元素插入堆

弹出和插入的效率：O(logn)

【基本操作】

pq = queue.PriorityQueue() #定义
pq.put([priority, value]) #进队列
pq.get() #取出队首
pq.empty() #判断空
pq.qsize() #队列大小

put()的第一个参数priority表示数据的优先级，第二个参数value是值。
如果只有一个参数，同时表示优先级和值。值越小优先级越高，队首总是最小值。

import queue
pq = queue.PriorityQueue()
pq.put(1)       
pq.put(7)
pq.put(5)
print(pq.qsize())
while not pq.empty():  
   print(pq.get(),end='  ')
1
2
3
4
5
6
7
8

import queue
pq = queue.PriorityQueue()
pq.put([1, 'abc'])       
pq.put([7, 998])
pq.put([5, True])
print(pq.qsize())
while not pq.empty():  
   print(pq.get(),end='  ')
1
2
3
4
5
6
7
8

栈

LifoQueue实现

put() 进栈
get() 出栈并读取
qsize() 栈的大小

from queue import LifoQueue
st = LifoQueue(maxsize=100)
st.put('hello')
st.put('e')
st.put(1)
print(st.qsize())
print(st.get())   #弹出栈顶
1
2
3
4
5
6
7

list实现

append() 进栈
pop() 出栈并读取
len() 栈的大小

from queue import LifoQueue
st = []
st.append('hello')
st.append('e')
st.append(1)
print(len(st))
print(st[len(st)-1])   #输出栈顶
print(st.pop())
print(st.pop())
if st: print("Not Empty")
else: print("Empty")
1
2
3
4
5
6
7
8
9
10
11

用deque实现栈（和list用法一样）

append() 进栈
pop() 出栈并读取
len() 栈的大小

from queue import LifoQueue
st = deque()
st.append('hello')
st.append('e')
st.append(1)
print(len(st))
print(st[len(st)-1])   #输出栈顶
print(st.pop())
print(st.pop())
if st: print("Not Empty")
else: print("Empty")
1
2
3
4
5
6
7
8
9
10
11

二叉树

每个节点最多有两个子节点：左孩子、右孩子
以它们为根的子树称为左子树、右子树。
**二叉树的每个节点不必全有左、右孩子，可以只有一个孩子或没有孩子，没有孩子的结点称为叶子节点。
二叉树的第i层，最多有2^(i-1)个节点
有n个点的平衡二叉树，共有O(logn)层

2019年第十届省赛，lanqiaoOJ题号1 8 3

给定一棵包含N 个节点的完全二叉树，树上每个节点都有一个权值,按从上到下、从左到右的顺序依次是A1, A2, …, AN。现在小明要把相同深度的节点的权值加在一起,他想知道哪个深度的结点权值之和最大？如果有多个深度的权值和同为最大,请你输出其中最小的深度。注：根的深度是1。

import math
n = int(input())
c = int(math.log(n,2))+1 #一共有c层
a = [0]+list(map(int, input().split())) #a[1]~
a[n]
s = [0] * (c+1) #记录每层的和，s[1]~
s[c]
for i in range(1,c+1): #第1层到第c层
s[i] = sum(a[2**(i-1): 2**i-1 +1])#注意切片范围
print(s.index(max(s)))
1
2
3
4
5
6
7
8
9
10

我的比较粗糙的做法（因为一些函数不熟练导致写的很繁琐，还有二叉树的下标关系没有理清楚，层数对应的下标号）

import math
N=int(input())
a=[0]+list(map(int, input().split()))

deep=int(math.log(len(a)+1,2))   #总共的层数

s=[0]*(deep+1)

for i in range(1,deep+1):
    for j in range(2**(i-1), 2**i):
        s[i]+=a[j]
#print(s)
smax=s[0]
j=0
for i in range(deep+1):
    if(s[i]>smax):
        j=i
        smax=s[i]
print(j)  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二叉树的应用

例题：FBI树
l anqi a oOJ题号5 7 1

【题目描述】 我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含
“0”又含“1”的串则称为F串。FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一
个长度为2
N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
1．T的根结点为R，其类型与串S的类型相同；
2．若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，
由右子串S2构造R的右子树T2。
现在给定一个长度为2^N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。
【输入描述】 第一行是一个整数 N （0 ≤ N ≤ 10）。第二行是一个长度为 2
N的 “01” 串。
【输出描述】输出一个字符串，即 FBI 树的后序遍历序列。
【输入样例】
3
10001011
【输出样例】
IBFBBBFIBFIIIFF

n=int(input())
s=[0]+list(input())
print(s)
tree=['']*4400
def build(p,L,R):  #自底而上的建立树
    if L==R:
        if s[R]=='1':tree[p]='I'
        else:        tree[p]='B'
        return
    mid=(L+R)//2  #向下取整
    print(mid)
    build(2*p,L,mid)
    build(2*p+1, mid+1, R)
    if tree[2*p]=='B' and tree[2*p+1]=='B':tree[p]='B'
    elif tree[2*p]=='I' and tree[2*p+1]=='I':tree[p]='I'
    else: tree[p]='F'

def postorder(p):
    if tree[2*p]!='':  postorder(2*p)
    if tree[2*p+1]!='': postorder(2*p+1)
    print(tree[p],end='')
build(1,1,len(s)-1)
postorder(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23