未知的世界

未知的世界

马上订阅 未知的世界 RSS 更新: http://lulalap.com/atom.xml

PAT A1133 Splitting A Linked List(C++)

2018年12月3日 18:37
PAT甲级目录 | PAT乙级目录

题目描述

原题地址：A1133 Splitting A Linked List
中文版：B1075 链表元素分类

解题思路

将链表存放到数组中，遍历链表，将对应范围的值加入不同的可变数组中，最后合并数组，顺序输出。

易错点

  • 最后一个结点的 next 地址应当输出 -1
  • 地址的格式为五位数

也许陌生的知识点

  • vector<int> ans;
    • 实现变长数组，元素类型可任意指定
      • ans.push_back(num[i])往变长数组末尾中添加一个元素
      • ans.pop_back()删除变长数组中最后一个元素
    • 需要的头文件：vector

代码示例：

  • 方法一：利用数组存放链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <vector>
using namespace std;
int main() {
  int A[100010], D[100010], n, k, pos, now, next, temp;
  vector<int> first, second, last;
  scanf("%d %d %d", &pos, &n, &k);
  for(int i = 0; i < n; i++){
    scanf("%d %d %d",&now, &temp, &next);
    A[now] = next;
    D[now] = temp;
  }
  while(pos != -1){ // 遍历链表
    if(D[pos] < 0) first.push_back(pos);
    else if(D[pos] > k) last.push_back(pos);
    else second.push_back(pos);
    pos = A[pos];
  }
  for(int i = 0; i < second.size(); i++) first.push_back(second[i]);
  for(int i = 0; i < last.size(); i++) first.push_back(last[i]);
  for(int i = 0; i < first.size(); i++){
    if(i == first.size() - 1) printf("%05d %d -1"...
剩余内容已隐藏
查看完整文章以阅读更多
查看完整文章