栈
A1051 出栈序列
①按序一直进栈，添加元素应查容量防止超限
②栈顶元素和序列匹配上，就可以继续下次匹配
#include <iostream>
#include <stack>
using namespace std;
int main() {
int M, N, K, c, k;
int s[1000];
stack<int> stk;
bool f;
scanf("%d%d%d", &M, &N, &K);
for (int i = 0; i < K; i++) {
c = k = 0;
f = true;
for (int j = 0; j < N; j++)
scanf("%d", &s[j]);
while (!stk.empty())
stk.pop();
while (c < N) {
stk.push(++c);
if (stk.size() > M) {
f = false;
break;
}
while (!stk.empty() && stk.top() == s[k]) {
stk.pop();
k++;
}
}
if (stk.empty() && f) printf("YES\n");
else printf("NO\n");
}
return 0;
}
队列
A1056 顺序对决
①每组决出赢家继续对决，每轮按序对决，符合FIFO使用队列，队列q按序保存当前轮选手
②解决晋级问题：每轮清空q，晋级的人存入q1，下一轮将q置为q1。总对决轮数 $\scriptsize ct0 = \left \lceil \frac{np}{ng} \right \rceil$
③解决分组问题：每轮 $\scriptsize ct = \left \lceil \frac{q.size()}{ng} \right \rceil$ 组，每ng个人按序比大小，最后不满ng时队列空则跳出，实现最后一组无论几个人自成一组。
④解决标号问题：淘汰的人给其标号n，倒置循环即 $\scriptsize n = ct + 1$
⑤何时结束：队列中仅有一个元素时决出最终赢家
吐槽：本题描述！第一次读的时候没懂哇……又臭又长又难懂，(ヘ･_･)ヘ┳━┳，全靠样例猜
#include <iostream>
#include <bits/stdc++.h>
#include <queue>
using namespace std;
int main() {
int np, ng, tp, maxi;
queue<int> q;
queue<int> q1;
scanf("%d%d", &np, &ng);
int w[np], n[np];
memset(n, 0, sizeof(n));
for (int i = 0; i < np; i++)
scanf("%d", &w[i]);
for (int i = 0; i < np; i++) {
scanf("%d", &tp);
q.push(tp);
}
while (q.size() > 1) {
int ct = q.size() % ng ? q.size() / ng + 1 : q.size() / ng;
for(int k = ct; k > 0; k--) {
maxi = q.front();
for (int i = 0; i < ng; i++) {
if (!q.empty()) {
tp = q.front();
if (w[maxi] < w[tp]) {
n[maxi] = ct + 1;
maxi = tp;
}
else if(w[maxi] > w[tp])
n[tp] = ct + 1;
q.pop();
}
else break;
}
q1.push(maxi);
}
while(!q1.empty()) {
q.push(q1.front());
q1.pop();
}
}
n[q.front()]++;
int i = 0;
for (; i < np - 1; i++)
printf("%d ", n[i]);
printf("%d\n", n[i]);
return 0;
}
链表
A1061 反转链表
该题需解决下述问题：
①如何表示链表
②如何反转链表：递归、栈迭代和迭代法，此处使用迭代法。要使当前节点cur指向前一节点pre，必须提前保存pre；而修改当前节点指针会导致丢失指向后续链表指针，故还需保存后续节点next
③如何控制分段数量
④解决分段之间的反转
⑤解决首尾问题
A1032 相交链表
此题所给数据特殊，链表无环且单串内无重复字符，即为找相同节点问题，以下给出双指针实现：
①哈希表 第一串读入各字符存set，第二串依次到set匹配即可
时间 $\scriptsize O(n_1+n_2)$，空间 $\scriptsize O(n_1)$
②双指针 指向两个串头的指针同时依次比对后移，两指针必在等长两串相交处相遇。两串长度不同时还想用此方法，就要 构造等长串 使得两指针在相交处相遇，设两串公共长度 $\scriptsize l$，各自的非公共长度 $\scriptsize a$ 和 $\scriptsize b$，则两串长度分别为 $\scriptsize l + a$ 和 $\scriptsize l + b$，分别叠加对方的非公共长度即可构造相交处为末尾的相等长度 $\scriptsize l + a + b$ ，妙蛙！
时间 $\scriptsize O(n_1+n_2)$，空间 $\scriptsize O(1)$
#include <iostream>
using namespace std;
const int maxn = 100001;
struct Node {
char letr;
int next;
Node(char letr, int next) : letr(letr), next(next) {}
} *node[maxn];
int main() {
int H1, H2, N;
scanf("%d%d%d", &H1, &H2, &N);
if (H1 == -1 || H2 == -1) {
printf("-1\n");
return 0;
}
int a, n; char d;
while (~scanf("%d %c %d", &a, &d, &n))
node[a] = new Node(d, n);
int p1 = H1, p2 = H2;
while (p1 != p2) {
p1 = p1 == -1 ? H2 : node[p1]->next;
p2 = p2 == -1 ? H1 : node[p2]->next;
}
if (p1 == -1) printf("-1\n");
else printf("%05d\n", p1);
return 0;
}
A1052 排序链表
十大排序方法中，归并排序和快速排序时间最优，为 $\scriptsize O(nlogn)$，下先给出链表归并排序方法，然而本题可使用库函数sort避免写复杂的逻辑
归并排序
①划分子链表：
a）划分子集[low,mid)、[mid,high]要找到链表中点mid，方法是使用双指针，使指针位移fast:slow=2，fast到末尾，slow即为中点mid
b）节点个数为0或1时自成序，空直接返回，单节点要断掉后续，否则将返回该节点为头的链表
①归并两条有序链表：超过单节点的子链表使用双指针依次比较后移方法筛选出后一节点，挂到记录的尾节点上去
此解法暂未计数有效节点（未排除不在链表中的节点）
#include <iostream>
using namespace std;
const int maxn = 100001;
struct Node {
int addr;
int key;
int next;
Node(int addr, int key, int next) : addr(addr), key(key), next(next) {}
} * node[maxn];
Node *merge(Node *l, Node *r) {
Node *vHead = new Node(-1, -1, -1);
Node *cur = vHead;
while (l && r) {
if (l->key <= r->key) {
cur->next = l->addr;
l = node[l->next];
}
else {
cur->next = r->addr;
r = node[r->next];
}
cur = node[cur->next];
}
cur->next = l ? l->addr : r ? r->addr : -1;
return node[vHead->next];
}
Node *part(Node *lo, Node *hi) {
if (lo == nullptr)
return lo;
if (node[lo->next] == hi) {
lo->next = -1;
return lo;
}
Node *fast = lo, *slow = lo;
while (fast != hi) {
slow = node[slow->next];
fast = node[fast->next];
if (fast != hi)
fast = node[fast->next];
}
return merge(part(lo, slow), part(slow, hi));
}
int main() {
int H, N;
scanf("%d%d", &H, &N);
int a, k, n;
while (~scanf("%d%d%d", &a, &k, &n))
node[a] = new Node(a, k, n);
Node *h = part(node[H], nullptr);
printf("%d %05d\n", cnt, h->addr);
for (; node[h->next]; h = node[h->next])
printf("%05d %d %05d\n", h->addr, h->key, h->next);
printf("%05d %d -1\n", h->addr, h->key);
return 0;
}
A1097 去重链表
使用 尾插法，用两条静态链表分别保存去重链表和重复链表
①两条链表：分别记录去重、重复链表头H、R和尾tailH、tailR
②检重加尾：每次检测set中是否已有当前元素，筛出当前节点cur作为新的尾部tail=cur并修改tail.next=-1，修改tail.next要提前保存 防止后继指针丢失
③边界输入：空链表、不重链表、全重链表、单元素链表
#include <iostream>
#include <cmath>
#include <unordered_set>
using namespace std;
const int maxn = 100001;
struct Node {
int addr;
int key;
int next;
Node(int addr, int key, int next) : addr(addr), key(key), next(next) {}
} *node[maxn];
int main() {
int H, N, R = -1;
scanf("%d%d", &H, &N);
int a, k, n;
while (~scanf("%d%d%d", &a, &k, &n))
node[a] = new Node(a, k, n);
unordered_set<int> st;
Node *cur = node[H], *tailH = nullptr, *tailR = nullptr;
while (cur) {
k = abs(cur->key);
if (!st.count(k)) {
st.insert(k);
if (tailH) tailH->next = cur->addr;
tailH = cur;
cur = node[cur->next];
tailH->next = -1;
}
else {
if (tailR == nullptr) R = cur->addr;
else tailR->next = cur->addr;
tailR = cur;
cur = node[cur->next];
tailR->next = -1;
}
}
Node *h;
for (h = node[H]; node[h->next]; h = node[h->next])
printf("%05d %d %05d\n", h->addr, h->key, h->next);
printf("%05d %d -1\n", h->addr, h->key, h->next);
if (R != -1) {
for (h = node[R]; node[h->next]; h = node[h->next])
printf("%05d %d %05d\n", h->addr, h->key, h->next);
printf("%05d %d -1\n", h->addr, h->key);
}
return 0;
}