文章目录
- 图论算法
- 常见题目与技巧 P1
- 常见题目与技巧 P2
- [删除链表的倒数第 N 个结点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
- 两两交换链表中的节点
- 删除排序链表中的重复元素
- [删除排序链表中的重复元素 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/)
- 环形链表
- [环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/)
- 相交链表
- 快乐数
- 移除链表元素
- 反转链表
- 删除链表中的节点
- 验证栈序列
- 比较含退格的字符串
- 删除字符串中的所有相邻重复项
- 图论算法
- 常见题目与技巧 P3
- 常见题目与技巧 P4
- 常见做题技巧 P5
- 常见做题技巧 P6
图论算法
图 = 点 + 边 无向图/有向图 有权图/无权图 环（有向图）
图的存储
邻接矩阵
#include <iostream>
using namespace std;
int arr[105][105], n, m;
int main() {
cin >> n >> m;
int a, b;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
arr[a][b] = c;
}
for (int i = 1; i <= n; i++) {
cout << i << " : ";
for (int i = 1; i <= n; j++) {
if (arr[i][j] != 0) {
cout << "{" << i << "-->" << j << "," << arr[i][j] << "} ";
}
}
cout << endl;
}
return 0;
}
dfs 是个回溯多大过程
bfs 队列 层序遍历
floyd
floyd算法——多源最短路 慢O(N^3) 简单
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k])
存在负环(一个环的路径为负数) 此时无最短路
#include <iostream>
#include <cstring>
using namespace std;
int arr[1005][1005], n, m, s;
int main() {
memset(arr, 0x3f, sizeof(arr));
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
if (arr[a][b] > c) {
arr[a][b] = c;
arr[b][a] = c;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]); }
}
}
for (int i = 1; i <= n; i++) {
arr[i][i] = 0;
if (arr[s][i] == 0x3F3F3F3F) {
cout << -1 << endl;
} else {
cout << arr[s][i] << endl;
}
}
return 0;
}
邻接表
只存储了有用的边，省空间 查边O(N)
邻接表 1
#include <iostream>
using namespace std;
int n, m, edg[105][105];
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
edge[a][++edge[a][0]] = b; // edge[a][0]——a点的边数
}
for (int i = 1; i <= n; i++) {
cout << i << " : ";
for (int j = 1; j <= edge[i][0]; j++) {
cout << edge[i][j] << " ";
}
cout << endl;
}
return 0;
}
邻接表 2
#include <iostream>
#include <vector>
using namespace std;
struct node {
int s, e, v;
};
int main() {
int n, m;
cin >> n >> m;
vector<vector<edge> > edg(n + 5, vector<edge>());
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
edge[a].push_back((edge{a, b, c}));
//edge[b].push_back((edge{b, a, c}));
}
for (int i = 1; i <= n; i++) {
cout << i << " : ";
for (int j = 0; j < edg[i].size(); j++) {
cout << "{" << i/*edg[i][j].s*/ << "--> "edge[i][j].e << "," << edg[i][j].v << "}";
}
cout << endl;
}
return 0;
}
dijkstra
1、从S中选出一个距离点v最近的点n
2、更新S中所有点距离点v的距离
最短路 时间复杂度O((E + V) * log(V))
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
struct node {// now 点， dis 距离
int now, dis;
bool operator< (const node &b) const {
return this->dis > b.dis;
}
};
struct edge {// e终点， v权值
int e, v;
};
int main() {
int n, m, s, ans[100005];
memset(ans, 0x3f, sizeof(ans));
cin >> n >> m >> s;
vector<vector<edge> > edg(n + 5, vector<edge>());
for (int i = 0; i < m; i++) { // 插边，重边未处理
int a, b, c;
cin >> a >> b >> c;
edg[a].push_back((edge{b, c}));
edg[b].push_back((edge{a, c}));
}
priority_queue<node> que;
que.push((node){s, 0});//起点入队列
ans[s] = 0; //起点去重
while (!que.empty()) { //dijkstra
node temp = que.top();
que.pop();//从状态中拿出最短路
if (ans[temp.now] < temp.dis) {// ans的边已经是最优解，无需更新
continue;
}
for (int i = 0; i < edg[temp.now].size(); i++) {
int e = edg[temp.now][i].e, v = edg[temp.now][i].v;
if (ans[e] > temp.dis + v) {//遍历以temp.now为起点的每条边
ans[e] = temp.dis + v; //更新距离
que.push((node){e, ans[e]});//将其丢入优先队列里，为后续节点更新做准备
}
}
}
for (int i = 1; i <= n; i++) {
if (ans[i] == 0x3f3f3f3f) {
cout << -1 << endl;
}
else {
cout << ans[i] << endl;
}
}
return 0;
}
链式前向星
类似邻接多重表（更优）
e v next(同起点的下一条边的编号)
数组模拟链表（头插法）
代码演示
#include <iostream>
#include <cstring>
using namespace std;
struct edge {
int e, v, next;
};
edge edg[1005];
int n, m, head[1005]; //head数组记录的是头节点
int main() {
memset(head, -1, sizeof(head));
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
edg[i].e = b; //终点
edg[i].v = c; //权值
edg[i].next = head[a]; //类似头插法，head[a]记录的是上一条边
head[a] = i; //更新头节点
}
for (int i = 1; i <= n; i++) {
cout << i << " : ";
for (int j = head[i]; j != -1; j = edg[j].next) {
cout << "{" << i << "-->" << edg[j].e << "," << edg[j].v << "}";
}
cout << endl;
}
return 0;
}
dijkstra+链式前向星
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct edge {
int e, v, next;
};
struct node {// now 点， dis 距离
int now, dis;
bool operator< (const node &b) const {
return this->dis > b.dis;
}
};
edge edg[200005];
int n, m, s, ans[100005], head[100005], cnt;
void add_edge(int a, int b, int c) {//链式前向星
edg[cnt].e = b;
edg[cnt].v = c;
edg[cnt].next = head[a];
head[a] = cnt;
cnt++;
}
int main() {
memset(head, -1, sizeof(head));
memset(ans, 0x3F, sizeof(ans));
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add_edge(a, b, c);
add_edge(b, a, c);
}
priority_queue<node> que;
que.push((node){s, 0});
ans[s] = 0;
while (!que.empty()) {
node temp = que.top();
que.pop();
if (temp.dis > ans[temp.now]) {
continue;
}
for (int i = head[temp.now]; i != -1; i = edg[i].next) {
int e = edg[i].e, v = edg[i].v;
if (ans[e] > ans[temp.now] + v) {
ans[e] = ans[temp.now] + v;
que.push((node){e, ans[e]});
}
}
}
for (int i = 1; i <= n; i++) {
if (ans[i] == 0x3f3f3f3f) {
cout << -1 << endl;
} else {
cout << ans[i] << endl;
}
}
return 0;
}
Bellman-ford
以边进行更新到点的距离 单源最短路径
初始化为极大值，每一轮更新遍历所有的边
通过边
用边起点的较短路+边的权值去更新边终点的答案
数据复杂度 O(N*M)，最差每轮更新一个点的最短路径 允许负边
执行n轮，每次遍历所有的边 更新一遍到原点的最短路
#include <iostream>
#include <cstring>
using namespace std;
struct edge {
int s, e, v;
};
edge edg[200005];
int n, m, s, ans[100005];
void add_edge(int a, int b, int c) {
edg[cnt].s = a;
edg[cnt].e = b;
edg[cnt].v = c;
cnt++;
}
int main() {
memset(ans, 0x3f, sizeof(ans));
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add_edge(a, b, c);
add_edge(b, a, c);
}
for (int i = 0; i <= n; i++) {//多少轮
int f = 0;
for (int j = 0; j < cnt; j++) {// 每一轮遍历所有边
if (ans[edg[j].e] > ans[edg[j].s] + edg[j].v) {
ans[edg[j].e] = ans[edg[j].s] + edg[j].v;
f = 1;
}
}
if (f == 0) break; //这一轮未更新任何点，即更新完成
}
for (int i = 1; i <= n; i++) {
if (ans[i] == 0x3f3f3f3f) {
cout << -1 << endl;
} else {
cout << ans[i] << endl;
}
}
return 0;
}
只有上一轮更新过的点，才能影响下一轮的更新
基于队列的bellman_ford的优化
最坏的时间复杂度 仍然是O(N*M)，时间复杂度不稳定，速度玄学
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct edge {
int e, v, next;
};
edge edg[200005];
int n, m, s, ans[100005], head[100005], cnt, mark[100005];//mark 每一轮去重
void add_edge(int a, int b, int c) { //链式前向星
edg[cnt].e = b;
edg[cnt].v = c;
edg[cnt].next = head[a];
head[a] = cnt++;
}
int main() {
memset(ans, 0x3f, sizeof(ans));
memset(head, -1, sizeof(head));
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add_edge(a, b, c);
add_edge(b, a, c);
}
queue<int> que;
ans[s] = 0;
que.push(s); //起点入队
mark[s] = 1;
while (!que.empty()){
int temp = que.front();//之前被更新过的点
que.pop();
mark[temp] = 0;
for (int i = head[temp]; i != -1; i = edg[i].next) {//所有以该点位起点的边去更新边的终点的答案
int e = edg[i].e, v = edg[i].v;
if (ans[e] > ans[temp] + v) {
ans[e] = ans[temp] + v;
if (mark[e] == 0) {
que.push(e);
mark[e] = 1;
}
}
}
}
for (int i = 1; i <= n; i++) {
if (ans[i] == 0x3f3f3f3f) {
cout << -1 << endl;
} else {
cout << ans[i] << endl;
}
}
return 0;
}
总结
邻接矩阵 n*n 快速知道下，y关系
表 m
链式前向星 用指针域模拟链表
最短路
floyd 多源，慢
dijkstra 单源，稳定的快，不能有负权边
bellman_ford 单源，慢
queue优化的bellman_ford，速度玄学，不稳定
医院设置
#include <iostream>
#include <cstring>
using namespace std;
int n, num[105], arr[105][105];
int main() {
memset(arr, 0x3F, sizeof(arr));
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> num[i];
int a, b;
cin >> a >> b;
if (a) {
arr[i][a] = 1;
arr[a][i] = 1;
}
if (b) {
arr[i][b] = 1;
arr[b][i] = 1;
}
arr[i][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
}
}
}
int ans = 0X3f3f3f3f;
for (int i = 1; i <= n; i++) {
int t = 0;
for (int j = 1; j <= n; j++) {
t += arr[j][i] * num[j];
}
ans = min(ans, t);
}
cout << ans << endl;
return 0;
}
灾后重建 floyd改
改一下 floyd 最外层循环即可
#include <iostream>
#include <cstring>
using namespace std;
int n, m, q, num[205], now, arr[205][205]; //now当前修到第几个点， num
int main(){
memset(arr, 0x3f, sizeof(arr));
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> num[i];
arr[i][i] = 0;
}
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
a++, b++;
arr[a][b] = arr[b][a] = c;
}
cin >> q;
for (int i = 0; i < q; i++) {
int x, y, t;
cin >> x >> y >> t;
x++, y++;
while (num[now] <= t && now <= n) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
arr[j][k] = min(arr[j][k], arr[j][now] + arr[now][k]);
}
}
now++;
}
if (num[x] > t || num[y] > t || arr[x][y] == 0x3f3f3f3f) {
cout << -1 << endl;
} else {
cout << arr[x][y] << endl;
}
}
return 0;
}
常见题目与技巧 P1
前缀和
快速求解区间和
求第0位到当前位的 和
询问 O(1)
空间复杂度 O(N)
class NumArray {
public:
int sum[10005] = {0};
NumArray(vector<int>& nums) {
for (int i = 0; i < num.size(); i++) {//总体向后偏移一位，不包含端点 i + 1
sum[i + 1] = sum[i] + nums[i];
}
}
int sumRange(int left, int right) {
return sum[right + 1] - sum[left];
}
};
二维数组的前缀和 分3块计算
class NumMatrix {
public:
int n, m;
vector<vector<int> > sum;
NumMatrix(vector<vector<int>>& matrix) {
n = matrix.size(), m = matrix[0].size();
sum = vector<vector<int> >(n, vector<int>(m, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
sum[i][j] = matrix[i][j];
if (i - 1 >= 0) {
sum[i][j] += sum[i - 1][j];
}
if (j - 1 >= 0) {
sum[i][j] += sum[i][j - 1];
}
if (i - 1 >= 0 && j - 1 >= 0){
sum[i][j] -= sum[i - 1][j - 1];
}
}
}
}
int sumRegion(int r1, int c1, int r2, int c2) {
int ans = sum[r2][c2];
if (r1 - 1 >= 0) {
ans -= sum[r1 - 1][c2];
}
if (c1 - 1 >= 0) {
ans -= sum[r2][c1 - 1];
}
if (c1 - 1 >= 0 && r1 -1 >= 0) {
ans += sum[r1 - 1][c1 - 1];
}
return ans;
}
};
广搜走地图
1、连通性
2、最少步数
队列（node） + 方向数组 + 判断和去重
#include <iostream>
#include <queue<
using namespace std;
struct node {
int x, y, step;
};
int n, m, sx, sy, ex, ey;
int dir[8][2] = {0, 1, 1, 0, 0, -1, -1, 0, 1, 1, 1, -1, -1};
char mmap[105][105];
void p(int cnt) {
cout << "--------------------" << cnt << "--------------------" << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << mmap[i][j]; //先新的点打印，后变为老的点
if (mmap[i][j] == 'x') {
mmap[i][j] = 'X'; //较早走过的点
}
}
cout << endl;
}
cout << "------------------------------------------" << endl;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; j++) {
cin >> mmap[i][j];
if (mmap[i][j] == 'S') {
sx = i, sy = j;
}
if (mmap[i][j] == 'T') {
ex = i, ey = j;
}
}
queue<node> que;
que.push((node){sx, sy, 0});
int cnt = 0;
while (!que.empty()) {
node temp = que.front;
que.pop();
for (int i = 0; i < 8; i++) {
int x = temp.x + dir[i][0];
int y = temp.y + dir[i][1];
if (mmap[x][y] == 'T') {
cout << temp.step + 1 << endl;
return 0;
}
if (mmap[x][y] == '.') {
que.push((node){x, y, temp.step + 1});
mmap[x][y] = 'x'; //去重
cnt++; //走了多少个点
if (cnt % 10 == 0) {
p(cnt);
}
}
}
}
return 0;
}
启发式搜索
本质是预估到达终点的距离，使用优先队列替代广搜的队列，并演示了相关的可视化代码，最终输出一条指定的最优解路
起点有多远 + 终点有多远 优先队列 欧式距离 其中一种为A*
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
struct node {
int x, y, step;
double h;
bool operator< (const node &b) const {
return step + h > b.step + b.h; // 小的优先 小顶堆-小于变大于 大顶堆-小于任是小于
}
};
int n, m, sx, sy, ex, ey, fx[105][105], fy[105][105];
int dir[8][2] = {0, 1, 1, 0, 0, -1, -1, 0, 1, 1, 1, -1, -1}; //八个方向
char mmap[105][105];
double dis(int x, int y) {
int t1 = x - ex, t2 = y - ey;
return sqrt(t1 * t1, t2 * t2);
}
void p(int cnt) {
cout << "--------------------" << cnt << "--------------------" << endl;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << mmap[i][j];
if (mmap[i][j] == 'x') {
mmap[i][j] = '~';
}
}
cout << endl;
}
cout << "------------------------------------------" << endl;
}
void func(int x, int y) {
if (mmap[x][y] == 'S') return;
mmap[x][y] = 'o';
func(fx[x][y], fy[x][y]); //爸爸的x和y
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; j++) {
cin >> mmap[i][j];
if (mmap[i][j] == 'S') {
sx = i, sy = j;
}
if (mmap[i][j] == 'T') {
ex = i, ey = j;
}
}
priority_queue<node> que;
que.push((node){sx, sy, 0, dis(sx, sy)});
int cnt = 0;
while (!que.empty()) {
node temp = que.top();
que.pop();
for (int i = 0; i < 8; i++) {
int x = temp.x + dir[i][0];
int y = temp.y + dir[i][1];
if (mmap[x][y] == 'T') {
func(temp.x, temp.y);
p(cnt);
cout << temp.step + 1 << endl;
return 0;
}
if (mmap[x][y] == '.') {
fx[x][y] = temp.x; //爸爸的x
ft[x][y] = temp.y; //爸爸的y
mmap[x][y] == 'x';
que.push((node){x, y, temp.step + 1, dis(x, y)});//优先选择dis最短计算
cnt++;
if (cnt % 5 == 0) {
p(cnt);
}
}
}
}
cout << -1 << endl;
return 0;
}
LRU 缓存机制
实现 LRUCache 类：
- LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
- void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
class LRUCache {
public:
struct node {
int key, val;
node *front, *back;
node() {
key = -1, val = -1;
front = back = nullptr;
}
node (int k, int v) {
key = k, val = v;
front = back = nullptr;
}
};
node *l, *r;//虚拟头 虚拟尾
int mmax, now;
unordered_map<int, node*> m;
LRUCache(int capacity) {
mmax = capacity, now = 0;
l = new node();
r = new node();
l->back = r;
r->front = l;
}
void push_frt(node *p) { // 头插
if (p->front != nullptr) { //调正p左右的元素，删除p
p->front->back = p->back;
p->back->front = p->front;
}
p->back = l->back;
p->front = l;
l->back->front = p;
l->back = p;
}
void del_back() {
node *p = r->front;
m.erase(p->key);
p->front->back = r;
r->front = p->front;
delete p;
}
int get(int key) {
if (m.count(key)) {
push_frt(m[key]);
return m[key]->val;
}
return -1;
}
void put(int key, int value) {
node *p;
if (m.count(key) == 0) {
p = new node(key, value);
m[key] = p;
now++;
} else {
p = m[key];
p->val = value;
}
push_frt(p);
if (now > mmax) {
now--;
del_back();
}
}
};
邮递员送信
起点终点互换
bellman-ford + 链式前向星
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct edge {
int e, v, next;
};
edge edg[2][100005];
int n, m, ans[2][100005], head[2][100005], mark[100005];
void add_edg(int cnt, int ind, int s, int e, int v) {
edg[cnt][ind].e = e;
edg[cnt][ind].v = v;
edg[cnt][ind].next = head[cnt][s];
head[cnt][s] = ind;
}
void func(int cnt) {
memset(mark, 0, sizeof(mark));
queue<int> que;
que.push(1);
ans[cnt][1] = 0;
mark[1] = 1;
while (!que.empty()) {
int temp = que.front();
que.pop();
mark[temp] = 0;
for (int i = head[cnt][temp]; i != -1; i = edg[cnt][i].next) {
int e = edg[cnt][i].e, v = edg[cnt][i].v;
if (ans[cnt][e] > ans[cnt][temp] + v) {
ans[cnt][e] = ans[cnt][temp] + v;
if (mark[e] == 0) {
mark[e] = 1;
que.push(e);
}
}
}
}
}
int main() {
memset(head, -1, sizeof(head));
memset(ans, 0x3f, sizeof(ans));
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add_edg(0, i, a, b, c);
add_edg(1, i, b, a, c); //变单源最短路
}
func(0);
func(1);
long long sum = 0;
for (int i = 2; i <= n; i++) {
sum += ans[0][i] + ans[1][i];
}
cout << sum << endl;
return 0;
}
常见题目与技巧 P2
删除链表的倒数第 N 个结点
1、虚拟头节点（方便对头节点操作）
2、左右指针，右指针后移N次，再左右一起移动，右指针指向空时，删除左指针的后一个元素即可
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *root = new ListNode(0, head); //创建虚拟头节点
ListNode *l = root, *r = head;
for (int i = 0; i < n; i++) {
r = r->next;
}
while (r != nullptr) {
l = l->next;
r = r->next;
}
ListNode *p = l->next;
l->next = l->next->next;
delete p;
ListNode *pp = root->next;
delete root;
return pp;
}
};
两两交换链表中的节点
1、虚拟头节点
2、p指针，交换p->next和p->next->next;
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *root = new ListNode(0, head);
ListNode *t = root;
while (t->next != nullptr && t->next->next != nullptr) {
ListNode *l = t->next;
ListNode *r = t->next->next;
l->next = r->next;
r->next = l;
t->next = r;
t = l;
}
ListNode *p = root->next;
delete root;
return p;
}
};
删除排序链表中的重复元素
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr) return head;
ListNode *p = head;
while (p->next != nullptr) {
if (p->next->val == p->val) {
ListNode* t = p->next;
p->next = p->next->next;
delete t;
} else {
p = p->next;
}
}
return head;
}
};
删除排序链表中的重复元素 II
左右指针
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode *root = new ListNode(0, head);
ListNode *l = root;
while (l->next != nullptr) {
ListNode *r = l->next->next;
while (r != nullptr && r->val == l->next->val) {
r = r->next;
}
if (r == l->next->next) { //没删元素
l = l->next;
} else { //删了元素
l->next = r;
}
}
return root->next;
}
};
环形链表
快慢指针
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == nullptr) return false;
ListNode *slow = head, *fast = head;
while (fast != nullptr && fast->next != nu;;ptr) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
return true;
}
}
return false;
}
};
环形链表 II
快慢指针 块指针 两倍路径于 慢指针
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while(true){
if(fast == nullptr || fast->next == nullptr){
return nullptr;
}
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
break;
}
}
fast = head;
while(slow != fast){
fast = fast->next;
slow = slow->next;
}
return slow;
}
};
相交链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode *a = headA, *b = headB;;
int f = 0;
while (1) {
if (a == b) {
return a;
}
if (a->next == nullptr) {
a = headB;
f++;
} else {
a = a->next;
}
if (b->next == nullptr) {
b = headA;
f++;
} else {
b = b->next;
}
if (f > 2) {
break;
}
}
return nullptr;
}
};
快乐数
快慢指针 or 哈希
class Solution {
public:
int num[10] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};
int func(int x) {
int t = 0;
while (x) {
t += num[x % 10];
x /= 10;
}
return t;
}
bool isHappy(int n) {
int slow = n, fast = n;
while (fast != 1) {
fast = func(fast);
fast = func(fast); //快指针
slow = func(slow);
if (fast == 1) {
break;
}
if (fast == slow) {
return false;
}
}
return true;
}
};
移除链表元素
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (head == nullptr) return head;
ListNode *root = new ListNode(0, head);
ListNode *l = root;
while(l != nullptr && l->next != nullptr) {
ListNode *r = l->next;
while(r != nullptr && r->val == val) {
r = r->next;
}
l->next = r;
l = l->next;
}
return root->next;
}
};
反转链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode *l = head, *r = head->next;
l->next = nullptr;
while (r != nullptr) {
ListNode *t = r->next;
r->next = l;
l = r;
r = t;
}
return l;
}
};
删除链表中的节点
借尸还魂
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
};
验证栈序列
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> sta;
int n = pushed.size();
for (int i = 0, j = 0; i < n; i++) { //模拟出栈
while (sta.empty() || sta.top() != popped[i]) { //栈顶不匹配，则入栈
if (j == n) {
return false;
}
sta.push(pushed[j]);//入栈
j++;
}
sta.pop();//匹配则出栈
}
return true;
}
};
比较含退格的字符串
两个栈
class Solution {
public:
bool backspaceCompare(string s, string t) {
stack<char> s1, s2;
for (auto c : s) {
if (c == '#') {
if (!s1.empty()) {
s1.pop();
}
} else {
s1.push(c);
}
}
for (auto c : t) {
if (c == '#') {
if (!s2.empty()) {
s2.pop();
}
} else {
s2.push(c);
}
}
while (!s1.empty() && !s2.empty()) {
if (s1.top() != s2.top()) {
return false;
}
s1.pop();
s2.pop();
}
if (s1.empty() && s2.empty()) {
return true;
}
return false;
}
};
删除字符串中的所有相邻重复项
栈模拟
class Solution {
public:
string removeDuplicates(string s) {
stack<char> sta;
for (auto c : s) {
if (sta.empty() || sta.top() != c) {
sta.push(c);
} else {
sta.pop();
}
}
string ans;
while (!sta.empty()) {
ans += sta.top;
sta.pop();
}
reverse(ans.begin());
return ans;
}
};
图论算法
最小生成树
kruskal = 边排序 + 并查集
#include <iostream>
#include <algorithm>
using namespace std;
struct edge {
int s, e, v;
bool operator< (const edge& b) const {
return this->v < b.v;
}
};
edge edg[200005];
int n, m, ans, my_union[5005], cnt;
void init() {
for (int i = 1; i <= n; i++) {
my_union[i] = i;
}
}
int find_fa(int x) {
if (my_union[x] == x) {
return x;
}
return my_union[x] = find_fa(my_union[x]);
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> edg[i].s >> edg[i].e >> edg[i].v;
}
sort(edg, edg + m);
init();
for (int i = 0; i < m; i++) {
int s = edg[i].s, e = edg[i].e, v = edg[i].v;
int fa = find_fa(s), fb = find_fa(e);
if (fa != fb) {
my_union[fa] = fb; // 合并两集合
ans += v;
cnt++;
if (cnt == n - 1) { // 已经选择 n - 1条边
cout << ans << endl; // 输出最小生成树的总长
return 0;
}
}
}
cout << "orz" << endl; // 最小生成树不存在
return 0;
}
prim 从一个点往外延申(选择最小路)
1、优先队列 (选择最小点 (到目前点集的) )
2、遍历某一起点的所有边（邻接表/链式前向星 较为方便）
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct node {
int e, v;
bool operator< (const node &b) const {
return this->v > b.v;
}
};
struct edge {
int e, v, next;
};
edge edg[4000005];
int n, m, head[5005], mark[5005], ans, cnt, edg_cnt, num[5005];//num[x] 表示连接到x边的权值 mark 表示某点有没有连通
void add_edg(int a, int b, int c) {
edg[edg_cnt].e = b;
edg[edg_cnt].v = c;
edg[edg_cnt].next = head[a];
head[a] = edg_cnt++;
}
int main() {
memset(head, -1, sizeof(head)); //-1终点
memset(num, 0x3f, sizeof(num));
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add_edg(a, b, c);
add_edg(b, a, c);
}
priority_queue<node> que;
que.push((node){n / 2, 0}); // 任意点为起点
while (!que.empty()) {
node temp = que.top();
que.pop();
if (mark[temp.e] == 1) { //已经连通
continue;
}
ans += temp.v;
mark[temp.e] = 1;
cnt++;
if (cnt == n) { //连通了n个点
cout << ans << endl;
return 0;
}
for (int i = head[temp.e]; i != -1; i = edg[i].next) {//遍历以temp.e为起点的边
int e = edg[i].e, v = edg[i].v;
if (mark[e] == 0 && num[e] > v) {// 当前边小于num[e]就加入优先队列，可省略
que.push((node){e, v});
num[e] = v;
}
}
}
cout << "orz" << endl;
return 0;
}
公路修建
prim 点 边现用现求
#include <iostream>
#include <cstring>
#include <queue>
#include <math.h>
#include <stdio.h>
using namespace std;
struct node {
int e;
double v;
bool operator< (const node &b) const {
return this->v > b.v;
}
};
int n, xy[50005][2], mark[5005], cnt;
double num[5005], ans;
double func(int a, int b) {
long long t1 = xy[a][0] - xy[b][0];
long long t2 = xy[a][1] - xy[b][1];
return sqrt(t1 * t1 + t2 * t2);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> xy[i][0] >> xy[i][1];
num[i] = 99999999999;
}
priority_queue<node> que;
que.push((node){1, 0});
while (!que.empty()) {
node temp = que.top();
que.pop();
if (mark[temp.e] == 1) continue;
ans += temp.v;
cnt++;
mark[temp.e] = 1;
if (cnt == n) {
printf("%.2f\n", ans);
return 0;
}
for (int i = 1; i <= n; i++) {
if (mark[i] == 0 && i != temp.e) {
double t = func(temp.e, i);
if (num[i] > t) {
num[i] = t;
que.push((node) {i, t});
}
}
}
}
}
无线通讯网
求删掉k个点以后的最小生成树的第n - k 长边
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
struct edge {
int s, e;
double v;
};
bool cmp(const edge &a, const edge &b) {
return a.v < b.v;
}
edge edg[250005];
int k, n, my_union[505], xy[505][2], edg_cnt, cnt;
void init() {
for (int i = 1; i <= n; i++) {
my_union[i] = i;
}
}
int find_fa(int x) {
if (my_union[x] == x) {
return x;
}
return my_union[x] = find_fa(my_union[x]);
}
int main() {
cin >> k >> n;
init();
for (int i = 1; i <= n; i++) {
cin >> xy[i][0] >> xy[i][1];
for (int j = 1; j < i; j++) { // 动态求所有边的长度
int t1 = xy[i][0] - xy[j][0];
int t2 = xy[i][1] - xy[j][1];
edg[edg_cnt].s = i;
edg[edg_cnt].e = j;
edg[edg_cnt++].v = sqrt(t1 * t1 + t2 * t2);
}
}
sort(edg, edg + edg_cnt, cmp);
for (int i = 0; i < edg_cnt; i++) {
int s = edg[i].s, e = edg[i].e;
double v = edg[i].v;
int fa = find_fa(s), fb = find_fa(e);
if (fa != fb) {
my_union[fa] = fb;
cnt++;
if (cnt == n - k) {
printf("%.2f\n", v);
return 0;
}
}
}
return 0;
}
最短路计数
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
struct node {// now 点， dis 距离
int now, dis;
bool operator< (const node& b) const {
return this->dis > b.dis;
}
};
struct edge {// e终点， v权值
int e, v;
};
int ans1[100005]; //方案数
int main() {
int n, m, s, ans[100005];
memset(ans, 0x3f, sizeof(ans));
cin >> n >> m;
for (int i = 1; i <= n; i++) { // init
ans1[i] = 1;
}
s = 1;
vector<vector<edge> > edg(n + 5, vector<edge>());
for (int i = 0; i < m; i++) { // 插边，重边未处理
int a, b, c;
cin >> a >> b;
c = 1;
edg[a].push_back((edge{ b, c }));
edg[b].push_back((edge{ a, c }));
}
priority_queue<node> que;
node t = { s, 0 };
que.push(t);//起点入队列
ans[s] = 0; //起点去重
while (!que.empty()) { //dijkstra
node temp = que.top();
que.pop();//从状态中拿出最短路
if (ans[temp.now] < temp.dis) {// 已经是较优解，无需更新
continue;
}
for (int i = 0; i < edg[temp.now].size(); i++) {
int e = edg[temp.now][i].e, v = edg[temp.now][i].v;
if (ans[e] > temp.dis + v) {//遍历以temp.now为起点的每条边
ans[e] = temp.dis + v; //更新距离
ans1[e] = ans1[temp.now];
t = { e, ans[e] };
que.push(t);//将其丢入优先队列里，为后续节点更新做准备
}
else if (ans[e] == temp.dis + v) {
ans1[e]= (ans1[e] + ans1[temp.now]) % 100003;
}
}
}
for (int i = 1; i <= n; i++) {
if (ans[i] == 0x3f3f3f3f) {
cout << 0 << endl;
}
else {
cout << ans1[i] << endl;
}
}
return 0;
}
拓扑排序
1、有向图 2、不唯一 3、图中不能有环
求每个节点的入度
取出一个入度为0的点，得到一个新图，求每个节点的入度
重复
不断取出入度为0的点
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct edge {
int e, next;
};
edge edg[100005];
int n, m, head[105], in_degreee[105], ans[105], cnt;
int main() {
memset(head, -1, sizeof(head));
cin >> n >> m;
for (int i = 0; i < m; i++) { //链式前向星
int a, b;
cin >> a >> b;
edg[i].e = b;
edg[i].next = head[a];
head[a] = i;
in_degree[b]++;
}
queue<int> que;
for (int i = 1; i <= n; i++) {
if (in_edgree[i] == 0) {
que.push(i);
}
}
while (!que.empty()) {
int temp = que.front();
que.pop();
ans[cnt++] = temp;
if (cnt == n) {
for (int i = 1; i < n; i++) {
cout << ans[i] << " ";
}
cout << endl;
return 0;
}
for (int i = head[temp]; i != -1; i = edg[i].next) { //遍历，找新的入度为0的点
int e = edg[i].e;
in_degree[e]--;
if (in_degree[e] == 0) {
que.push(e);
}
}
}
cout << "have loop" << endl; //有环
return 0;
}
输出所有拓扑排序
排列组合
选数
遍历边，入度-1
递归
遍历边，入度+1（回溯）
1、存数
2、标记去重
3、遍历，入度 - 1
4、递归
5、遍历，入度 - 1
6、标记取消
#include <iostream>
#include <vector>
using namespace std;
int n, m, ans[105], in_degree[105];
void func(int now, vector<vector<int> > &edg) {
if (now == n + 1) {
for (int i = 1; i <= n; i++) {
cout << ans[i] << " ";
}
cout << endl;
return ;
}
for (int i = 1; i <= n; i++) {
if (in_degree[i] == 0 && mark[i] == 0) {
ans[now] = i;
mark[i] = 1;
for (int j = 0; j < edg[i].size(); j++) {
in_degree[edg[i][j]]--;
}
func(now + 1, edg);
for (int j = 0; j < edg[i].size(); j++) {
in_degree[edg[i][j]]++;
}
mark[i] = 0;
}
}
}
int main() {
cin >> n >> m;
vector<vector<int> > edg(n + 1, vector<int>());
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
edg[a].push_back(b);
in_degree[b]++;
}
func(1， edg); // 1 递归深度
return 0;
}
#641. 拓扑排序
题目描述
给定一个有 NN 个点，MM 条边的有向无权图，现求其拓扑排序。若有多个拓扑排序，则尽可能让小数在前大数在后。
输入
输入文件第一行是两个整数 nn 和 mm。接下来 mm 行，每行 22 个整数 a,ba,b，表示有一条从 aa 点到 bb 点的边，保证数据中无环。
输出
输出文件包含 11 行，共有 NN 个整数，表示拓扑排序，每两个数中间用空格隔开。
样例输入
7 6
1 2
1 4
2 3
4 5
3 6
5 6
样例输出
1 2 3 4 5 6 7
代码：
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct edge {
int e, next;
};
edge edg[100005];
int n, m, head[105], in_degreee[105], ans[105], cnt;
int main() {
memset(head, -1, sizeof(head));
cin >> n >> m;
for (int i = 0; i < m; i++) { //链式前向星
int a, b;
cin >> a >> b;
edg[i].e = b;
edg[i].next = head[a];
head[a] = i;
in_degree[b]++;
}
queue<int> que;
for (int i = 1; i <= n; i++) {
if (in_edgree[i] == 0) {
que.push(i);
}
}
while (!que.empty()) {
int temp = que.front();
que.pop();
ans[cnt++] = temp;
if (cnt == n) {
for (int i = 1; i < n; i++) {
cout << ans[i] << " ";
}
cout << endl;
return 0;
}
for (int i = head[temp]; i != -1; i = edg[i].next) { //遍历，找新的入度为0的点
int e = edg[i].e;
in_degree[e]--;
if (in_degree[e] == 0) { // 入度为0，去更新其他点
que.push(e);
}
}
}
cout << "have loop" << endl; //有环
return 0;
}
priority_queue<Type,Container,Functional>
其中：
Type是数据类型
Container是容器类型（Container必须是用数组实现的容器，比如vector等默认为vector
Functional就是比较的方式，也是我们后边实现排序的重要角色
当我们不声明任何的时候，默认是大顶堆
priority_queue<int, vector<int>, greater<int>> q;//升序
priority_queue<int, vector<int>, less<int>> q;//降序
//greater和less是std中实现的两个仿函数
神经网络
求一遍拓扑排序，在求其C值
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
struct edge {
int e, v, next;
};
edge edg[10005];
int n, m, c[105], u[105], head[105], in_degree[105], out_degree[105], f;
int main() {
memset(head, -1, sizeof(head));
cin >> n >> m;
queue<int> que;
for (int i = 1; i <= n; i++) {
cin >> c[i] >> u[i];
if (c[i] != 0) {
que.push(i);
}
}
for (int i = 0; i < m; i++) {
int a, b, v;
cin >> a >> b >> v;
edg[i].e = b;
edg[i].v = v;
edg[i].next = head[a];
head[a] = i;
in_degree[b]++;
out_degree[a]++;
}
while (!que.empty()) {
int temp = que.front();
que.pop();
for (int i = head[temp]; i != -1; i = edg[i].next) {
int e = edg[i].e, v = edg[i].v;
in_degree[e]--;
if (c[temp] > 0) { //兴奋状态
c[e] += v * c[temp];
}
if (in_degree[e] == 0) {
que.push(e);
c[e] -= u[e];
}
}
}
for (int i = 1; i <= n; i++) {
if (out_degree[i] == 0 && c[i] > 0) {
cout << i << " " << c[i] << endl;
f = 1;
}
}
if (f == 0) {
cout << "NULL" << endl;
}
return 0;
}
旅行计划
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, in_degree[100005], ans[100005];
int main() {
cin >> n >> m;
vector <vector<int> > edg(n + 1, vector<int>());
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
edg[a].push_back(b);
in_degree[b]++;
}
queue<int> que;
for (int i = 1; i <= n; i++) {
if (in_degree[i] == 0) {
que.push(i);
ans[i] = 1;
}
}
while (!que.empty()) {
int temp = que.front();
que.pop();
for (int i = 0; i < edg[temp].size(); i++) {
int e = edg[temp][i];
ans[e] = ans[temp] + 1; //上一个点的
in_degree[e]--;
if (in_degree[e] == 0) { // 入度为0，去更新其他点
que.push(e);
}
}
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << endl;
}
return 0;
}
食物链计数
输出总链数，本质上就是拓扑排序
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, ans[5005], in_degree[5005], out_degree[5005];
int main() {
cin >> n >> m;
vector<vector<int> > edg(n + 1, vector<int>());
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
in_degree[b]++;
out_degree[a]++;
edg[a].push_back(b);
}
queue<int> que;
for (int i = 1; i <= n; i++) {
if (in_degree[i] == 0) {
que.push(i);
ans[i] = 1;
}
}
while (!que.empty()) {
int temp = que.front();
que.pop();
//for (int i =0; i < edg[temp].size(); i++) {
//int e = edg[temp][i];
for (auto e : edg[temp]) {
ans[e] += ans[temp]; //到这的链的数量的累加
ans[e] %= 100000007;
in_degree[e]--;
if (in_degree[e] == 0) {
que.push(e);
}
}
}
int sum = 0;
for (int i = 1; i <= n; i++) {
if (out_degree[i] == 0) {
sum += ans[i];
sum %= 100000007;
}
}
cout << sum << endl;
return 0;
}
排序
成环 > 求解
#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
using namespace std;
int n, m, in_degree[30];
char ans[30];
int func(vector<vector<int> > &edg) { //求一轮
int in[30];
queue<int> que;
for (int i = 0; i < n; i++) { //拷贝入度数组
in[i] = in_degree[i];
if (in[i] == 0) {
que.push(i);
}
}
int ans_cnt = 0, mmax = que.size(); //ans_cnt 已经求好的元素数量 和标记
while (!que.empty()) { //跑一遍 mmax数量大于1，表明拓扑排序不唯一，故不能确定排序
mmax = max(mmax, (int)que.size());
int temp = que.front();
que.pop();
ans[ans_cnt++] = temp + 'A';
for (auto e : edg[temp]) {
in[e]--;
if (in[e] == 0) {
que.push(e);
}
}
}
if (ans_cnt != n) return -1;
if (mmax <= 1) return 1;
return 0;
}
int main() {
cin >> n >> m;
vector<vector<int> > edg(n, vector<int>());
for (int i = 1; i <= m; i++) {
char t[4];
cin >> t;
int a = t[0] - 'A', b = t[2] - 'A';
edg[a].push_back(b);
in_degree[b]++; //入度加一
int cnt = func(edg);
if (cnt == -1) {
printf("Inconsistency found after %d relations.\n", i);
return 0;
} else if (cnt == 1) { //拓扑排序唯一
printf("Sorted sequence determined after %d relations: %s.", i, ans);
return 0;
}
}
printf("Sorted sequence cannot be determined.");
return 0;
}
常见题目与技巧 P3
先序中序求后序
中左右 + 左中右 ->左右中
#include <iostream>
#include <cstring>
using namespace std;
char front[105], mid[105];
void func(int fl, int fr, int ml, int mr) {
if (fl > fr) return ;
if (fl == fr) { //只有一个元素 叶子节点 结束递归
cout << front[fl];
return ;
}
char root = front[fl];
int ind;
for (int i = ml; i <= mr; i++) {
if (mid[i] == root) {
ind = i; //ind 根的位置
break;
}
}
// 原长mr - ml + 1
func(fl + 1, fl + ind - ml, ml, ind - 1); //左子树： 起始位fl + 1，长度ind - ml(含端点)
func(fl + ind - ml + 1, fr, ind + 1, mr); //右子树： 起始位fl + ind - ml + 1，末位fr长度 mr - ind(含端点)
// 长度 mr - ml
cout << root;
}
int main() {
cin >> front >> mid;
func(0, strlen(front) - 1, 0, strlen(mid));
return 0;
}
后序中序求先序
左右中 + 左中右 -> 中左右
#include <iostream>
#include <cstring>
using namespace std;
char mid[105], back[105];
void func(int ml, int mr, int bl, int br) { //mid left mid right
if (ml > mr) return ;
if (ml == mr) { //只有一个元素 叶子节点 结束递归
cout << mid[ml];
return ;
}
char root = back[br];
int ind;
for (int i = ml, i <= mr; i++) {
if (mid[i] == root) {
ind = i;
break;
}
}
cout << root
func(ml, ind - 1, nl, bl + ind - ml - 1);
func(ind + 1, mr, bl + ind - ml, br - 1);
}
int main() {
cin >> mid >> back;
func(0, strlen(mid) - 1, 0, strlen(back) - 1);
cout << endl;
return 0;
}
从前序与中序遍历序列构造二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<int, int> m;
TreeNode *func(int fl, int fr, int ml, int mr, vector<int> &front, vector<int> &mid) {
if (fl > fr) return nullptr;
if (fl == fr) {
TreeNode *p = new TreeNode(front[fl]);
return p;
}
TreeNode *p = new TreeNode(front[fl]);
int ind = m[front[fl]];
p->left = func(fl + 1, fl + ind - ml, ml, ind - 1, front, mid);
p->right = func(fl + ind - ml + 1, fr, ind + 1, mr, front, mid);
return p;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
for (int i = 0; i < inorder.size(); i++) {
m[inorder[i]] = i;
}
TreeNode *root = func(0, preorder.size() - 1, 0, preorder.size() - 1, preorder, inorder);
return root;
}
};
中序与后序遍历序列构造二叉树
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
unordered_map<int, int> m;
TreeNode *func(int ml, int mr, int bl, int br, vector<int> &mid, vector<int> &back) {
if (ml > mr) return nullptr;
if (ml == mr) {
TreeNode *p = new TreeNode(mid[ml]);
return p;
}
TreeNode *p = new TreeNode(back[br]);
int ind = m[back[br]];
p->left = func(ml, ind - 1, bl, bl + ind - ml - 1, mid, back);
p->right = func(ind + 1, mr, bl + ind - ml, br - 1, mid, back);
return p;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
for (int i = 0; i < inorder.size(); i++) {
m[inorder[i]] = i;
}
TreeNode *root = func(0, inorder.size() - 1, 0, postorder.size() - 1, inorder, postorder);
return root;
}
};
如何判断给出的先序和中序就是不匹配的
找每一次递归中遍历元素是否匹配
[USACO06NOV]Roadblocks G
严格次短路
bellmanford
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;
struct edge {
int e, v, next;
};
edge edg[200005];
int n, m, edg_cnt, head[5005], ans[5005], ans2[5005], mark[5005];
void add_edg(int s, int e, int v) {
edg[edg_cnt].e = e;
edg[edg_cnt].v = v;
edg[edg_cnt].next = head[s];
head[s] = edg_cnt++;
}
int main() {
memset(head, -1, sizeof(head));
memset(ans, 0x3f, sizeof(ans));
memset(ans2, 0x3f, sizeof(ans2));
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add_edg(a, b, c);
add_edg(b, a, c);
if (a == 1 || b == 1) { // 所有连接起点的次短路
ans2[1] = min(ans2[1], c * 2); // 起点次短路更新为 最短路的两倍 (无向图)
}
}
ans[1] = 0;
queue<int> que;
que.push(1);
mark[1] = 1;
while (!que.empty()) {
int temp = que.front();
que.pop();
mark[temp] = 0;
for (int i = head[temp]; i != -1; i = edg[i].next) {
int e = edg[i].e, v = edg[i].v;
if (ans[temp] + v < ans[e]) { //最短路->最短路
ans2[e] = ans[e];
ans[e] = ans[temp] + v;
if (mark[e] == 0) {
mark[e] = 1;
que.push(e);
}
}
if (ans[temp] + v < ans2[e] && ans[temp] + v != ans[e]) { //最短路->次短路
ans2[e] = ans[temp] + v;
if (mark[e] == 0) {
mark[e] = 1;
que.push(e);
}
}
if (ans2[temp] + v < ans2[e]) { //次短->次短
ans2[e] = ans2[temp] + v;
if (mark[e] == 0) {
mark[e] = 1;
que.push(e);
}
}
}
}
cout << ans2[n] << endl;
/*
for (int i = 1; i <= n; i++) {
cout << i << " " << ans[i] << " " << ans2[i] << endl;
}
*/
return 0;
}
最长路
基于队列优化的bellman_ford
#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;
struct edge {
int e, v, next;
};
edge edg[50005];
int n, m, head[1505], ans[1505], in_degree[1505], mark[1505];
int func(int x) { //第一遍，遍历1的所有边
if (x == n) return 0; //能走到
for (int i = head[x]; i != -1; i = edg[i].next) {
int e = edg[i].e;
if (mark[e] == 0) {
mark[e] = 1;
if (func(e) == 0) return 0; //能走到
}
}
return 1;
}
int main() {
memset(head, -1, sizeof(head));
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
edg[i].e = b;
edg[i].v = c;
edg[i].next = head[a];
head[a] = i;
in_degree[b]++;
}
if (func(1)) { //判断能否走到N号点
cout << -1 << endl;
return 0;
}
queue<int> que;
ans[1] = 0;
for (int i = 1; i <= n; i++) {
ans[i] = -2100000000; //防止负数出现
if (in_degree[i] == 0) {
que.push(i);
}
}
ans[1] = 0;
while (!que.empty()) {
int temp = que.front();
que.pop();
for (int i = head[temp]; i != -1; i = edg[i].next) {
int e = edg[i].e, v = edg[i].v;
ans[e] = max(ans[e], ans[temp] + v);
in_degree[e]--;
if (in_degree[e] == 0) {
que.push(e);
}
}
}
cout << ans[n] << endl;
return 0;
}
宿舍楼里的电竞赛
folyd
多源最短路 求 排名
确定一个数组 排在A之前的数量 + 排在A之后的数量 == n - 1
#include <iostream>
#include <cstring>
using namespace std;
int n, m, arr[105][105], ans, in_degree[105];
int main() {
memset(arr, 0x3f, sizeof(arr));
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
arr[a][b] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= n; k++) {
arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (arr[i][j] != 0x3f3f3f3f) { //有路径
in_degree[i]++; //排在后面 i 赢了的次数
in_degree[j]++; //排在后面 j 输了
}
}
}
for (int i = 1; i <= n; i++) {
if (in_degree[i] == n - 1) {
ans++;
}
}
cout << ans << endl;
return 0;
}
常见题目与技巧 P4
二叉树的前序遍历
二叉树的非递归遍历: 栈 morois遍历(省内存)
递归
class Solution {
public:
void preorder(TreeNode *root, vector<int> &res) {
if (root == nullptr) {
return;
}
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
vector<int> preorderTraversal(TreeNode *root) {
vector<int> res;
preorder(root, res);
return res;
}
};
stack 迭代
vector
stack 父入栈，左边入栈(递推)，左为空父出栈，父右边入栈，右空，祖父出栈…
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (root == nullptr) {
return res;
}
stack<TreeNode*> stk;
TreeNode* node = root;
while (!stk.empty() || node != nullptr) {
while (node != nullptr) {
res.emplace_back(node->val); //插入后面
stk.emplace(node); //插入
node = node->left;
}
node = stk.top();
stk.pop();
node = node->right;
}
return res;
}
};
morois遍历
找前驱节点 建立虚拟指针，遍历到前驱的右指针为自身，说明遍历完左子树 root 左移动 root 右移动
利用空指针进行回溯操作
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> ans;
while (root != nullptr) {
if (root->left == nullptr) { //左子树为空，处理右子树 或者 回到黑边
ans.push_back(root->val);
root = root->right;
} else {
TreeNode *pre = root->left;
while (pre->right != nullptr && pre->right != root) {//找前驱
pre = pre->right;
}
if (pre->right == nullptr) { //第一次找到前驱，建立黑边，并处理左子树
ans.push_back(root->val);
pre->right = root;
root = root->left; //处理
} else { //第二次找到前驱，还原，处理右子树
pre->right = nullptr;
root = root->right; //处理
}
}
}
return ans;
}
};
二叉树的中序遍历
morois遍历 改变输出的条件
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
while (root != nullptr) {
if (root->left == nullptr) { //左子树为空，处理右子树 或者 回到黑边
ans.push_back(root->val);
root = root->right;
} else {
TreeNode *pre = root->left;
while (pre->right != nullptr && pre->right != root) {//找前驱
pre = pre->right;
}
if (pre->right == nullptr) { //第一次找到前驱，建立黑边，并处理左子树
//ans.push_back(root->val); 改到第二次找到前驱的时候进行输出
pre->right = root;
root = root->left; //处理
} else { //第二次找到前驱，还原，处理右子树
ans.push_back(root->val);
pre->right = nullptr;
root = root->right; //处理
}
}
}
return ans;
}
};
二叉树的后序遍历
倒序输出
class Solution {
public:
void add_ans(TreeNode *p, vector<int> &ans) {
stack<int> sta;
while (p != nullptr) {
sta.push(p->val);
p = p->right;
}
while (!sta.empty()) {
ans.push_back(sta.top());
sta.pop();
}
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ans;
TreeNode *p = new TreeNode(0);
p->left = root;
while (p != nullptr) {
if (p->left == nullptr) {
p = p->right;
} else {
TreeNode *pre = p->left;
while (pre->right != nullptr && pre->right != p) {//找前驱节点
pre = pre->right;
}
if (pre->right == nullptr) { //第一次找前驱，建立黑边，处理左子树
pre->right = p;
p = p->left;
} else { //第二次找前驱，倒序输出，处理右子树
pre->right = nullptr;
add_ans(p->left, ans); //倒序输出
p = p->right;
}
}
}
return ans;
}
};
棒球比赛
class Solution {
public:
int calPoints(vector<string>& ops) { //string 数组
stack<int> sta;
int ans = 0;
for (auto s : ops) {
if (s == "+") {
int t1 = sta.top();
sta.pop();
int t2 = sta.top() + t1;
sta.push(t1);
sta.push(t2);
ans += t2;
} else if (s == "D") {
ans += sta.top() * 2;
sta.push(sta.top() * 2);
} else if (s == "C") {
ans -= sta.top();
sta.pop();
} else {
int t = stoi(s);
ans += t;
sta.push(t);
}
}
return ans;
}
};
删除最外层的括号
用栈模拟，入栈出栈时判断栈是否为空，以此判断是否最外层
class Solution {
public:
string removeOuterParentheses(string s) {
stack<bool> sta;
string ans;
for (auto c : s) {
if (c == '(') {
if (!sta.empty()) {
ans += '(';
}
sta.push(true);
} else {
sta.pop();
if (!sta.empty()) {
ans += ')';
}
}
}
return ans;
}
};
最近的请求次数
class RecentCounter {
public:
queue<int> que;
RecentCounter() {
}
int ping(int t) {
que.push(t);
while (t - que.front() > 3000) {
que.pop();
}
return que.size();
}
};
相同的树
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) return true;
if (p == nullptr || q == nullptr || p->val != q->val) return flase;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
对称二叉树
class Solution {
public:
bool func(TreeNode *p, TreeNode *q) {
if (p == nullptr && q == nullptr) return true;
if (p == nullptr || q == nullptr || p->val != q->val) return false;
return func(p->left, q->right) && func(p->right, q->left);
}
bool isSymmetric(TreeNode* root) {
if (root == nullptr) return true;
return func(root->left, root->right);
}
};
二叉树的层序遍历
广搜
class Solution {
public:
struct node {
TreeNode *p;
int deep; //层深
};
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int> > ans;
if (root == nullptr) return ans;
vector<int> line;
int cnt = 0;
queue<node> que;
que.push((node){root, 0});
while (!que.empty()) {
node temp = que.front();
que.pop();
if (temp.deep != cnt) {
ans.push_back(line);
line.clear();
cnt = temp.deep;
}
line.push_back(temp.p->val);
if (temp.p->left != nullptr) {
que.push((node){temp.p->left, temp.deep + 1});
}
if (temp.p->right != nullptr) {
que.push((node){temp.p->right, temp.deep + 1});
}
}
ans.push_back(line); //最后一层的push_back
return ans;
}
};
二叉树的层序遍历 II
1、栈
2、队列 + reverse
class Solution {
public:
struct node {
TreeNode *p;
int deep; //层深
};
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int> > ans;
if (root == nullptr) return ans;
vector<int> line;
int cnt = 0;
queue<node> que;
que.push((node){root, 0});
while (!que.empty()) {
node temp = que.front();
que.pop();
if (temp.deep != cnt) {
ans.push_back(line);
line.clear();
cnt = temp.deep;
}
line.push_back(temp.p->val);
if (temp.p->left != nullptr) {
que.push((node){temp.p->left, temp.deep + 1});
}
if (temp.p->right != nullptr) {
que.push((node){temp.p->right, temp.deep + 1});
}
}
ans.push_back(line); //最后一层的push_back
reverse(ans.begin(), ans.end());
return ans;
}
};
二叉树的锯齿形层序遍历
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int> > ans; //ans[][]
if(root == nullptr) return ans;
queue<TreeNode*> q, next; //两个队列 区分层数
vector<int> temp;
q.push(root);
while(!q.empty()) {
TreeNode *node = q.front();
q.pop();
temp.push_back(node->val);
if (node->left) next.push(node->left);
if (node->right) next.push(node->right);
if (q.empty()) {
ans.push_back(temp);
temp.clear();
q.swap(next);
}
}
for(int i = 0; i < ans.size(); i++) {
if(i % 2 == 1) {
std::reverse(ans[i].begin(), ans[i].end());
}
}
return ans;
}
};
二叉树的最大深度
class Solution {
public:
int ans;
void func(TreeNode *p, int deep) {
if (p == nullptr) return ;
ans = max(ans, deep);
func(p->left, deep + 1);
func(p->right, deep + 1);
}
int maxDepth(TreeNode* root) {
ans = 0;
func(root, 1);
return ans;
}
};
二叉树的最小深度
class Solution {
public:
int ans;
void func(TreeNode *p, int deep) {
if (p == nullptr || deep >= ans) return ;
if (p->left == nullptr && p->right == nullptr) {
ans = min(ans, deep);
return ;
}
func(p->left, deep + 1);
func(p->right, deep + 1);
}
int minDepth(TreeNode* root) {
if (root == nullptr) {
return 0;
}
ans = INT_MAX;
func(root, 1);
return ans;
}
};
将有序数组转换为二叉搜索树
class Solution {
public:
TreeNode* helper(vector<int>& nums, int left, int right) {
if (left > right) {
return nullptr;
}
int mid = (left + right) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = helper(nums, left, mid - 1);
root->right = helper(nums, mid + 1, right);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1);
}
};
常见做题技巧 P5
线段树
线段树 区间和 初始化O(N) 修改O(logN) 查询O(logN)
前缀和 区间和 初始化O(N) 修改O(N) 查询O(1)
线段树 修改 懒标记
练习题2：线段树模板(二)
#include <iostream>
using namespace std;
struct node {
int l, r, cnt; // l~r 区间 , cnt元素数量
long long sum, lazy;
};
node tree[40005];
int n, m;
long long num[10005];
void up_sum(int now) { // 修改值上浮
tree[now].sum = tree[now * 2].sum + tree[now * 2 + 1].sum;
}
void down_lazy(int now) { //懒标记 下沉
if (tree[now].lazy != 0) {
tree[now * 2].lazy += tree[now].lazy;
tree[now * 2].sum += tree[now * 2].cnt * tree[now].lazy;
tree[now * 2 + 1].lazy += tree[now].lazy;
tree[now * 2 + 1].sum += tree[now * 2 + 1].cnt * tree[now].lazy;
tree[now].lazy = 0;
}
}
void built_tree(int now, int l, int r) { //建树
tree[now].l = l, tree[now].r = r;
tree[now].cnt = r - l + 1;
tree[now].lazy = 0;
if (l == r) {
tree[now].sum = num[l];
return ;
}
int mid = (l + r) / 2;
built_tree(now * 2, l, mid);
built_tree(now * 2 + 1, mid + 1, r);
up_sum(now);
}
void modify(int now, int l, int r, int v) { //修改
if (tree[now].l >= l && tree[now].r <= r) {
tree[now].sum += tree[now].cnt * v; // sum += 数量 * 加上的值
tree[now].lazy += v;
return ;
}
down_lazy(now);
int mid = (tree[now].l + tree[now].r) / 2;
if (mid >= l) modify(now * 2, l, r, v);
if (mid < r) modify(now * 2 + 1, l, r, v);
up_sum(now);
}
long long query(int now, int l, int r) { //查询
if (tree[now].l >= l && tree[now].r <= r) {
return tree[now].sum;
}
down_lazy(now);
int mid = (tree[now].l + tree[now].r) / 2;
long long t = 0;
if (mid >= l) t += query(now * 2, l, r);
if (mid < r) t += query(now * 2 + 1, l, r);
return t;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> num[i];
}
built_tree(1, 1, n); //第一层 1到n
for (int i = 0; i < m; i++) {
int t, a, b, c;
cin >> t;
if (t == 1) { //修改 加上c
cin >> a >> b >> c;
modify(1, a, b, c);
} else { //查询
cin >> a >> b;
cout << query(1, a, b) << endl;
}
}
return 0;
}
单调栈
有序的栈
适合解决 向前或者向后 第一个元素 大于或者小于 的问题
柱状图中最大的矩形
class Solution {
public:
struct node {
int ind, h; //ind 下标
};
int largestRectangleArea(vector<int>& heights) {
stack<node> sta; //up 升序
sta.push((node){-1, -1});
int ans = 0;
for (int i = 0; i < heights.size(); i++) {
while (sta.size() != 1 && sta.top().h > heights[i]) { //弹出，并求height[i]的面积
node temp = sta.top();
sta.pop();
ans = max(ans, temp.h * (i - sta.top().ind - 1));
}
sta.push((node){i, heights[i]});
}
while (sta.size() != 1) {
node temp = sta.top();
sta.pop();
ans = max(ans, temp.h * ((int)heights.size() - sta.top().ind - 1));
}
return ans;
}
};
类似 接雨水 42
逛街
前几年的 笔试常考的 一般第二题
一人为中心，左边单调递减，右边单调递增
解法：
从左向右，求一个单调递减的栈 （元素不满足递减时，出栈元素再入栈）
从右向左，求一个单调递减的栈
单调队列
双端队列，从尾入 从尾出
滑动窗口
单调递增的队列 最小值
单调递减的队列 最大值
题目描述
给出一个长度为 NN 的数组，一个长为 KK 的滑动窗口从最左移动到最右，每次窗口移动，如下图：
找出窗口在各个位置时的极大值和极小值。
#include <iostream>
#include <deque>
using namespace std;
struct node {
int ind, val;
};
int n, k, num[300005], a1[300005], a2[300005];
int main() {
cin >> n >> k;
deque<node> mmin, mmax;
for (int i = 1; i <= n; i++) {
cin >> num[i];
while (!mmin.empty() && mmin.back().val > num[i]) { //维护递增
mmin.pop_back();
}
mmin.push_back((node){i, num[i]});
if (mmin.front().ind + k <= i) { //维护最小值
mmin.pop_front();
}
while (!mmax.empty() && mmax.back().val < num[i]) { //维护递减
mmax.pop_back();
}
mmax.push_back((node){i, num[i]});
if (mmax.front().ind + k <= i) { //维护最大值
mmax.pop_front();
}
if (i >= k) { //入答案数组
a1[i] = mmin.front().val;
a2[i] = mmax.front().val;
}
}
for (int i = k; i <= n; i++) {
if (i != k) cout << " ";
cout << a1[i];
}
cout << endl;
for (int i = k; i <= n; i++) {
if (i != k) cout << " ";
cout << a2[i];
}
cout << endl;
return 0;
}
常见做题技巧 P6
动态规划 DP
递推解动态规划
1、大问题 可以 分解为 小问题 (最优子结构)
2、无后效性
方法：
1、观察 大问题可以分解为小问题
2、状态定义 数组如何定义
3、状态转移 转移方程
4、初始化
零钱兑换
贪心不成立
递推求解 从1推到21
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> ans(amount + 1, INT_MAX / 2); //初始化为INT_MAX / 2
ans[0] = 0;
for (int i = 1; i <= amount; i++) {
for (auto x : coins) {
if (i >= x) {
ans[i] = min(ans[i], ans[i - x] + 1);
}
}
}
if (ans[amount] == INT_MAX / 2) return -1;
return ans[amount];
}
};
打家劫舍
ans[x] 到 x 的 最大钱数
ans[i] = max(ans[i - 1], ans[i - 2] + nums[i - 1]);
class Solution {
public:
int rob(vector<int>& nums) {
vector<int> ans(nums.size() + 1, 0);
ans[1] = nums[0];
for (int i = 2; i <= nums.size(); i++) {
ans[i] = max(ans[i - 1], ans[i - 2] + nums[i - 1]);
}
return ans[nums.size()];
}
};
最长递增子序列 LIS
ans[x] 以x为结尾的最长递增序列的长度
ans[x] = max(ans[1] ~ ans[x]) + 1
时间复杂度O(N^2)
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> ans(nums.size(), 1);
int mmax = 0;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
ans[i] = max(ans[i], ans[j] + 1);
}
}
mmax = max(mmax, ans[i]);
}
return mmax;
}
};
时间复杂度O(NlogN)
贪心的思想
维护一个ans 数组 (数组里的元素无意义，数组长度是所求)
如果遇到更大的元素直接放最后面
否则，与前面的元素进行替换 (找第一个大于它的进行替换) 类似//00001111
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> ans;
for (auto x : nums) {
if (ans.empty() || x > ans[ans.size() - 1]) {
ans.push_back(x);
} else {
//00001111
int l = 0, r = ans.size() - 1;
while (l != r) {
int mid = (l + r) / 2;
if (ans[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
ans[l] = x;
}
}
return ans.size();
}
};
最长公共子序列 LCS
正解：ans[i][j] 表示 从 0 ~ i 和 从 0 ~ j 的最长公共子序列
if (s1[i] == s[j]) ans[i][j] = 1 + ans[i - 1][j - 1]
else ans[i][j] = max(ans[i - 1][j], ans[i][j - 1])
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n = text1.size(), m = text2.size();
vector<vector<int> > ans(n + 1, vector<int>(m + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (text1[i - 1] == text2[j - 1]) {
ans[i][j] = 1 + ans[i - 1][j - 1];
} else {
ans[i][j] = max(ans[i - 1][j], ans[i][j - 1]);
}
}
}
return ans[n][m];
}
};
练习题4：0/1背包
0/1 物品最多拿一次
ans[x][y] 用前X件物品去装上限为Y的背包能获得的最大价值
anx[x - 1][y] 不装/装不下 ans[x - 1][y] 装 w[x] + ans[x - 1][y - v[x]] w[x] 价值 v[x] 空间
0/1背包 本状态 基于 前 i - 1件的状态
#include <iostream>
using namespace std;
int n, v[105], w[105], ans[105][10005], m;
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) { //遍历所有空间
if (v[i] <= j) {
ans[i][j] = max(ans[i - 1][j], w[i] + ans[i - 1][j - v[i]]); //装了v[i], 去前i - 1件物品状上限为 j-v[i] 的最大价值
} else {
ans[i][j] = ans[i - 1][j];
}
}
}
cout << ans[n][m] << endl;
return 0;
}
滚动数组
#include <iostream>
using namespace std;
int n, v[105], w[105], ans[10005], m;
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= n; i++) // 遍历所有物品
for (int j = m; j >= v[i]; j--) //遍历所有空间 装第 i 件物品
ans[j] = max(ans[j], w[i] + ans[j - v[i]]); //滚动数组 从后向前更新
cout << ans[m] << endl;
return 0;
}
练习题5：完全背包
物品无限多
ans[x][y] 用前X件物品去装上限为Y的背包能获得的最大价值
anx[x - 1][y] 不装/装不下 ans[x - 1][y] 装 w[x] + ans[x][y - v[x]] w[x] 价值 v[x] 空间
完全背包 本状态 基于 本层的状态
滚动数组 从前向后
#include <iostream>
using namespace std;
int n, m, v[10005], w[10005], ans[10005];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> v[i] >> w[i];
}
for (int i = 1; i <= n; i++) // 遍历所有物品
for (int j = 1; j <= m; j++) //遍历所有空间 装第 i 件物品
if(v[i] <= j)
ans[j] = max(ans[j], w[i] + ans[j - v[i]]); //滚动数组 从前向后更新
cout << ans[m] << endl;
return 0;
}
练习题6：多重背包
物品的数量有限多
将数量拆成 2的次方数 n 降为 logn 如：100 1 2 4 8 16 32 …
问题转换为 0/1 背包问题
#include <iostream>
using namespace std;
int n, v[10005], w[10005], ans[10000005], m, cnt = 1;
int v1[105], w1[105], s1[105];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> v1[i] >> w1[i] >> s1[i];
}
for (int i = 1; i <= n; i++) {
int log = 1;
while (s1[i]) {
if (s1[i] < log) {
v[cnt] = v1[i] * s1[i];
w[cnt++] = w1[i] * s1[i];
s1[i] = 0;
} else {
v[cnt] = v1[i] * log;
w[cnt++] = w1[i] * log;
s1[i] -= log;
log *= 2;
}
}
}
cnt--;
for (int i = 1; i <= cnt; i++) // 遍历所有物品
for (int j = m; j >= v[i]; j--) //遍历所有空间 装第 i 件物品
ans[j] = max(ans[j], w[i] + ans[j - v[i]]); //滚动数组 从后向前更新
cout << ans[m] << endl;
return 0;
}