Terminus

给一个图的邻接矩阵，求连通分量。 原题链接 12345678910111213141516171819202122232425262728293031class Solution {public: void dfs(vector<vector<int>>& isConnected, vector<int>& visited, int n, int i) { // 枚举所有城市，看和 i 这个城市是否相连 for (int j = 0; j < n; j++) { // 如果城市 j 与城市 i 相连且还没被访问过 if (isConnected[i][j] == 1 && !visited[j]) { // 标记访问 visited[j] = 1; // 去城市 j 进行深度搜索 ...

原题链接 Floyd 算法，求两点间的最短路径的一种算法。 把两个字母看做图的节点，把两个字母相除的商看做两个点之间的路径权值。问题是求给定两点之间是否有路径，并计算出权值。 1234567891011121314151617181920212223242526272829303132class Solution {public: vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) { unordered_set<string> vers; unordered_map<string, unordered_map<string, double>> d; for(int i=0;i<equations. ...

先看如何用暴力法实现。 再分析是否有单调关系。 最后利用单调关系，套用双指针模板，将复杂度降低一个 n。 模板结构为 for 循环里面一个 while。 1234567891011121314151617181920212223#include <iostream>using namespace std;const int N = 100010;int a[N], s[N];int main() { int n; cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; int res = 0; for (int i = 0, j = 0; i < n; i++) { s[a[i]]++; while (s[a[i]] > 1) { s[a[j]]--; j++; } res = max(res, i - j + 1); } cout << res; return ...

离散化适用于数据的值域很大，但数量少的情况。可以将数据映射到 1, 2, 3, …, n。 对数组进行排序去重 123456789101112sort(alls.begin(), alls.end());alls.erase(unique(alls.begin(), alls.end()), alls.end());// 求 x 这个值离散化之后的结果int find(int x) { int l=0, r=alls.size()-1; while(l<r) { int mid = l+r>>1; if(x>=alls[mid]) r=mid; else l = mid+1; } return r+1; // 映射到 1, 2, 3, ..., n} 区间和 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include <iostream>#include ...

原题链接 1234567891011121314151617181920class Solution {public: bool canPlaceFlowers(vector<int>& f, int n) { for (int i = 0, len = f.size(); i < len && n > 0;) { // 从花坛第一个位置开始扫描 if (f[i] == 1) { // 如果当前种了花，往前跳 2 格，因为无论下一格是 0 还是 1，都不可能再种 i += 2; } else if (i == len - 1 || f[i + 1] == 0) { // 如果当前位置没种花，而且，是最后一个位置或者下一个位置没有种花，就可以在当前格子种 n--; i += 2; } else { // 当前位置没种花，但是下一 ...

快速排序模板 1234567891011121314151617181920212223242526272829#include <iostream>using namespace std;const int N = 1e6 + 10;int q[N];int n;void quick_sort(int l, int r) { if(l>=r) return; int i = l-1, j = r+1; int p = q[(l+r)/2]; while(i<j) { while(q[++i]<p); while(q[--j]>p); if(i<j) swap(q[i], q[j]); } quick_sort(l, j); quick_sort(j+1, r);}int main() { scanf("%d", &n); for(int i=0;i<n;i++) s ...

归并排序模板 1234567891011121314151617181920212223242526272829#include <iostream>using namespace std;const int N = 1e6 + 10;int q[N];int tmp[N];void merge_sort(int q[], int l, int r) { if(l>=r) return; int mid = l + r >> 1; merge_sort(q, l, mid); merge_sort(q, mid+1, r); int k=0, i=l, j=mid+1; while(i<=mid && j<=r) { if(q[i]<=q[j]) tmp[k++] = q[i++]; else tmp[k++] = q[j++]; } while(i<=mid) tmp[k++] = q[i++]; whi ...

一维差分 差分是前缀和的逆运算，差分数组的作用是在 O(1) 的时间复杂度内，对原数组中某一段区间 [l, r] 内的所有数加上一个固定的值。 给定数组 a1,a2,...,ana_1, a_2, ... , a_na1​,a2​,...,an​（前缀和） 构造 b1,b2,...,bnb_1, b_2, ... , b_nb1​,b2​,...,bn​（差分） 使得 ai=b1+b2+...+bia_i = b_1 + b_2 + ... + b_iai​=b1​+b2​+...+bi​ 构造方式 b1=a1b_1 = a_1b1​=a1​ b2=a2−a1b_2 = a_2 - a_1b2​=a2​−a1​ b3=a3−a2b_3 = a_3 - a_2b3​=a3​−a2​ … bn=an−an−1b_n = a_n - a_{n-1}bn​=an​−an−1​ 可以在 O(n)O(n)O(n) 的时间复杂度内由 {bn}\{b_n\}{bn​} 得到 {an}\{a_n\}{an​} 12345678910111213141516171819202122232425#incl ...

前缀和的作用是快速求数组中一段区间内的所有数之和。 Sj−Si−1=ai+...+ajS_j - S_{i-1} = a_i + ... + a_jSj​−Si−1​=ai​+...+aj​ 程序实现上，前缀和数组下标从 1 开始，因为求 [1, x] 之间的和，可以通过 S[x] - S[0] 计算，不必特判 1。 12345678910111213141516171819202122#include <iostream>using namespace std;const int N = 100010;int a[N];int s[N];int main() { // 让 cin 更快，副作用是不能再使用 scanf ios::sync_with_stdio(false); int n, m; cin >> n >> m; for(int i=1;i<=n;i++) cin >> a[i]; for(int i=1;i<=n;i++) { s[i]=s[i ...

高精度计算时要把数据存入数组，先存低位，因为当发生进位时，向数组最后一个元素后增加元素是非常容易的。 高精度加法模板： 1234567891011121314151617181920212223242526272829#include <iostream>#include <vector>using namespace std;vector<int> add(vector<int>& A, vector<int>& B) { vector<int> C; int t = 0; for(int i=0; i<A.size() || i<B.size();i++) { if(i<A.size()) t+=A[i]; if(i<B.size()) t+=B[i]; C.push_back(t%10); t/=10; } if(t) C.push_back(1); ...