首页 > 编程语言 >【PAT_Python解 AC满分代码】1105 链表合并

【PAT_Python解 AC满分代码】1105 链表合并

时间:2024-11-02 12:44:27浏览次数:5  
标签:AC PAT addr list len 链表 long result

原题链接:PTA | 程序设计类实验辅助教学平台

Tips:以下Python代码仅个人理解,非最优算法,仅供参考!多学习其他大佬的AC代码!

import sys

def main():
    # 读取链表头和节点数
    h1, h2, n = map(int, sys.stdin.readline().split())
    e = [0] * 100010  # 存储数据
    ne = [-1] * 100010  # 存储下一个地址

    for _ in range(n):
        addr, data, next_addr = map(int, sys.stdin.readline().split())
        e[addr] = data
        ne[addr] = next_addr

    L1 = []
    L2 = []

    # 构建链表L1
    p = h1
    while p != -1:
        L1.append(p)
        p = ne[p]

    # 构建链表L2
    p = h2
    while p != -1:
        L2.append(p)
        p = ne[p]

    # 确保L1是长链表
    if len(L2) > len(L1):
        L1, L2 = L2, L1

    # 反转短链表L2
    L2.reverse()
    
    # 合并链表
    L = []
    j = 0
    for i in range(len(L1)):
        L.append(L1[i])
        if (i + 1) % 2 == 0 and j < len(L2):
            L.append(L2[j])
            j += 1

    # 输出结果
    for i in range(len(L)):
        if i < len(L) - 1:
            print(f"{L[i]:05d} {e[L[i]]} {L[i + 1]:05d}")
        else:
            print(f"{L[i]:05d} {e[L[i]]} -1")

if __name__ == '__main__':
    main()


下面是测试点4,答案错误,但不超时(留着以后有空再回来继续想!),想了一会感觉没啥毛病,但问题肯定在合并链表的算法,数据量大的时候可能会漏,还是会错位啥的吧,不管了!上面AC代码直接拿列表装,也不用重新更新指定下一地址了!

import sys

# 定义链表节点的结构
class Node:
    def __init__(self, address, data, next_addr):
        self.address = address
        self.data = data
        self.next_addr = next_addr

# 解析输入
def read_input():
    head_l1, head_l2, n = sys.stdin.readline().split()
    n = int(n)
    nodes = {}
    
    for _ in range(n):
        address, data, next_addr = sys.stdin.readline().split()
        nodes[address] = Node(address, data, next_addr)
    
    return head_l1, head_l2, nodes

# 构建链表并计算长度
def build_linked_list(head_addr, nodes):
    current_addr = head_addr
    linked_list = []
    
    while current_addr != '-1':
        node = nodes[current_addr]
        linked_list.append(node)
        current_addr = node.next_addr
    
    return linked_list

# 合并链表
def merge_linked_lists(long_list, short_list):
    result = []
    len_long = len(long_list)
    len_short = len(short_list)
    
    long_index = 0
    for i in range(len_short):
        # 添加长链表的节点
        result.append(long_list[long_index])
        long_index += 1
        
        if long_index < len_long:
            result.append(long_list[long_index])
            long_index += 1
        
        # 添加短链表的节点
        result.append(short_list[i])
    
    # 将剩余的长链表节点添加到结果中
    result.extend(long_list[long_index:])

    # 更新所有节点的下一个地址
    for k in range(len(result) - 1):
        result[k].next_addr = result[k + 1].address
    # 最后一个节点的 next_addr 指向 -1
    result[-1].next_addr = '-1'
    
    return result

# 输出结果
def output_result(merged_list):
    for node in merged_list:
        sys.stdout.write(f'{node.address} {node.data} {node.next_addr}\n')

# 主函数
def main():
    head_l1, head_l2, nodes = read_input()
    
    # 创建两个链表
    list1 = build_linked_list(head_l1, nodes)
    list2 = build_linked_list(head_l2, nodes)
    len_list1 = len(list1)
    len_list2 = len(list2)
    
    if len_list1 >= 2 * len_list2:
        # list1 是长链表,list2 是短链表
        short_list = list2[::-1]  # 逆序短链表
        long_list = list1
    else:
        # list2 是长链表,list1 是短链表
        short_list = list1[::-1]  # 逆序短链表
        long_list = list2

    # 合并链表
    merged_list = merge_linked_lists(long_list, short_list)
    
    # 打印结果
    output_result(merged_list)

