• D2-读论文D2&算法题D2(复习:单链表、双链表、模拟栈)


    ---------0702读了4篇论文~现在做一下算法题,然后去干饭!!!

    826单链表(复习)

    注意删除头结点时,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
    • 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
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    827双链表(复习)

    问题非常多,需要加练!
    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
    • 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
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    828模拟栈(复习)

    模拟栈做的很顺畅!!!但需要注意以下问题:
    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())
    
    • 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
    • 35
    • 36
    • 37
    • 38
    • 39

    —0747今天已经在算法上用了40~50分钟(没错,45min)了,就不学新的了。明天继续复习一下双链表(今天做的不好),再写一道新题。吃早饭去啦!!!

    ----2007跑完步,洗完澡,边吃豆干边写总结。打算一会看会图论。

  • 相关阅读:
    A. 2-3 Moves
    【MySQL】MySQL 服务无法启动。服务没有报告任何错误。请键入 NET HELPMSG 3534 以获得更多的帮助。
    博图Modbus组态及参数设定源码
    《七月集训》第一日——数组
    js中的i++和++i
    问题解决系列:从源码讲解为什么是 ‘JZ0SL_ Unsupported SQL type 1111‘
    词!自然语言处理之词全解和Python实战!
    心情不好就狂吃?好心情心理:这是病,得治!
    【中国知名企业高管团队】系列25:360
    【已解决】MySQL:执行sql查询出错误数据(MySQL隐藏机制-类型转换导致)
  • 原文地址:https://blog.csdn.net/weixin_45252975/article/details/125592555