HelloWorld 开发者社区

科技资讯

全部资讯

开源项目

全部项目

推荐好文

PAT_甲级_1151 LCA in a Binary Tree

题目大意:给定一颗含有N个节点的前序和中序序列,要求给定任意2个节点,需要输出其最近公共祖先。算法思路:这里和1143一样给出2种思路,一种不用建树,一种需要建树。算法思路1(不用建树):我们借鉴建树的递归过程完成树的部分搜索,如果当前搜

PAT_甲级_1148 Werewolf - Simple Version

题目大意:已知N名玩家中有2人扮演狼人角色,有2人说的不是实话,有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家,如果有解,在一行中按递增顺序输出2个狼人的编号;如果解不唯一,则输出最小序列解;若无解则输出NoSolution.

PAT_甲级_1150 Travelling Salesman Problem

题目大意:给定一个N个顶点和M条边的无向图,K个查询,每一个查询输入长度为n的路径,判断该路径是否是TScycle或者TSsimplecycle并输出题目要求的对应信息。算法思路:我们使用邻接矩阵G保存该图的边权,然后使用path数组保存每一次查询的路径,

PAT_甲级_1149 Dangerous Goods Packaging

题目大意:现有N对互不兼容的物品清单和M个需要装箱的货物清单,询问每一个需要装箱的货物清单是否可以完全兼容并装箱,如果可以输出Yes,否则输出No。算法思路:首先使用$incompatible$二维数组存储每一个物体的所有不兼容的物体,并使用$incompat$

PAT_甲级_1147 Heaps

题目大意:现有M个查询,每一个查询给定一个长度为N的完全二叉树层序序列,判断该二叉树是大根堆,小根堆和非堆,然后输出该完全二叉树的后序遍历序列。算法思路:对于完全二叉树可以使用一个数组来保存其层序序列,然后使用函数isMaxHeap和isMinHeap分别判断该

PAT_甲级_1146 Topological Order

题目大意:给定一个有向图,N个顶点,M条边,现给定K个查询,每一个查询输入一个序列,判断该序列是否是该图的拓扑排序序列,如果不是,输出该序列的编号(从0开始)算法思路:模拟拓扑排序的过程,对于输入的序列,先检查其入度是否为0,不为0说明该序列不是拓扑排序序列,否

PAT_甲级_1145 Hashing - Average Search Time

题目大意:给定N个数字插入到用户指定长度为MSize的hash表中,如果X无法插入就输出Xcannotbeinserted.紧接着给出M个查询的数字,计算平均M个数字的查找时间。算法思路:首先对于输入的hash表长度MSize得判断是否为素数,如果不是,需

PAT_甲级_1144 The Missing Number

题目大意:给定一个长度为N的序列,需要输出该序列中最小的没有出现的正整数算法思路:使用map记录所有输入的正数,然后从1开始一直向后查找map中没有出现的正数,然后输出退出循环即可。注意点:1、如果是使用hash数组来记录每一个出现的

PAT_甲级_1143 Lowest Common Ancestor

题目大意:给定一颗二叉排序树的先序序列,输出待查询的两个节点的最近公共祖先。算法思路1(不建树):使用$pre$存放输入的先序序列,$isLegal$标记每一个树中的节点,对于输入的节点只要小于0或者$isLegal$对应值为false,就说明不在树中,输出对

正在加载更多文章…

加载更多

已加载文章中没有匹配内容,可继续加载更多。