- 博客(52)
- 收藏
- 关注
RSS订阅原创 765. 情侣牵手-并查集
N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。人和座位用0到2N-1的整数表示，情侣们按顺序编号，第一对是(0, 1)，第二对是(2, 3)，以此类推，最后一对是(2N-2, 2N-1)。这些情侣的初始座位row[i]是由最初始坐在第 i 个座位上的人决定的。示例 1:输入: row = [0, 2, 1, 3]输出: 1解释: 我们只需要交换row[...
2020-07-04 00:31:38
228
原创 1068 Find More Coins (30分)-01背包 、动态规划（01背包问题还没搞明白，待更新）
Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for eac
2020-06-30 13:51:18
120
原创 1064 Complete Binary Search Tree (30分)-数组，中序遍历
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater th
2020-06-30 00:18:08
99
原创 1057 Stack (30分)-堆栈、二分排序
Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to im
2020-06-29 23:37:02
129
原创 1038 Recover the Smallest Number (30分)-数学分析
Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given { 32, 321, 3214, 0229, 87 }, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different ord
2020-06-29 00:25:15
69
原创 1049 Counting Ones (30分)-数学分析
The task is simple: given any positive integerN, you are supposed to count the total number of 1's in the decimal form of the integers from 1 toN. For example, givenNbeing 12, there are five 1's in 1, 10, 11, and 12.Input Specification:Each input f...
2020-06-28 23:26:14
183
原创 1045 Favorite Color Stripe (30分)-求最长公共子序列
Eva is trying to make her own color stripe out of a given one. She would like to keep only her favorite colors in her favorite order by cutting off those unwanted pieces and sewing the remaining parts together to form her favorite color stripe.It is said
2020-06-28 17:23:05
114
原创 1034 Head of a Gang (30分)-图的连通集，DFS，STL
One way that the police finds the head of a gang is to check people's phone calls. If there is a phone call betweenAandB, we say thatAandBis related. The weight of a relation is defined to be the total time length of all the phone calls made between...
2020-06-27 19:53:19
75
原创 1030 Travel Plan (30分)-DFS & dijkstra、最短路径
A traveler's map gives the distances between cities along the highways, together with the cost of each highway. Now you are supposed to write a program to help a traveler to decide the shortest path between his/her starting city and the destination. If suc
2020-06-27 15:51:21
130
原创 1026 Table Tennis (30分)-模拟队列、坑点分析
A table tennis club has N tables available to the public. The tables are numbered from 1 to N. For any pair of players, if there are some tables open when they arrive, they will be assigned to the available table with the smallest number. If all the tables
2020-06-26 23:43:14
607
原创 1022 Digital Library (30分)-STL大杂烩
A Digital Library contains millions of books, stored according to their titles, authors, key words of their abstracts, publishers, and published years. Each book is assigned an unique 7-digit number as its ID. Given any query from a reader, you are suppose
2020-06-25 01:17:36
92
原创 1018 Public Bike Management (30分)-DFS、最短路径
There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.The Public Bike Management Center (PBMC) keeps mo
2020-06-24 21:47:38
84
原创 1014 Waiting in Line (30分)-queue、坑点分析
Suppose a bank hasNwindows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:The space inside the yellow line in front of each window is enoug..
2020-06-24 16:31:32
435
1
原创 1004 Counting Leaves (30分)-map、vector
A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child.Input Specification:Each input file contains one test case. Each case starts with a line containing0<N<100, the number of nod.
2020-06-24 01:28:41
65
原创 1107 Social Clusters (30分)-并查集
1107Social Clusters(30分)When register on a social network, you are always asked to specify your hobbies in order to find some potential friends with the same hobbies. Asocial clusteris a set of people who have some of their hobbies in common. You are...
2020-06-24 00:04:20
137
原创 1131 Subway Map (30分)-DFS，最短路径（待更新）
In the big cities, the subway systems always look so complex to the visitors. To give you some sense, the following figure shows the map of Beijing subway. Now you are supposed to help people with your computer skills! Given the starting position of your u
2020-06-23 19:39:33
108
原创 1115 Counting Nodes in a BST (30分)-BST插入、求高、遍历
A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:The left subtree of a node contains only nodes with keys less than or equal to the node's key. The right subtree of a node contains only nodes with key
2020-06-23 00:07:24
51
原创 1119 Pre- and Post-order Traversals (30分)-前序后序重构树，唯一性判定
Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences, or preorder and inorder traversal sequences. However, if only the postorder and
2020-06-22 22:54:30
172
原创 1127 ZigZagging on a Tree (30分)-zigzagging order, double stack
Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However
2020-06-22 21:12:49
182
原创 1143 Lowest Common Ancestor (30分)-前序和中序重构二叉树、LCA
The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.A binary search tree (BST) is recursively defined as a binary tree which has the following properties:The left subtree of a node co
2020-06-21 13:01:25
95
原创 1151 LCA in a Binary Tree (30分)-前序中序重构数、LCA
The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants.Given any two nodes in a binary tree, you are supposed to find their LCA.Input Specification:Each input file contains one test ca
2020-06-21 12:41:45
91
原创 1147 Heaps (30分)-Heap、数组
In computer science, aheapis a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) t..
2020-06-20 14:43:44
87
原创 1155 Heap Paths (30分)-Heap、数组
In computer science, aheapis a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) t..
2020-06-20 13:48:53
73
原创 7-27 家谱处理 (30分)-树的数组实现
人类学研究对于家族很感兴趣，于是研究人员搜集了一些家族的家谱进行研究。实验中，使用计算机处理家谱。为了实现这个目的，研究人员将家谱转换为文本文件。下面为家谱文本文件的实例：John Robert Frank Andrew Nancy David家谱文本文件中，每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代，而他们的丈夫或妻子不出现在家谱中。每个人的子女比父母多缩进2个空格。以上述家谱文本文件为例，John这个家族最早的祖先，他
2020-06-18 23:01:02
362
原创 7-46 新浪微博热门话题 (30分)-STL+字符串处理
新浪微博可以在发言中嵌入“话题”，即将发言中的话题文字写在一对“#”之间，就可以生成话题链接，点击链接可以看到有多少人在跟自己讨论相同或者相似的话题。新浪微博还会随时更新热门话题列表，并将最热门的话题放在醒目的位置推荐大家关注。本题目要求实现一个简化的热门话题推荐功能，从大量英文（因为中文分词处理比较麻烦）微博中解析出话题，找出被最多条微博提到的话题。输入格式:输入说明：输入首先给出一个正整数N（≤105），随后N行，每行给出一条英文微博，其长度不超过140个字符。任何包含在一对最近的#中
2020-06-18 19:48:14
278
原创 7-39 魔法优惠券 (25分)-priority_queue
在火星上有个魔法商店，提供魔法优惠券。每个优惠劵上印有一个整数面值K，表示若你在购买某商品时使用这张优惠劵，可以得到K倍该商品价值的回报！该商店还免费赠送一些有价值的商品，但是如果你在领取免费赠品的时候使用面值为正的优惠劵，则必须倒贴给商店K倍该商品价值的金额…… 但是不要紧，还有面值为负的优惠劵可以用！（真是神奇的火星）例如，给定一组优惠劵，面值分别为1、2、4、-1；对应一组商品，价值为火星币M$7、6、-2、-3，其中负的价值表示该商品是免费赠品。我们可以将优惠劵3用在商品1上，得到M$28的回报
2020-06-18 15:43:57
226
原创 7-12 排序 (25分)(冒泡、希尔、堆、归并排序对比）
给定N个（长整型范围内的）整数，要求输出从小到大排序后的结果。本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下：数据1：只有1个元素； 数据2：11个不相同的整数，测试基本正确性； 数据3：103个随机整数； 数据4：104个随机整数； 数据5：105个随机整数； 数据6：105个顺序整数； 数据7：105个逆序整数； 数据8：105个基本有序的整数； 数据9：105个随机正整数，每个数字不超过1000。 输入格式: 输入第一行给出正整数N（≤105
2020-06-18 14:39:47
228
原创 7-49 打印学生选课清单 (25分)-map+priority_queue
假设全校有最多40000名学生和最多2500门课程。现给出每门课的选课学生名单，要求输出每个前来查询的学生的选课清单。输入格式:输入的第一行是两个正整数：N（≤40000），为前来查询课表的学生总数；K（≤2500），为总课程数。此后顺序给出课程1到K的选课学生名单。格式为：对每一门课，首先在一行中输出课程编号（简单起见，课程从1到K编号）和选课学生总数（之间用空格分隔），之后在第二行给出学生名单，相邻两个学生名字用1个空格分隔。学生姓名由3个大写英文字母+1位数字组成。选课信息之后，在一行内给出了
2020-06-18 12:06:06
315
原创 7-48 银行排队问题之单窗口“夹塞”版 (30分)-map+优先队列
排队“夹塞”是引起大家强烈不满的行为，但是这种现象时常存在。在银行的单窗口排队问题中，假设银行只有1个窗口提供服务，所有顾客按到达时间排成一条长龙。当窗口空闲时，下一位顾客即去该窗口处理事务。此时如果已知第i位顾客与排在后面的第j位顾客是好朋友，并且愿意替朋友办理事务的话，那么第i位顾客的事务处理时间就是自己的事务加朋友的事务所耗时间的总和。在这种情况下，顾客的等待时间就可能被影响。假设所有人到达银行时，若没有空窗口，都会请求排在最前面的朋友帮忙（包括正在窗口接受服务的朋友）；当有不止一位朋友请求某位顾客帮
2020-06-18 01:02:35
655
原创 7-29 修理牧场 (25分)-优先队列+贪心算法
农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（
2020-06-17 17:46:29
599
原创 7-26 Windows消息队列 (25分)-优先队列
消息队列是Windows系统的基础。对于每个进程，系统维护一个消息队列。如果在进程中有特定事件发生，如点击鼠标、文字改变等，系统将把这个消息加到队列当中。同时，如果队列不是空的，这一进程循环地从队列中按照优先级获取消息。请注意优先级值低意味着优先级高。请编辑程序模拟消息队列，将消息加到队列中以及从队列中获取消息。输入格式:输入首先给出正整数N（≤105），随后N行，每行给出一个指令——GET或PUT，分别表示从队列中取出消息或将消息添加到队列中。如果指令是PUT，后面就有一个消息名称、以及一个
2020-06-17 17:02:17
187
原创 7-25 朋友圈 (25分)-通过并查集实现
某学校有N个学生，形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果A和B是朋友，且B和C是朋友，则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。输入格式:输入的第一行包含两个正整数N（≤30000）和M（≤1000），分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出1个俱乐部的信息，其中学生从1~N编号：第i个俱乐部的人数Mi（空格）学生1（空格）学生
2020-06-17 12:19:47
386
原创 7-14 电话聊天狂人 (25分)-map
给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。输入格式:输入首先给出正整数N（≤105），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。输出格式:在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。输入样例:413005711862 1358862583213505711862 130886
2020-06-17 11:11:03
154
原创 7-15 QQ帐户的申请与登陆 (25分)-map
实现QQ新帐户申请和老帐户登陆的简化版功能。最大挑战是：据说现在的QQ号码已经有10位数了。输入格式:输入首先给出一个正整数N（≤105），随后给出N行指令。每行指令的格式为：“命令符（空格）QQ号码（空格）密码”。其中命令符为“N”（代表New）时表示要新申请一个QQ号，后面是新帐户的号码和密码；命令符为“L”（代表Login）时表示是老帐户登陆，后面是登陆信息。QQ号码为一个不超过10位、但大于1000（据说QQ老总的号码是1001）的整数。密码为不小于6位、不超过16位、且不包含空格的字
2020-06-17 10:41:09
125
原创 7-45 航空公司VIP客户查询 (25分)-map
不少航空公司都会提供优惠的会员服务，当某顾客飞行里程累积达到一定数量后，可以使用里程积分直接兑换奖励机票或奖励升舱等服务。现给定某航空公司全体会员的飞行记录，要求实现根据身份证号码快速查询会员里程积分的功能。输入格式:输入首先给出两个正整数N（≤105）和K（≤500）。其中K是最低里程，即为照顾乘坐短程航班的会员,航空公司还会将航程低于K公里的航班也按K公里累积。随后N行，每行给出一条飞行记录。飞行记录的输入格式为：18位身份证号码（空格）飞行里程。其中身份证号码由17位数字加最后一位校验码
2020-06-17 00:09:47
534
原创 7-44 基于词频的文件相似度 (30分)-set
实现一种简单原始的文件相似度计算，即以两文件的公共词汇占总词汇的比例来定义相似度。为简化问题，这里不考虑中文（因为分词太难了），只考虑长度不小于3、且不超过10的英文单词，长度超过10的只考虑前10个字母。输入格式:输入首先给出正整数N（≤100），为文件总数。随后按以下格式给出每个文件的内容：首先给出文件正文，最后在一行中只给出一个字符#，表示文件结束。在N个文件内容结束之后，给出查询总数M（≤104），随后M行，每行给出一对文件编号，其间以空格分隔。这里假设文件按给出的顺序从1到N编号。
2020-06-16 22:08:19
562
原创 7-24 树种统计 (25分)-map
随着卫星成像技术的应用，自然资源研究机构可以识别每一棵树的种类。请编写程序帮助研究人员统计每种树的数量，计算每种树占总数的百分比。输入格式:输入首先给出正整数N（≤105），随后N行，每行给出卫星观测到的一棵树的种类名称。种类名称由不超过30个英文字母和空格组成（大小写不区分）。输出格式:按字典序递增输出各种树的种类名称及其所占总数的百分比，其间以空格分隔，保留小数点后4位。输入样例:29Red AlderAshAspenBasswoodAshBeechYell
2020-06-12 01:16:12
190
原创 7-22 堆栈模拟队列 (25分)-堆栈
设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数:int IsFull(Stack S)：判断堆栈S是否已满，返回1或0； int IsEmpty (Stack S )：判断堆栈S是否为空，返回1或0； void Push(Stack S, ElementType item )：将元素item压入堆栈S； ElementType Pop(Stack S )：删除并返回S的栈顶元素。实现队列的操作，即入队void AddQ(E
2020-06-08 21:55:03
511
原创 7-17 汉诺塔的非递归实现 (25分)（含递归代码）
借助堆栈以非递归（循环）方式求解汉诺塔的问题（n, a, b, c），即将N个盘子从起始柱（标记为“a”）通过借助柱（标记为“b”）移动到目标柱（标记为“c”），并保证每个移动符合汉诺塔问题的要求。输入格式:输入为一个正整数N，即起始柱上的盘数。输出格式:每个操作（移动）占一行，按柱1 -> 柱2的格式输出。输入样例:3输出样例:a -> ca -> bc -> ba -> cb -> ab -> ca ->
2020-06-08 13:39:54
1629
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人