单链表

AcWing 826. 单链表

实现一个单链表，链表初始为空，支持三种操作：

向链表头插入一个数；
删除第 $k$ 个插入的数后面的数；
在第 $k$ 个插入的数后插入一个数。

现在要对该链表进行 $M$ 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 $k$ 个插入的数并不是指当前链表的第 $k$ 个数。例如操作过程中一共插入了 $n$ 个数，则按照插入的时间顺序，这 $n$ 个数依次为：第 $1$ 个插入的数，第 $2$ 个插入的数，…第 $n$ 个插入的数。

输入格式

第一行包含整数 $M$ ，表示操作次数。

接下来 $M$ 行，每行包含一个操作命令，操作命令可能为以下几种：

H x，表示向链表头插入一个数 $x$ 。
D k，表示删除第 $k$ 个插入的数后面的数（当 $k$ 为 $0$ 时，表示删除头结点）。
I k x，表示在第 $k$ 个插入的数后面插入一个数 $x$ （此操作中 $k$ 均大于 $0$ ）。

输出格式

共一行，将整个链表从头到尾输出。

数据范围

$1 \le M \le 100000$
所有操作保证合法。

输入样例：

输出样例：

6 4 6 5

数组模拟单链表

不要通过scan(“%c”, &op) 读入操作字符：会读进\n

可以使用scanf(" %c", &op)`` ``scanf(" %c", &c)在%c之前空格会告诉scanf忽略前面的空行，而等待第一个非空行元素读入其中

#include <iostream>

using namespace std;

const int kN = 1e5 + 10;
int e[kN], ne[kN], head, idx;

void Init() {
  head = -1, idx = 0;
}

void AddToHead(int x) {
  e[idx] = x, ne[idx] = head, head = idx++;
}

// 在下标为k节点的后面插入值为x的新节点
void Insert(int k, int x) {
  e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}


// 删除下标为k节点的后面一个节点
void Del(int k) {
  ne[k] = ne[ne[k]];
}

int main() {
  Init();
  int n;
  scanf("%d", &n);
  char op;
  int k, x;
  
  while (n--) {
    scanf(" %c", &op);
    // cin >> op;
    if (op == 'H') {
      scanf("%d", &x);
      AddToHead(x);
    } else if (op == 'D') {
      scanf("%d", &k);
      if (!k) {
        head = ne[head];
      } else {
        Del(k - 1);  // 第k个节点的下标为k-1
      }
    } else if (op == 'I') {
      scanf("%d%d", &k, &x);
      Insert(k - 1, x);
    }
  }
  for (int i = head; i != -1; i = ne[i]) printf("%d ", e[i]);
  return 0;
}

双链表

AcWing 827. 双链表

实现一个双链表，双链表初始为空，支持 $5$ 种操作：

在最左侧插入一个数；
在最右侧插入一个数；
将第 $k$ 个插入的数删除；
在第 $k$ 个插入的数左侧插入一个数；
在第 $k$ 个插入的数右侧插入一个数

现在要对该链表进行 $M$ 次操作，进行完所有操作后，从左到右输出整个链表。

输入格式

第一行包含整数 $M$ ，表示操作次数。

接下来 $M$ 行，每行包含一个操作命令，操作命令可能为以下几种：

L x，表示在链表的最左端插入数 $x$ 。
R x，表示在链表的最右端插入数 $x$ 。
D k，表示将第 $k$ 个插入的数删除。
IL k x，表示在第 $k$ 个插入的数左侧插入一个数。
IR k x，表示在第 $k$ 个插入的数右侧插入一个数。

输出格式

共一行，将整个链表从左到右输出。

数据范围

$1 \le M \le 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>

using namespace std;

const int kN = 1e5 + 10;
int e[kN], l[kN], r[kN], idx;  // l[i]: 下标为i节点的左节点下标

// 初始化: 设置下标分别为0和1的点作为左右端点, 第1个工作节点的下标为2
void Init() {
  r[0] = 1, r[1] = 0, idx = 2; 
}

// 在下标为k的元素后面插入插入x
void Insert(int k, int x)
{
    e[idx] = x;
    l[idx] = k, r[idx] = r[k];
    l[r[k]] = idx, r[k] = idx++; // 不能写成l[r[idx]] = idx++: 会先算idx++导致idx改变
}

void Del(int k) {
  l[r[k]] = l[k], r[l[k]] = r[k];
}

int main() {
  Init();
  int n;
  scanf("%d", &n);
  
  string op;
  int k, x;
  while (n--) {
    cin >> op;
    if (op == "L") {
      scanf("%d", &x);
      Insert(0, x);
    } else if (op == "R") {
      scanf("%d", &x);
      Insert(l[1], x);
    } else if (op == "D") {
      scanf("%d", &k);
      Del(k + 1);
    } else if (op == "IL") {
      scanf("%d%d", &k, &x);
      Insert(l[k + 1], x);
    } else if (op == "IR") {
      scanf("%d%d", &k, &x);
      Insert(k + 1, x);
    }
  }
  for (int i = r[0]; i != 1; i = r[i]) printf("%d ", e[i]);
  return 0;
}

