欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1025 反转链表 (25分)

程序员文章站 2022-06-07 14:15:02
...

1025 反转链表 (25分)

输入样例:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

解题心得:

  1. 本题两个注意点,1⃣️不是所有结点都是在链表上;2⃣️反转后链表中每个结点的next仍指向反转后的下一个结点,一定要审题!
  2. 第5个测试点超时,python本身的效率是一方面,代码可能还有优化的空间,但是没有必要,既然选择使用python说明对效率要求不是特别高,也可以把python代码过分优化,就失去了代码的优雅性。针对pat的题目而言,绝大部分用python没有问题,对于部分超时问题,请把python代码用c++或者c翻译一遍就没问题;
  3. 每次做pat提交错误时,都是无从下手->然大悟->原来如此->如此简单。
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict


def get_k_reverse(first_addr, nodes, k):
    addr = first_addr
    sorted_nodes = []
    while addr != '-1':
        sorted_nodes.append(nodes[addr])
        addr = nodes[addr][2]
    # print('debug:', sorted_nodes)

    i = 0
    n = len(sorted_nodes)
    loops = n // k
    while i < loops:
        for j in reversed(range(i * k, (i + 1) * k)):
            print(' '.join(sorted_nodes[j][0:2]), end=' ')
            if j - 1 >= i * k:
                print(sorted_nodes[j - 1][0])
            elif i + 1 < loops:
                print(sorted_nodes[(i + 2) * k - 1][0])
            elif i + 1 == loops and (i + 1) * k < n:
                print(sorted_nodes[(i + 1) * k][0])
            else:
                print('-1')
        i += 1

    for j in range(i * k, n):
        print(' '.join(sorted_nodes[j][0:2]), end=' ')
        if j + 1 < n:
            print(sorted_nodes[j + 1][0])
        else:
            print('-1')


if __name__ == '__main__':
    first_addr, n, k = sys.stdin.readline().split()
    n = int(n)
    k = int(k)
    nodes = defaultdict(list)
    for i in range(n):
        node = sys.stdin.readline().split()
        nodes[node[0]] = node

    get_k_reverse(first_addr, nodes, k)

相关标签: 算法修养