---------0702读了4篇论文~现在做一下算法题,然后去干饭!!!
注意删除头结点时,h已经指向第一个节点了,只需要将h赋值为ne[h](第二个节点即可)
m = int(input())
N = 100010
idx,h=1,-1
e,ne = [0]*N, [0]*N
def insert_h(x):
global h,idx
e[idx] = x
ne[idx] = h
h = idx
idx += 1
def rem(k):
global h
if k==0:
# h已经指向下一个了,所以擅长出的时候直接赋值ne[h]即可
h = ne[h]
else:
ne[k] = ne[ne[k]]
def insert(k,x):
global idx
e[idx] = x
ne[idx] = ne[k]
ne[k] = idx
idx += 1
for _ in range(m):
op, *pt = input().split()
if op=='H':
x = int(pt[0])
insert_h(x)
elif op=='D':
k = int(pt[0])
rem(k)
else:
k,x = map(int, pt)
insert(k, x)
while h!=-1:
print(e[h], end=' ')
h = ne[h]
问题非常多,需要加练!
1、idx是从2开始,所以第k个数的idx是k+1
2、insert时赋值的顺序要明确,不要忘记写,确保有4个线
3、rem时明确赋值对象是谁,脑子里要有图。
m = int(input())
N = 100010
h,t = 0,1
e,l,r =[0]*N,[0]*N,[0]*N
# idx从k开始,所以第k个数是k+1
idx = 2
# 初始化
r[h] = 1
l[t] = 0
def insert(k,x):
# 从第k个数的右侧插入一个数x
global idx
e[idx] = x
r[idx] = r[k]
# 没有写l[idx]
l[idx] = k
l[r[k]] = idx
# 是r[k],而不是k
r[k] = idx
idx += 1
def rem(k):
# 写反了
# r[k] = r[l[k]]
# l[k] = l[r[k]]
l[r[k]] = l[k]
r[l[k]] = r[k]
for _ in range(m):
op, *pt = input().split()
if op=='L':
x = int(pt[0])
insert(0,x)
elif op=='R':
x = int(pt[0])
insert(l[1],x)
elif op=='D':
k = int(pt[0])+1
rem(k)
elif op=='IL':
k,x = map(int, pt)
insert(l[k+1], x)
else:
k,x = map(int,pt)
insert(k+1, x)
h = r[h]
while h!=1:
print(e[h], end=' ')
h = r[h]
模拟栈做的很顺畅!!!但需要注意以下问题:
1、tt从0开始;是否为空,用tt>0判断,>0是不为空
;push元素时,tt先+1
2、试了一下,把global tt在所有函数外声明还是不管用,需要在函数内进行global声明。【有时间应该去弄清楚python的变量定义域机制是怎么work的】
m = int(input())
N = 100010
stk = [0]*N
tt = 0
def push(x):
global tt
tt += 1
stk[tt] = x
def pop():
global tt
tt -= 1
def empty():
global tt
if tt>0:
return False
else:
return True
def query():
global tt
return stk[tt]
for _ in range(m):
op, *pt = input().split()
if op=='push':
x = int(pt[0])
push(x)
elif op=='pop':
pop()
elif op=='empty':
if empty():
print('YES')
else:
print('NO')
else:
print(query())
—0747今天已经在算法上用了40~50分钟(没错,45min)了,就不学新的了。明天继续复习一下双链表(今天做的不好),再写一道新题。吃早饭去啦!!!
----2007跑完步,洗完澡,边吃豆干边写总结。打算一会看会图论。