语法问题

[cling]$ int a[10];
[cling]$ int idx = 1;
[cling]$ a[idx] = idx++;
input_line_5:2:14: warning: unsequenced modification and access to 'idx' [-Wunsequenced]
 a[idx] = idx++;
   ~~~       ^
[cling]$ a
(int [10]) { 0, 0, 1, 0, 0, 0, 0, 0, 0, 0 }  // 将idx++后再赋值
[cling]$ a[0] = idx++;
[cling]$ a
(int [10]) { 2, 0, 1, 0, 0, 0, 0, 0, 0, 0 }  // 先赋值再++, 否则为3 (前面++过所以为2)

栈

AcWing 828. 模拟栈

实现一个栈，栈初始为空，支持四种操作：

push x – 向栈顶插入一个数 $x$ ；
pop – 从栈顶弹出一个数；
empty – 判断栈是否为空；
query – 查询栈顶元素。

现在要对栈进行 $M$ 个操作，其中的每个操作 $3$ 和操作 $4$ 都要输出相应的结果。

输入格式

第一行包含整数 $M$ ，表示操作次数。

接下来 $M$ 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。

数据范围

$1 \le M \le 100000$ ,
$1 \le x \le 10^9$
所有操作保证合法。

输入样例：

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例：

5
5
YES
4
NO

数组模拟栈

#include <iostream>

using namespace std;

const int kN = 1e5 + 10;
int stk[kN], tt;  // tt=0表示栈为空, 第一个工作节点的下标从1开始

int main() {
  int n;
  scanf("%d", &n);
  
  string op;
  int x;
  while (n--) {
    cin >> op;
    if (op == "push") {
      scanf("%d", &x);
      stk[++tt] = x;
    } else if (op == "pop") {
      tt--;
    } else if (op == "query") {
      printf("%d\n", stk[tt]);
    } else if (op == "empty") {
      printf("%s\n", (tt?  "NO": "YES"));
    }
  }
  return 0;
}

AcWing 3302. 表达式求值★

给定一个表达式，其中运算符仅包含 +,-,*,/（加减乘整除），可能包含括号，请你求出表达式的最终值。

注意：

数据保证给定的表达式合法。
题目保证符号 - 只作为减号出现，不会作为负号出现，例如，-1+2,(2+2)*(-(1+1)+2) 之类表达式均不会出现。
题目保证表达式中所有数字均为正整数。
题目保证表达式在中间计算过程以及结果中，均不超过 $2^{31}-1$ 。
题目中的整除是指向 $0$ 取整，也就是说对于大于 $0$ 的结果向下取整，例如 $5/3=1$ ，对于小于 $0$ 的结果向上取整，例如 $5/(1-4) = -1$ 。
C++和Java中的整除默认是向零取整；Python中的整除//默认向下取整，因此Python的eval()函数中的整除也是向下取整，在本题中不能直接使用。

输入格式

共一行，为给定表达式。

输出格式

共一行，为表达式的结果。

数据范围

表达式的长度不超过 $10^5$ 。

输入样例：

(2+2)*(1+1)

输出样例：

基于栈

#include <iostream>
#include <stack>
#include <unordered_map>

using namespace std;

stack<int> nums;
stack<char> op;

void eval() {
  int b = nums.top(); nums.pop();
  int a = nums.top(); nums.pop();
  char c = op.top(); op.pop();
  switch (c) {
    case '+': nums.push(a + b); break;
    case '-': nums.push(a - b); break;
    case '*': nums.push(a * b); break;
    case '/': nums.push(a / b); break;
  }
}

int main() {
  unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
  string str;
  cin >> str;
  for (int i = 0; i < str.size(); i++) {
    char c = str[i];
    if (isdigit(c)) {
      int j = i, x = 0;
      while (j < str.size() && isdigit(str[j])) x = 10 * x + str[j++] - '0';  // j++啦, 否则报TLE
      nums.push(x);
      i = j - 1;
    } else if (c == '(') {
      op.push(c);
    } else if (c == ')') {
      while (op.size() && op.top() != '(') eval();
      op.pop();
    } else {
      while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
      op.push(c);
    }
  }
  while (op.size()) eval();
  printf("%d\n", nums.top());
  return 0;
}

队列

AcWing 829. 模拟队列

实现一个队列，队列初始为空，支持四种操作：

push x – 向队尾插入一个数 $x$ ；
pop – 从队头弹出一个数；
empty – 判断队列是否为空；
query – 查询队头元素。

现在要对队列进行 $M$ 个操作，其中的每个操作 $3$ 和操作 $4$ 都要输出相应的结果。

输入格式

第一行包含整数 $M$ ，表示操作次数。

接下来 $M$ 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。

数据范围

$1 \le M \le 100000$ ,
$1 \le x \le 10^9$ ,
所有操作保证合法。

输入样例：

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例：

NO
6
YES
4

数组模拟队列

模拟队列, 初始化: hh = 0, tt = -1, 入队列: q[++tt] = x, 查空: hh <= tt

#include <iostream>

using namespace std;

