用python来解PAT乙级1075链表元素分类-25-20分 (有注释)最后一个超时
本题看似繁琐,其实只需要分为两个步骤来做
首先按照给定的首个结点坐标和输入的多组数据,来将单链表的顺序给排出来
然后根据题意 按照每个结点位置的数值来将单链表分成三个部分:小于0,大于0小于K,大于K
最后输出就ok
代码如下:
import sys first , n , k = input().split() n = int(n) k = int(k) addr_data = dict() addr_next = dict() data_shuchu = dict() data_print = dict()#这两个是为了方便输出 addr_sort = [] for h in range(n):#接收输入数据,保存到字典里,方便输出 addr , data , next = sys.stdin.readline().split() addr_data[addr] = data addr_next[addr] = next data_shuchu[int(data)] = f'{addr} {data}' data_print[int(data)] = addr while first != '-1':#单链表排序(正序) addr_sort.append(first)#得到单链表次序的结点坐标列表 first = addr_next[first] data_sort = [int(addr_data[i]) for i in addr_sort]#得到单链表次序的数值列表 res = [] #分三个循环按照数值大小分成三块 for i in data_sort: if i<0: res.append(i)#负数 for j in data_sort: if 0<=j<=k: res.append(j)#小于K值的 for h in data_sort: if h>k: res.append(h)#大于K值的 for v in range(len(res)-1): sys.stdout.write(f'{data_shuchu.get(res[v])} {data_print.get(res[v+1])}\n') sys.stdout.write(f'{data_shuchu.get(res[-1])} -1\n')
因为怕超时,所以用了sys模块的stdin和stdout的输入输出方式提高效率,虽然最后还是超时了。。。
对于创建字典和列表一类的,千万不要怕麻烦,创建的越多中间的过程会越简单,只是你要记得各种名称,别把自己给弄晕了就成。。。
下面是提交结果: