这几天看论文，代码又搁置了，估计有些块注定是红色的了呜呜呜~
话不多说，开始复习叭~
刚好一题不空，开心！！！
要好好努力学习，才不辜负自己老师和家人呀~
一、785
很多错误，基本上都忘了。
1、终止条件
2、j为r+1，r应该为index
3、交换值的时候要先判断i<j
4、递归时注意括号里写的是什么
def quick_sort(q,l,r):
if l>=r:
return
i = l-1
j = r+1
x = q[l+r>>1]
while i<j:
i+=1
j-=1
while q[i]<x:
i+=1
while q[j]>x:
j-=1
if i<j:
q[i],q[j]=q[j],q[i]
quick_sort(q,l,j)
quick_sort(q,j+1,r)
n = int(input())
nums = list(map(int,input().split()))
quick_sort(nums,0,n-1)
print(' '.join(map(str,nums)))
二、786
1、函数有四个参数
2、递归带返回值的时候，每个递归函数都要写个return，不然传不回去。
def quick_sort(q,l,r,k):
if l>=r:
return q[l]
i,j = l-1,r+1
x = q[l+r>>1]
while i<j:
i+=1
j-=1
while q[i]<x:
i+=1
while q[j]>x:
j-=1
if i<j:
q[i],q[j]=q[j],q[i]
sl = j-l+1
if k<=sl:
return quick_sort(q,l,j,k)
else:
return quick_sort(q,j+1,r,k-sl)
n,k = map(int,input().split())
nums = list(map(int,input().split()))
print(quick_sort(nums,0,n-1,k))
三、787
1、是归并排序好的两段在比较，但是第一段是l:mid+1，第二段是mid+1:r+1
2\注意q[]中是：，而不是，
四、788
1、归并的时候，直接把一段拿过来的时候，要想好index。
五、789
比较顺利，但有些生疏。
六、790
问题不大，但是别忘了输出形式
print(’{:.6f}’.format(l))
print("{:.0f}".format(l))
七、795
1\nums读入的时候也要多一个，第一个是0
2、输出的时候是从右减左
⑧796
没啥问题
九、797
问题不大
就是别忘了用map转换成int类型
十、798
问题不大，除了函数参数丢了一个。
十一、800
没啥问题：先暴力，根据单调性做简化。
十二、801
比较强，居然还记得lowbit什么含义以及怎么写。
lowbit返回最后的一位1，可以用来判断1的个数。
n&-n
十三、802
1\二分写的有些问题
（1）>>1放在while里面
（2）大小比较写反了
alls[mid]>=x:
2、alls不用预先设置范围，直接append就ok了。
十四、803
1、sorted的用法，函数前要写key=&&&&前面要接nums，与nums。sort（）不同。
2、if res：如果res不为空才进去，不要写反了【第二次了哦】。
十五、799
要注意能不能进while循环呀。刚开始j=i=0，把while j<i写在外面，进不了循环呀~~~
——————————————————————————————新代码——————
一、828 单链表
1、k指的是下标为k
2、链表遍历。相当于先让head为-1，在后续操作中这个假想的-1一直在。
3、感觉很不熟练，需要多多练习！！！
m = int(input())
N = 100010
e,ne,idx,head = [0]*N,[0]*N,0,-1
# 将x插到头结点
def add_to_head(x):
# 用global将idx,head声明为全局变量
global idx,head
e[idx], ne[idx], head, idx = x, head, idx, idx+1
# 将下标是k的点后面的点删掉
def remove(k):
global idx
ne[k] = ne[ne[k]]
# 将x插到下标是k的点后面
def add(k,x):
global idx
e[idx], ne[idx],ne[k], idx = x, ne[k], idx, idx+1
for _ in range(m):
# 在变量前加*，则多余的函数参数会作为一个元组存在args中
op, *p = input().split()
if op =='H':
x=int(p[0])
add_to_head(x)
elif op=='I':
k,x = map(int,p)
add(k-1,x)
else:
k = int(p[0])
if k==0:
# 删除头结点接相当于让head直接指向第二个节点
head = ne[head]
else:
remove(k-1)
# 链表输出
while head!=-1:
print(e[head],end=' ')
head = ne[head]
二、827双链表
不是很熟悉，注释里的k+1的左侧不一定是k需要注意
m = int(input())
head,tail=0,1
N = 100010
e,l,r,idx = [0]*N, [0]*N, [0]*N,0
def init():
global idx
r[0] = 1
l[1] = 0
idx = 2
# 节点a的right插入一个数x
def add(a,x):
global idx
e[idx] = x
l[r[a]]= idx
l[idx] = a
r[idx] = r[a]
# 这步最后做
r[a] = idx
idx += 1
def remove(k):
r[l[k]] = r[k]
l[r[k]] = l[k]
init()
for _ in range(m):
op, *p = input().split()
if op=='L':
x = int(p[0])
add(0,x)
elif op=='R':
x = int(p[0])
add(l[1],x)
elif op =='D':
k = int(p[0])
# idx从2开始，所以第k个点应该是k+1,下同理
remove(k+1)
elif op=='IL':
k,x = map(int,p)
# 因为定义为从右侧插入，所以需要找到第k个（编号为k+1）左侧的变号，这个编号不一定是k，所以用l[k+1]表示。
add(l[k+1],x)
else:
k,x = map(int,p)
add(k+1,x)
i = r[0]
while i!=1:
print(e[i], end=' ')
i = r[i]
三、模拟栈828
最后只让查没让弹出哦query
m = int(input())
N = 100010
stk, tt = [0]*N,0
def push(x):
global stk,tt
tt += 1
stk[tt]=x
def pop():
global tt
tt -= 1
def empty():
global tt
if tt==0:
return 'YES'
return 'NO'
def query():
global stk,tt
return stk[tt]
for _ in range(m):
op,*p = input().split()
if op=='push':
x = int(p[0])
push(x)
elif op=='pop':
pop()
elif op=='empty':
print(empty())
else:
print(query())
四、模拟队列
m = int(input())
N = 100010
q, hh, tt = [0]*N, 0, -1
def push(x):
global q, hh, tt
tt +=1
q[tt]=x
def pop():
global hh
hh += 1
def empty():
global tt,hh
if hh<=tt:
return 'NO'
else:
return 'YES'
def query():
global q,hh
return q[hh]
for _ in range(m):
op, *p = input().split()
if op=='push':
x = int(p[0])
push(x)
elif op=='pop':
pop()
elif op=='empty':
print(empty())
else:
print(query())
五、830单调栈
n = int(input())
N = 10010
a = list(map(int,input().split()))
stk,tt=[0]*N,0
for i in range(n):
while tt and stk[tt]>=a[i]:
tt-=1
if tt:
print(stk[tt],end=' ')
else:
print('-1',end=' ')
tt += 1
stk[tt] = a[i]
先去做核酸啦~
跑了十公里，把今天的新题写完，就去写日记和周总结了~另外今天配速进6了！不错
六、154单调队列
有点难以理解，但是重要的是，要保证队列单调增或单调减，然后取第一个
n,k = map(int, input().split())
a = list(map(int,input().split()))
N = 1000010
q,hh,tt=[0]*N,0,-1
for i in range(n):
if hh<=tt and i-k+1>q[hh]:
hh += 1
while hh<=tt and a[q[tt]]>=a[i]:
tt-=1
tt += 1
q[tt] = i
if i-k+1>=0:
print(a[q[hh]], end=' ')
print()
q,hh,tt=[0]*N,0,-1
for i in range(n):
if hh<=tt and i-k+1>q[hh]:
hh+=1
while hh<=tt and a[q[tt]]<=a[i]:
tt-=1
tt+=1
q[tt] = i
if i-k+1>=0:
print(a[q[hh]], end=' ')
七、kmp831
很艰难，勉强理解，明日再战
N = 100010
n = int(input())
p = ' '+ input()
m = int(input())
s = ' '+ input()
ne =[0]*N
j=0
# 求next
for i in range(2,n+1):
while j and p[i]!=p[j+1]:
j = ne[j]
if p[i]==p[j+1]:
j+=1
ne[i] = j
j = 0
for i in range(1,m+1):
while j and s[i]!=p[j+1]:
j = ne[j]
if s[i]==p[j+1]:
j+=1
if j==n:
print(i-n,end=' ')
j = ne[j]
去写周总结啦~~~~~~~~~明日再战！