单链表模板

题目

实现一个单链表，链表初始为空，支持三种操作： (1) 向链表头插入一个数； (2) 删除第k个插入的数后面的数； (3) 在第k个插入的数后插入一个数 现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。 注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。 输入格式 第一行包含整数M，表示操作次数。 接下来M行，每行包含一个操作命令，操作命令可能为以下几种： (1) “H x”，表示向链表头插入一个数x。 (2) “D k”，表示删除第k个输入的数后面的数（当k为0时，表示删除头结点）。 (3) “I k x”，表示在第k个输入的数后面插入一个数x（此操作中k均大于0）。 输出格式 共一行，将整个链表从头到尾输出。 数据范围 1≤M≤100000 所有操作保证合法。 输入样例： 10 H 9 I 1 1 D 1 D 0 H 6 I 3 6 I 4 5 I 4 5 I 3 4 D 6 输出样例： 6 4 6 5

代码

#include <iostream> using namespace std; const int N = 100010; // head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点 int h[N], e[N], ne[N], head, idx; void init() { head = -1; //head指向空指针，判断链表结束标志 idx = 0; } //链表头部插入元素 void insert(int a) { e[idx] = a; //相当于链式链表中的new一个节点 ne[idx] = head; head = idx++; //head指向第一个元素，不在指向-1，同时idx++，为插入下一个元素做准备。 } //链表第k个位置后面插入元素 void insert(int k, int a) { e[idx] = a; ne[idx] = ne[k]; ne[k] = idx++; } //删除链表第k个位置后面元素 void remove(int k) { ne[k] = ne[ne[k]]; } int main() { init(); int n; cin >> n; while(n--) { char s; cin >> s; if(s == 'H') { int x; cin >> x; insert(x); } else if(s == 'I') { int k, x; cin >> k >> x; insert(k - 1, x); } else { int k; cin >> k; if(k == 0) head = ne[head]; remove(k - 1); } } for(int i = head; i != -1; i = ne[i]) { cout << e[i] <<" "; } cout << endl; return 0; }

双链表模板

题目

实现一个双链表，双链表初始为空，支持5种操作： (1) 在最左侧插入一个数； (2) 在最右侧插入一个数； (3) 将第k个插入的数删除； (4) 在第k个插入的数左侧插入一个数； (5) 在第k个插入的数右侧插入一个数 现在要对该链表进行M次操作，进行完所有操作后，从左到右输出整个链表。 注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。 输入格式 第一行包含整数M，表示操作次数。 接下来M行，每行包含一个操作命令，操作命令可能为以下几种： (1) “L x”，表示在链表的最左端插入数x。 (2) “R x”，表示在链表的最右端插入数x。 (3) “D k”，表示将第k个插入的数删除。 (4) “IL k x”，表示在第k个插入的数左侧插入一个数。 (5) “IR k x”，表示在第k个插入的数右侧插入一个数。 输出格式 共一行，将整个链表从左到右输出。 数据范围 1≤M≤100000 所有操作保证合法。 输入样例： 10 R 7 D 1 L 3 IL 2 10 D 3 IL 2 7 L 8 R 9 IL 4 7 IR 2 2 输出样例： 8 7 7 3 2 9

代码

#include <iostream> #include <string> using namespace std; const int N = 100010; int e[N], l[N], r[N], idx; void init() { //0是左端点，1是右端点 r[0] = 1; l[1] = 0; idx = 2; } // 在节点k的右边插入一个数a void insert(int k, int a) { e[idx] = a; l[idx] = k; r[idx] = r[k]; l[r[k]] = idx; r[k] = idx++; } void remove(int k) { r[l[k]] = r[k]; l[r[k]] = l[k]; } int main() { int n; cin >> n; init(); while(n--) { string op; cin >> op; int k, x; if(op == "R") { cin >> x; insert(l[1], x); } else if(op == "L") { cin >> x; insert(0, x); } else if(op == "D") { cin >> k; remove(k + 1); } else if(op == "IL") { cin >> k >> x; insert(l[k + 1], x); //在k的左侧插入数值相当于在k左侧的数地右边插入数值 } else { cin >> k >> x; insert(k + 1, x); } } for(int i = r[0]; i != 1; i = r[i]) { cout <<e[i] << " "; } cout << endl; return 0; }

链表应用

题目描述

给定一个长度为 n 的序列 A，A 中的数各不相同。对于 A 中的每一个数 Ai，求： min1≤j<i|Ai−Aj| 以及令上式取到最小值的 j（记为 Pi）。若最小值点不唯一，则选择使 Aj 较小的那个。 输入格式 第一行输入整数n，代表序列长度。 第二行输入n个整数A1…An,代表序列的具体数值，数值之间用空格隔开。 输出格式 输出共n-1行，每行输出两个整数，数值之间用空格隔开。 分别表示当i取2~n时，对应的min1≤j<i|Ai−Aj|和Pi的值。 数据范围 n≤105,|Ai|≤109 输入样例： 3 1 5 3 输出样例： 4 1 2 1

题解

求某个数前面的最小的绝对值之差。可以先将原数组排序，（下标也随之排序）。然后在排序后的数组上建立双向链表，这样就可以找到某一个数左边和右边的数，他们是最接近这个数的。因此，绝对值在这两个数产生。从下标最大的开始，这样，不论左边还是右边元素在原数组下标都比他小。然后将这个下标对应的数从链表中删除。因为，这个数是最后的数。不可能在之后的数的前面出现。

#include <iostream> #include <algorithm> #include <cmath> using namespace std; const int N = 100010; typedef long long LL; typedef pair<LL, int> PII; PII a[N]; int p[N]; //记录排好序后，原数组下标在链表中的位置 int l[N], r[N]; PII ans[N]; //记录答案，方便逆序输出 int main() { int n; cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i].first; a[i].second = i; } sort(a + 1, a + n + 1); //创建链表 a[0].first = -3e9; a[n + 1].first = 3e9; for(int i = 1; i <= n; i++) { l[i] = i - 1; r[i] = i + 1; p[a[i].second] = i; // 记录原数组下标在链表中的位置 } for(int i = n; i > 1; i--) { int j = p[i]; //获取原数组的元素在链表中位置。 int left = l[j], right = r[j]; LL lv = abs(a[j].first - a[left].first), rv = abs(a[j].first - a[right].first); if(lv <= rv) ans[i] = {lv, a[left].second}; else ans[i] = {rv, a[right].second}; //删除这个元素，因为他是最大的 l[r[j]] = l[j]; r[l[j]] = r[j]; } for (int i = 2; i <= n; i ++ ) cout << ans[i].first << ' ' << ans[i].second << endl; return 0; }