const int kN = 1e5 + 10;
int q[kN], hh = 0, tt = -1;

int main() {
  int n;
  scanf("%d", &n);
  
  string op;
  int x;
  while (n--) {
    cin >> op;
    if (op == "push") {
      scanf("%d", &x);
      q[++tt] = x;
    } else if (op == "pop") {
      hh++;
    } else if (op == "query") {
      printf("%d\n", q[tt]);
    } else if (op == "empty") {
      printf("%s\n", (hh <= tt? "NO": "YES"));
    }
  }
  return 0;
}

单调栈

AcWing 830. 单调栈

给定一个长度为 $N$ 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 $-1$ 。

输入格式

第一行包含整数 $N$ ，表示数列长度。

第二行包含 $N$ 个整数，表示整数数列。

输出格式

共一行，包含 $N$ 个整数，其中第 $i$ 个数表示第 $i$ 个数的左边第一个比它小的数，如果不存在则输出 $-1$ 。

数据范围

$1 \le N \le 10^5$
$1 \le 数列中元素 \le 10^9$

输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

单调栈

STL版本

#include <iostream>
#include <stack>

using namespace std;

int main() {
  int n;
  scanf("%d", &n);
  stack<int> stk;
  while (n--) {
    int x;
    scanf("%d", &x);

    while (stk.size() && stk.top() >= x) stk.pop();
    if (stk.empty()) {
      printf("-1 ");
    } else {
      printf("%d ", stk.top());
    }
    stk.push(x);
  }
  return 0;
}

数组模拟版本

#include <iostream>

using namespace std;

const int kN = 1e5 + 10;
int stk[kN], tt = 0;

int main() {
  int n;
  scanf("%d", &n);
  while (n--) {
    int x;
    scanf("%d", &x);
    while (tt && stk[tt] >= x) tt--;
    printf("%d ", (tt? stk[tt]: -1));
    stk[++tt] = x;
  }
  return 0;
}

单调队列

AcWing 154. 滑动窗口

给定一个大小为 $n \le 10^6$ 的数组。

有一个大小为 $k$ 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 $k$ 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]， $k$ 为 $3$ 。

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 $n$ 和 $k$ ，分别代表数组长度和滑动窗口的长度。

第二行有 $n$ 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

8 3
1 3 -1 -3 5 3 6 7

输出样例：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

单调队列

单调栈/队列题思路：

先用暴力实现, 用栈/队列模拟
删除无用元素
有无单调性, 进行优化(比如查找问题用二分, 极值问题取端点)

#include <iostream>
#include <queue>

using namespace std;

const int kN = 1e6 + 10;
int a[kN];

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) scanf("%d", &a[i]);
  
  deque<int> q;
  for (int i = 0; i < n; i++) {
    while (q.size() && a[q.back()] >= a[i]) q.pop_back();
    q.push_back(i);
    if (q.size() && i - q.front() + 1 > k) q.pop_front();
    // if (q.size() > k) q.pop_front();  // 不对喔, 单调队列中很多值pop_back掉了
    if (i >= k - 1) printf("%d ", a[q.front()]);
  }
  printf("\n");
  
  q.clear();
  for (int i = 0; i < n; i++) {
    while (q.size() && a[q.back()] <= a[i]) q.pop_back();
    q.push_back(i);
    if (q.size() && i - q.front() + 1 > k) q.pop_front();
    if (i >= k - 1) printf("%d ", a[q.front()]);
  }
  return 0;
}

KMP

给定一个字符串 $S$ ，以及一个模式串 $P$ ，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 $P$ 在字符串 $S$ 中多次作为子串出现。

求出模式串 $P$ 在字符串 $S$ 中所有出现的位置的起始下标。

输入格式

第一行输入整数 $N$ ，表示字符串 $P$ 的长度。

第二行输入字符串 $P$ 。

第三行输入整数 $M$ ，表示字符串 $S$ 的长度。

第四行输入字符串 $S$ 。

输出格式

共一行，输出所有出现位置的起始下标（下标从 $0$ 开始计数），整数之间用空格隔开。

数据范围

$1 \le N \le 10^5$
$1 \le M \le 10^6$

输入样例：

3
aba
5
ababa

输出样例：

0 2

单链表

AcWing 826. 单链表

数组模拟单链表

双链表

AcWing 827. 双链表

算法

语法问题

栈

AcWing 828. 模拟栈

输入格式

输出格式

数据范围

输入样例：

输出样例：

数组模拟栈

AcWing 3302. 表达式求值★

输入格式

输出格式

数据范围

输入样例：

输出样例：

基于栈

队列

AcWing 829. 模拟队列

输入格式

输出格式

数据范围

输入样例：

输出样例：

数组模拟队列

单调栈

AcWing 830. 单调栈

输入格式

输出格式

数据范围

输入样例：

输出样例：

单调栈

STL版本

数组模拟版本

单调队列

AcWing 154. 滑动窗口

输入格式

输出格式

输入样例：

输出样例：

单调队列

KMP

输入格式

输出格式

数据范围

输入样例：

输出样例：

Trie

并查集

堆

哈希表