[swift] LeetCode 23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input: [ 1->4->5,   1->3->4,   2->6 ]
Output: 1->1->2->3->4->4->5->6

 

[swift] LeetCode 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

 

[swift] LeetCode 20. Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

 

L2-022 重排链表-PAT团体程序设计天梯赛GPLT

给定一个单链表 L~1~→L~2~→…→L~n-1~→L~n~,请编写程序将链表重新排列为 L~n~→L~1~→L~n-1~→L~2~→…。例如:给定L为1→2→3→4→5→6,则输出应该为6→1→5→2→4→3。

输入格式:

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数,即正整数N (<= 10^5^)。结点的地址是5位非负整数,NULL地址用-1表示。

接下来有N行,每行格式为:

Address Data Next

其中Address是结点地址;Data是该结点保存的数据,为不超过10^5^的正整数;Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式:

对每个测试用例,顺序输出重排后的结果链表,其上每个结点占一行,格式与输入相同。

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

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

分析:用结构体{id, data, next}存储节点信息,模拟链表。先遍历一遍链表,把有用数节点存起来(甲级乙级中,姥姥为了加大难度,加了好多不在链表中的干扰数据)然后从后往前交替输出,(先把顺序存在ans中,待会统一输出),l, r代表将要输出的节点位置,当(l-1)-(r+1) == 1时都遍历一遍了,可退出循环~

 

L2-027 名人堂与代金券-PAT团体程序设计天梯赛GPLT

对于在中国大学MOOC学习“数据结构”课程的学生,想要获得一张合格证书,总评成绩必须达到 60 分及以上,并且有另加福利:总评分在 [G, 100] 区间内者,可以得到 50 元 PAT 代金券;在 [60, G) 区间内者,可以得到 20 元PAT代金券。全国考点通用,一年有效。同时任课老师还会把总评成绩前 K 名的学生列入课程“名人堂”。本题就请你编写程序,帮助老师列出名人堂的学生,并统计一共发出了面值多少元的 PAT 代金券。

输入格式:
输入在第一行给出 3 个整数,分别是 N(不超过 10 000 的正整数,为学生总数)、G(在 (60,100) 区间内的整数,为题面中描述的代金券等级分界线)、K(不超过 100 且不超过 N 的正整数,为进入名人堂的最低名次)。接下来 N 行,每行给出一位学生的账号(长度不超过15位、不带空格的字符串)和总评成绩(区间 [0, 100] 内的整数),其间以空格分隔。题目保证没有重复的账号。

输出格式:
首先在一行中输出发出的 PAT 代金券的总面值。然后按总评成绩非升序输出进入名人堂的学生的名次、账号和成绩,其间以 1 个空格分隔。需要注意的是:成绩相同的学生享有并列的排名,排名并列时,按账号的字母序升序输出。

输入样例:
10 80 5
cy@zju.edu.cn 78
cy@pat-edu.com 87
1001@qq.com 65
uh-oh@163.com 96
test@126.com 39
anyone@qq.com 87
zoe@mit.edu 80
jack@ucla.edu 88
bob@cmu.edu 80
ken@163.com 70

输出样例:
360
1 uh-oh@163.com 96
2 jack@ucla.edu 88
3 anyone@qq.com 87
3 cy@pat-edu.com 87
5 bob@cmu.edu 80
5 zoe@mit.edu 80

分析:给每个大于60分的学生发20块,如果还有人同时大于G,在发30块。把所有学生生排序后,重新排名。第一个学生为第一名,以后的学生如果分数和前一个学生并列,他的名次和前一个同学名次一样,否则他的名次为下标加一

 

L2-026 小字辈-PAT团体程序设计天梯赛GPLT

本题给定一个庞大家族的家谱,要请你给出最小一辈的名单。

输入格式:
输入在第一行给出家族人口总数 N(不超过 100 000 的正整数) —— 简单起见,我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号,其中第 i 个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为 -1。一行中的数字间以空格分隔。

输出格式:
首先输出最小的辈分(老祖宗的辈分为 1,以下逐级递增)。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔,行首尾不得有多余空格。

输入样例:
9
2 6 5 5 -1 5 6 4 7

输出样例:
4
1 9

分析:广度优先搜索最长路径问题(深搜可能会超时),老祖宗的父母即root的id用0表示 ,队列中的结构体成员分别是,人的编号和所处层数。