编程题学习

acwing

826. 单链表

#include <iostream>using namespace std;const int N = 100010;int idx, e[N], ne[N], head;void init()
{head = -1;idx = 0;
}void insert_head(int x)
{e[idx] = x;ne[idx] = head;head = idx ++ ;
}void delete_k_pos(int x, int k)
{e[idx] = x;ne[idx] = ne[k];ne[k] = idx ++ ;
}void delete_k(int k)
{ne[k] = ne[ne[k]];
}int main()
{int n;cin >> n;init();ios::sync_with_stdio(false);cin.tie(0);char op;int x, k;while (n -- ){cin >> op;if (op == 'H'){cin >> x;insert_head(x);}else if (op == 'D'){cin >> k;if (!k) head = ne[head];else{delete_k(k - 1);}}else{cin >> k >> x;delete_k_pos(x, k - 1);}}for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';cout << endl;return 0;
}

827. 双链表

#include <iostream>
#include <string>using namespace std;const int N = 100010;int idx, e[N], l[N], r[N];void init()
{r[0] = 1;l[1] = 0;idx = 2;
}// 在节点a的右边插入一个数x
void insert_a_right(int a, int x)
{e[idx] = x;r[idx] = r[a];l[idx] = a;l[r[a]] = idx;r[a] = idx ++ ;
}// 删除节点a
void delet_k(int a)
{l[r[a]] = l[a];r[l[a]] = r[a];
}int main()
{int n;cin >> n;init();int x, k;string op;while (n -- ){cin >> op;if (op == "L"){cin >> x;insert_a_right(0, x);}else if (op == "R"){cin >> x;insert_a_right(l[1], x);}else if (op == "D"){cin >> k;delet_k(k + 1);}else if (op == "IL"){cin >> k >> x;insert_a_right(l[k + 1], x);}else{cin >> k >> x;insert_a_right(k + 1, x);}}for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';cout << endl;return 0;
}

1. 之所以在 “D”, “IL”, “IR” 要用 k+1 的原因是 双链表的起始点是2. 所以，每个插入位置k的真实位置应该为 k-1+2 = k+1 (在单链表中为 k-1)。
2. 0, 1 节点的作用是边界。0为左边界，1为右边界。他俩在这里有点类似保留字的作用。正因如此，我们的idx也是从2开始
3. 最后遍历输出结果的 for (int i = rn[0]; i != 1; i = rn[i])。从 rn[0] 开始是因为 0 为左边界，而终止条件 i==1是因为1为右边界（如果碰到，说明已经遍历完毕）

828. 模拟栈

#include <iostream>using namespace std;const int N = 100010;int top = -1;int stk[N];int main()
{int n;cin >> n;string op;while (n -- ){int x;cin >> op;if (op == "push"){cin >> x;stk[++ top] = x;}else if (op == "query"){cout << stk[top] << endl;}else if (op == "pop"){top -- ;}else if (op == "empty"){if (top == -1){cout << "YES"<< endl;}else {cout << "NO" << endl;}}}
}