# 调用主函数
if __name__ == '__main__':
    main()

标签:AC,PAT,addr,list,len,链表,long,result
From: https://blog.csdn.net/m0_56677113/article/details/142916032

相关文章

  • 关于Copilot出现:You don`t have access to Github Copilot .....的问题解决方案
    前面如何如何配置,以及如何如何上传学生证资料等我这里不赘述badendinghappyending出现这个界面这个问题就是set_up不是很完全,设置一下就行disable改为enable等这样再回去IDE,就可以正常使用了......
  • 代码随想录一刷Day6--链表day1
    1.增加虚拟头节点,使头节点的移除跟别的移除统一(否则头节点需要让head指针往后移)2.删除节点的话,注意delete203.移除链表元素对链表的操作有点不熟悉ListNode*DummyHead=newListNode(0,head);  使用new进行虚拟头节点的创建删除tmp删除分支时,不用让cur=cur-》next 70......
  • 【backdoor attack】 POISONED FORGERY FACE: TOWARDS BACKDOOR ATTACKS ON FACE FORG
    一、研究动机​ 虽然目前在图像识别任务中有许多有效后门攻击方法,直接扩展到人脸伪造检测领域却存在着一定的问题,例如存在一些伪造人脸检测的算法(SBI,FaceX-ray)是通过真实图像合并转换为负样本进行模型训练的,这种情况下会导致:Backdoorlabelconflict[!NOTE]存在原因:对真实......
  • Apple Safari 18 - macOS 专属浏览器 (独立安装包下载)
    AppleSafari18-macOS专属浏览器(独立安装包下载)适用于macOSSonoma和macOSVentura的Safari浏览器18请访问原文链接:https://sysin.org/blog/apple-safari-18/查看最新版。原创作品,转载请保留出处。作者主页:sysin.org之前Safari浏览器伴随macOS更新一起发......
  • C. DS循环链表—约瑟夫环 (Ver. I - B)
    题目描述N个人坐成一个圆环(编号为1-N),从第S个人开始报数,数到K的人出列,后面的人重新从1开始报数。问最后剩下的人的编号。例如:N=3,K=2,S=1。2号先出列,然后是1号,最后剩下的是3号。测试数据有多组,每组包括3个数N、K、S,表示有N个人,从编号为S的人开始,数到K出列。输入测......
  • 链表和数组的插入删除时间复杂度都是o(n),为什么说链表效率高
    链表和数组的插入删除时间复杂度都是o(n),链表效率高的原因:1.动态内存分配;2.插入和删除操作的局部性;3.避免数组的扩容和复制;4.无需移动大量数据;5.适用于频繁的随机插入和删除;6.简化数据结构维护。链表的节点可以在运行时动态分配内存,而数组在创建时需要分配固定大小的内存。......
  • UEFI 笔记 001 —— 什么是 ACPI method
    声明:个人笔记,概不负责所谓ACPImethod本质上就是Callback是在OS主导下,OS发起的,对SystemFirmware的调用。类似在Windows上用C编写Win32应用,需要实现一堆OS要求的Callback函数。ACPImethod的提供者,事实上在实现OS要求的Callback所不同的是,OS调用C应......
  • [ACTF2020 新生赛]Include
    链接:https://buuoj.cn/challenges#[ACTF2020新生赛]Include。打开环境后如下,只有一个"tips"的超链接。访问tips,留意传入了"file"参数。接下来,可以尝试下路径穿越:?file=flag.php../../../../../etc/passwd。可以看到,存在路径穿越漏洞,但是通过路径穿越漏洞并没有读取到......
  • [ACTF2020 新生赛]Exec
    题目链接:https://buuoj.cn/challenges#[ACTF2020新生赛]Exec。打开后,环境如下。尝试输入"127.0.0.1",抓取请求包。POST/HTTP/1.1Host:038dc28f-5191-4958-8946-1127f62ad770.node5.buuoj.cn:81Content-Length:16Cache-Control:max-age=0Upgrade-Insecure-Requests:......
  • 全栈(full stack)是什么意思
    全栈(FullStack)指的是一种技能集合和开发理念,涵盖软件开发的各个层面,从前端用户界面到后端服务器端、数据库和服务器管理等多个领域。全栈开发者具备跨越整个技术堆栈的能力,能够综合处理应用程序开发的各个方面,从而构建完整、高效且稳定的应用系统。1.全栈开发的涵盖范围全栈......