- 博客(130)
- 收藏
- 关注
RSS订阅翻译 正则表达式匹配规则
匹配任意字符精确匹配实际上用处不大，因为我们直接用String.equals()就可以做到。大多数情况下，我们想要的匹配规则更多的是模糊匹配。我们可以用.匹配一个任意字符。例如，正则表达式a.c中间的.可以匹配一个任意字符，例如，下面的字符串都可以被匹配："abc"，因为.可以匹配字符b；"a&c"，因为.可以匹配字符&；"acc"，因为.可以匹配字符c。但它不能匹配"ac"、“a&&c”，因为.匹配一个字符且仅限一个字符。匹配数字用.可以匹配任意字符，这个
2022-03-10 14:41:57
2987
2
翻译 JAVA接口与抽象类的区别和联系
接口和抽象类在抽象类中，抽象方法本质上是定义接口规范：即规定高层类的接口，从而保证所有子类都有相同的接口实现，这样，多态就能发挥出威力。如果一个抽象类没有字段，所有方法全部都是抽象方法：abstract class Person { public abstract void run(); public abstract String getName();}就可以把该抽象类改写为接口：interface。在Java中，使用interface可以声明一个接口：interface
2022-02-25 09:33:51
343
翻译 JAVA多态
多态引用变量的声明类型可能与其实际类型不符Person p = new Student();现在，我们考虑一种情况，如果子类覆写了父类的方法：public class Main { public static void main(String[] args) { Person p = new Student(); p.run(); // 应该打印Person.run还是Student.run? }}class Person { publ
2022-02-24 16:35:56
165
原创 acwing算法基础课：Huffman树（合并果子）
Huffman树：合并果子在一个果园里，达达已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。达达决定把所有的果子合成一堆。每一次合并，达达可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以达达在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使达i耗
2021-11-12 20:19:37
95
原创 acwing算法基础课：贪心（区间选点）
数位统计dp：计数问题给定两个整数a和b，求a和b之间的所有数字中0~9的出现次数。例如，a=1024，b=1032，则a和b之间共有9个数如下:1024、1025、1026、1027、1028、1029、1030、1031、1032其中0’出现10次，‘1’出现10次，‘2’出现7次，"3’出现3次等等…测试样例输入样例：输出样例：...
2021-11-12 19:47:14
429
原创 acwing算法基础课：区间DP（石子合并）
区间DP:石子合并设有N堆石子排成—排，其编号为1，2，3,…，N。每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。例如有4堆石子分别为1352，我们可以先合并1、2堆，代价为4，得到452，又合并1，2堆，代价为9，得到92，再合并得到11，总代价为4+9+11=24;如果第二步是先合并2，3堆，则代价为7，得到47，最后
2021-11-11 17:07:18
204
原创 acwing算法基础课：线性DP(最长公共子序列)
线性dp：最长公共子序列给定两个长度分别为N和M的字符串A和B，求既是A的子序列又是B的子序列的字符串长度最长是多少。#include <iostream>using namespace std;const int N = 1010;int n, m;char a[N], b[N];int f[N][N];int main(){ cin >> n >> m; cin >> a + 1 >> b + 1; for(
2021-11-09 19:43:14
112
原创 acwing算法基础课：线性DP(最长上升子序列)
线性dp：最长上升子序列给定一个长度为N的数列，求数值严格单调递增的子序列的长度最长是多少。#include <iostream>using namespace std;const int N = 1010;int n;int a[N], f[N];int main(){ cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i+
2021-11-08 19:49:43
89
原创 acwing算法基础课：线性DP(数字三角形)
线性dp：数字三角形给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。73 88 1 02 7 4 44 5 2 6 5#include <iostream>using namespace std;const int N = 1010, INF = 1e9;int n;int a[N][N];int f[N][N];int main(){ cin
2021-11-06 22:44:04
95
原创 acwing算法基础课：背包问题（分组背包问题）
分组背包问题有N组物品和一个容量是V的背包。每组物品有若干个，同一组内的物品最多只能选一个。每件物品的体积是vij，价值是 wij，其中i是组号，j是组内编号。求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。输出最大价值。#include <iostream>using namespace std;const int N = 110;int n, m;int v[N][N], w[N][N], s[N];int f[N];int main(){
2021-11-05 20:14:23
141
原创 acwing算法基础课：背包问题（多重背包问题）
多重背包问题有N种物品和一个容量是V的背包。第i种物品最多有si 件，每件体积是vi，价值是wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。#include <iostream>using namespace std;const int N = 110;int n, m;int v[N], w[N], s[N];int f[N][N];int main(){ cin >> n >> m; f
2021-11-03 20:45:08
176
原创 acwing算法基础课：背包问题（完全背包问题）
完全背包问题有N种物品和一个容量是V的背包，每种物品都有无限件可用。第i种物品的体积是vi，价值是wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。#include <iostream>using namespace std;const int N = 1010;int n, m;int v[N], w[N];int f[N][N];int main(){ cin >> n >> m; fo
2021-11-02 19:50:13
122
原创 acwing算法基础课：背包问题（01背包）
01背包问题有N件物品和一个容量是V的背包。每件物品只能使用一次。第i件物品的体积是vi，价值是wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。#include <iostream>using namespace std;const int N = 100;int n, m;int v[N], w[N];int f[N][N];int main(){ cin >> n >> m; for(
2021-11-02 19:06:58
135
原创 acwing算法基础课：试除法分解质因数
试除法分解质因数模板分解质因数在数学领域的意思是：任何一个合数都可以写成几个质数相乘的形式。其中每个质数都是这个合数的因数，叫做这个合数的分解质因数。分解质因数只针对合数。例:12=2x2x3。void divide(int x){ for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { int s = 0; while (x % i == 0) x /= i
2021-10-30 19:49:30
148
原创 acwing算法基础课：试除法判定质数
试除法判定质数模板bool is_prime(int x){ if (x < 2) return false; for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) return false; return true;}
2021-10-30 19:18:34
64
原创 acwing算法基础课：二分图算法（匈牙利算法）
匈牙利算法模板时间复杂度是 O(nm), n 表示点数，m表示边数int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个bool st[N]; // 表示第二个集合中的每个点是否已经被遍
2021-10-29 20:24:37
153
原创 acwing算法基础课：二分图算法（染色法判别二分图算法）
染色法判别二分图模板时间复杂度是 O(n+m), n 表示点数，m表示边数int n; // n表示点数int h[N], e[M], ne[M], idx; // 邻接表存储图int color[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色// 参数：u表示当前节点，c表示当前点的颜色bool dfs(int u, int c){ color[u] = c; for (int i = h[u]; i != -1; i
2021-10-28 19:35:42
168
原创 acwing算法基础课：最小生成树算法（Kruskal算法）
Kruskal算法模版时间复杂度是 O(mlogm), n 表示点数，m表示边数int n, m; // n是点数，m是边数int p[N]; // 并查集的父节点数组struct Edge // 存储边{ int a, b, w; bool operator< (const Edge &W)const { return w < W.w; }}edges[M];int find(int
2021-10-27 19:59:52
296
原创 acwing算法基础课：最小生成树算法（朴素版prim算法）
朴素版prim算法模版时间复杂度是 O(n2+m), n 表示点数，m表示边数int n; // n表示点数int g[N][N]; // 邻接矩阵，存储所有边int dist[N]; // 存储其他点到当前最小生成树的距离bool st[N]; // 存储每个点是否已经在生成树中// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和int prim(){ memset(dist, 0x3f
2021-10-26 19:22:01
166
原创 acwing算法基础课：最短路算法（floyd算法）
floyd算法模版时间复杂度是 O(n3), n表示点数初始化： for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF;// 算法结束后，d[a][b]表示a到b的最短距离void floyd(){ for (int k = 1; k <=
2021-10-25 20:43:14
267
原创 acwing算法基础课：最短路算法（spfa判断负环算法）
spfa判断负环算法模版spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环时间复杂度是 O(nm), n 表示点数，m表示边数int n; // 总点数int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数bool st[N]; // 存储每个点是否
2021-10-25 19:58:24
201
原创 acwing算法基础课：最短路算法（spfa算法）
spfa算法模版时间复杂度 平均情况下 O(m)，最坏情况下 O(nm), n 表示点数，m表示边数int n; // 总点数int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边int dist[N]; // 存储每个点到1号点的最短距离bool st[N]; // 存储每个点是否在队列中// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1int spfa(){ memset(
2021-10-24 20:10:52
209
原创 acwing算法基础课：最短路算法（Bellman-Ford算法）
Bellman-Ford算法时间复杂度 O(nm), n 表示点数，m表示边数注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。int n, m; // n表示点数，m表示边数int dist[N]; // dist[x]存储1到x的最短路距离struct Edge // 边，a表示出点，b表示入点，w表示边的权重{ int a, b, w;}edges[M];// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
2021-10-22 21:57:37
170
原创 acwing算法基础课：最短路算法（堆优化dijkstra算法）
堆优化dijkstra算法模版时间复杂度 O(mlogn), n 表示点数，m表示边数typedef pair<int, int> PII;int n; // 点的数量int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边int dist[N]; // 存储所有点到1号点的距离bool st[N]; // 存储每个点的最短距离是否已确定// 求1号点到n号点的最短距离，如果不存在，则返回-1i
2021-10-21 20:57:34
198
原创 acwing算法基础课：最短路算法（朴素dijkstra算法）
朴素dijkstra算法模板int g[N][N]; // 存储每条边int dist[N]; // 存储1号点到每个点的最短距离bool st[N]; // 存储每个点的最短路是否已经确定// 求1号点到n号点的最短路，如果不存在则返回-1int dijkstra(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n - 1; i ++ ) {
2021-10-18 20:51:08
129
原创 acwing算法基础课：拓扑排序
拓扑排序模板有向无环图才有拓扑序列，并且拓扑序不一定唯一时间复杂度 O(n+m), n 表示点数，m表示边数bool topsort(){ int hh = 0, tt = -1; // d[i] 存储点i的入度 for (int i = 1; i <= n; i ++ ) if (!d[i]) q[ ++ tt] = i; while (hh <= tt) { int t = q[hh
2021-10-17 22:01:51
252
原创 C语言函数指针
函数指针 先解释void (*func)(int)：void func()->void func(int)->void *func(int)->void (*func)(int)上面的图示能看明白吧？func是一个函数指针，它的返回类型为空，它所指向的函数接收一个int型的参数。若是写成void *func(int)则变成了:func是一个函数，它的返回类型是空指针，它接受一个int型参数。所以void (*signal(int sinno,void(*func)(int)))
2021-10-16 11:16:43
398
原创 acwing算法基础课：树与图的搜索（宽度优先遍历）
宽度优先遍历模板queue<int> q;st[1] = true; // 表示1号点已经被遍历过q.push(1);while (q.size()){ int t = q.front(); q.pop(); for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true; //
2021-10-15 20:25:06
158
原创 acwing算法基础课：树与图的遍历（深度优先遍历）
深度优先遍历模板时间复杂度 O(n+m), n 表示点数，m表示边数int dfs(int u){ st[u] = true; // st[u] 表示点u已经被遍历过 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) dfs(j); }}例题给定一颗树，树中包含n个结点(编号1~n)和n-1条无向边。请你找到树的重心，并输出将重心删除后，
2021-10-15 19:33:08
151
原创 acwing算法基础课：树与图的存储
树与图的存储模板树是一种特殊的无环连通图(1) 邻接矩阵：g[a][b] 存储边a->b(2) 邻接表：// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点int h[N], e[N], ne[N], idx;// 添加一条边a->bvoid add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}// 初始化idx = 0;memset(h, -1,
2021-10-14 20:41:19
160
原创 acwing算法基础课：BFS
BFS模板使用数据结构队列，最短路径queue<int> q;st[1] = true; // 表示1号点已经被遍历过q.push(1);while (q.size()){ int t = q.front(); q.pop(); for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j]
2021-10-12 20:22:07
277
原创 acwing算法基础课：DFS
DFS模板int dfs(int u){ st[u] = true; // st[u] 表示点u已经被遍历过 for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) dfs(j); }}例题n-皇后问题是指将n今皇后放在n*n的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。#include <iost
2021-10-08 11:08:43
136
原创 acwing算法基础课：哈希表
一般哈希表模板(1) 拉链法 int h[N], e[N], ne[N], idx; // 向哈希表中插入一个数 void insert(int x) { int k = (x % N + N) % N; e[idx] = x; ne[idx] = h[k]; h[k] = idx ++ ; } // 在哈希表中查询某个数是否存在 bool find(int x) {
2021-09-27 12:59:30
219
原创 acwing算法基础课：堆
堆模板堆是一个完全二叉树，左右节点都小于父节点// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1// ph[k]存储第k个插入的点在堆中的位置// hp[k]存储堆中下标是k的点是第几个插入的int h[N], ph[N], hp[N], size;// 交换两个点，及其映射关系void heap_swap(int a, int b){ swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]);
2021-09-26 21:12:16
105
原创 acwing算法基础课：并查集
并查集模板作用：1.将两个集合合并2.询问两个元素是否在同一个集合中近乎O(1)时间复杂度完成上述操作基本原理：每个集合用一棵树表示，树根的编号就是整个集合的编号。每个节点存储它的父节点，p[x]表示x的父节点(1)朴素并查集： int p[N]; //存储每个点的祖宗节点 // 返回x的祖宗节点 int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x];
2021-09-13 21:02:41
161
原创 acwing算法基础课：Trie树
Trie树模板int son[N][26], cnt[N], idx;// 0号点既是根节点，又是空节点// son[][]存储树中每个节点的子节点// cnt[]存储以每个节点结尾的单词数量// 插入一个字符串void insert(char *str){ int p = 0; for (int i = 0; str[i]; i ++ ) { int u = str[i] - 'a'; if (!son[p][u]) son[p][u
2021-09-13 18:33:32
127
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人