Template
Frequent Template
Shortest Path最短路径
Dijkstra
class Solution {
public:
vector<int> getPath(vector<int>& path, int src, int tar) { //nodes from 1 -> n;
vector<int> nodeSeq;
int cur = tar;
while (path[cur] != -1) {
nodeSeq.emplace_back(cur);
cur = path[cur];
}
nodeSeq.emplace_back(src);
reverse(nodeSeq.begin(), nodeSeq.end());
return nodeSeq;
}
int networkDelayTime(vector<vector<int>>& times, int n, int src) { //nodes from 1 -> n;
const int Inf = INT_MAX / 2;
vector<vector<int>> graph(n, vector<int> (n, Inf));
for (const auto& edge: times) {
int from = edge[0] - 1, to = edge[1] - 1, cost = edge[2];
graph[from][to] = cost;
}
for (int i = 0; i < n; ++i) {
graph[i][i] = 0;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<int> dist(n, Inf);
vector<bool> visited(n, false);
vector<int> path(n, -1);
pq.emplace(0, src - 1);
dist[src - 1] = 0;
while (!pq.empty()) {
pair<int, int> p = pq.top(); pq.pop();
int cur = p.second;
if (visited[cur]) {//add visited array to avoid useless traversal
continue;
}
visited[cur] = true;
for (int i = 0; i < n; ++i) {
if (dist[i] > dist[cur] + graph[cur][i]) {
dist[i] = dist[cur] + graph[cur][i];
pq.emplace(dist[i], i);
path[i] = cur;
}
}
}
vector<int> pathNodes = getPath(path, src - 1);
for (auto node: pathNodes)
cout << node + 1 << ' ';
int maxDistance = *max_element(dist.begin(), dist.end());
return maxDistance == Inf ? -1 : maxDistance;
}
};Floyd
vector<int> getPath();
int Floyd(vector<vector<int>>& times, int n, int src) { //nodes from 1 -> n;
const int Inf = INT_MAX / 2;
vector<vector<int>> graph(n, vector<int> (n, Inf));
for (int i = 0; i < n; ++i) {
graph[i][i] = 0;
}
for (const auto& edge: times) {
int from = edge[0] - 1, to = edge[1] - 1, cost = edge[2];
graph[from][to] = cost;
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
int maxDistance = *max_element(graph[src - 1].begin(), graph[src - 1].end());
return maxDistance == Inf ? -1 : maxDistance;
}SPFA
int SPFA(vector<vector<int>>& edges, int n, int src) { //nodes from 1 -> n;
const int Inf = INT_MAX / 2;
vector<vector<int>> graph(n, vector<int> (n, Inf));
for (int i = 0; i < n; ++i) {
graph[i][i] = 0;
}
for (const auto& edge: edges) {
int from = edge[0] - 1, to = edge[1] - 1, cost = edge[2];
graph[from][to] = cost;
}
vector<int> dist(n, Inf);
vector<bool> inQ(n, false);
dist[src - 1] = 0;
inQ[src - 1] = true;
queue<int> Q;
Q.emplace(src - 1);
while (!Q.empty()) {
int cur = Q.front(); Q.pop();
inQ[cur] = false;
for (int i = 0; i < n; ++i) {
if (dist[i] > dist[cur] + graph[cur][i]) {
dist[i] = dist[cur] + graph[cur][i];
if (!inQ[i]) {
Q.emplace(i);
inQ[i] = true;
}
}
}
}
int maxDistance = *max_element(dist.begin(), dist.end());
return maxDistance == Inf ? -1 : maxDistance;
}```
## Minimum Spanning Tree最小生成树
### Prim
```cpp
int Prim(vector<vector<int>>& edges, int n) {
const int Inf = INT_MAX / 2;
vector<vector<int>> graph(n, vector<int> (n, Inf));
for (int i = 0; i < n; ++i) {
graph[i][i] = 0;
}
for (const auto& edge: edges) {
int p1 = edge[0] - 1, p2 = edge[1] - 1, cost = edge[2];
graph[p1][p2] = graph[p2][p1] = cost;
}
vector<bool> visited(n, false);
vector<int> dist(n, Inf);
dist[0] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.emplace(0, 0);
int res = 0;
int connectedNum = 0;
while(!pq.empty()) {
pair<int, int> p = pq.top(); pq.pop();
int cur = p.second;
if (visited[cur]) {
continue;
}
++connectedNum;
res += p.first;
visited[cur] = true;
for (int i = 0; i < n; ++i) {
if (dist[i] > graph[cur][i]) {
dist[i] = graph[cur][i];
pq.emplace(dist[i], i);
}
}
}
return n == connectedNum ? res : - 1;
}UnionFind并查集
class UnionFind {
public:
UnionFind(int n): rank(n, 1) {
parent.reserve(n);
for (int i = 0; i < n; ++i) {
parent.emplace_back(i);
}
}
bool IsConnected(int x, int y) {
return find(x) == find(y);
}
bool Unite(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX == rootY) {
return false;
}
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootX] = rootY;
++rank[rootY];
}
return true;
}
private:
int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
vector<int> parent;
vector<int> rank;
};Kruskal
class UnionFind {
public:
UnionFind(int n) {
parent.resize(n);
rank.resize(n);
for (int i = 0; i < n; ++i) {
parent[i] = i;
rank[i] = 1;
}
}
int find(int i) {
if (i != parent[i]) {
parent[i] = find(parent[i]);
}
return parent[i];
}
bool unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] <= rank[rootY]) {
if (rank[rootX] == rank[rootY]) {
++rank[rootY];
}
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
}
return true;
}
return false;
}
private:
vector<int> parent;
vector<int> rank;
};
int Kruskal(vector<vector<int>>& edges, int n) {
sort(edges.begin(), edges.end(), [](const vector<int>& edge1, const vector<int>& edge2) {
return edge1[2] < edge2[2];
});
int connectedNum = 1;
int res = 0;
UnionFind uf(n);
for (const auto& edge: edges) {
int p1 = edge[0] - 1, p2 = edge[1] - 1, cost = edge[2];
if (uf.unite(p1, p2)) {
res += cost;
++connectedNum;
}
}
return connectedNum == n ? res : -1;
}int SPFA(vector<vector<int>>& edges, int n, int src) { //nodes from 1 -> n;
const int Inf = INT_MAX / 2;
vector<vector<int>> graph(n, vector<int> (n, Inf));
for (int i = 0; i < n; ++i) {
graph[i][i] = 0;
}
for (const auto& edge: edges) {
int from = edge[0] - 1, to = edge[1] - 1, cost = edge[2];
graph[from][to] = cost;
}
vector<int> dist(n, Inf);
vector<bool> inQ(n, false);
dist[src - 1] = 0;
inQ[src - 1] = true;
queue<int> Q;
Q.emplace(src - 1);
while (!Q.empty()) {
int cur = Q.front(); Q.pop();
inQ[cur] = false;
for (int i = 0; i < n; ++i) {
if (dist[i] > dist[cur] + graph[cur][i]) {
dist[i] = dist[cur] + graph[cur][i];
if (!inQ[i]) {
Q.emplace(i);
inQ[i] = true;
}
}
}
}
int maxDistance = *max_element(dist.begin(), dist.end());
return maxDistance == Inf ? -1 : maxDistance;
}Segment Tree线段树
区间加法
tag[]表示加法懒标记
//add to the interval block
#include<bits/stdc++.h>
using namespace std;
int n, m;
typedef long long ll;
const int MAXN = 1e5 + 10;
ll arr[MAXN], sum[MAXN<<2], tag[MAXN<<2];
inline int lc(int p) {
return p << 1;
}
inline int rc(int p) {
return p << 1 | 1;
}
void pushUp(int p) {
sum[p] = sum[lc(p)] + sum[rc(p)];
}
void build(int p, int l, int r) {
if (l == r) {
sum[p] = arr[l];
return;
}
int mid = ((r - l) >> 1) + l;
build(lc(p), l, mid);
build(rc(p), mid + 1, r);
pushUp(p);
}
void lazy(int p, ll val, int l, int r) {
tag[p] += val;
sum[p] += val * (r - l + 1);
}
void pushDown(int p, int l, int r) {
int mid = ((r - l) >> 1) + l;
lazy(lc(p), tag[p], l, mid);
lazy(rc(p), tag[p], mid + 1, r);
tag[p] = 0;
}
void update(int p, ll val, int updateL, int updateR, int l, int r) {
if (updateL <= l && r <= updateR) {
lazy(p, val, l, r);
return;
}
int mid = ((r - l) >> 1) + l;
if (tag[p] != 0) {
pushDown(p, l, r);
}
if (updateL <= mid) update(lc(p), val, updateL, updateR, l, mid);
if (updateR > mid) update(rc(p), val, updateL, updateR, mid + 1, r);
pushUp(p);
}
ll query(int p, int queryL, int queryR, int l, int r) {
if (queryL <= l && r <= queryR) {
return sum[p];
}
int mid = ((r - l) >> 1) + l;
if (tag[p] != 0) {
pushDown(p, l, r);
}
ll res = 0;
if (queryL <= mid) res += query(lc(p), queryL, queryR, l, mid);
if (queryR > mid) res += query(rc(p), queryL, queryR, mid + 1, r);
return res;
}
int main() {
int l, r;
ll val;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &arr[i]);
}
build(1, 1, n);
while (m--) {
int choice; cin >> choice;
if (choice == 1) {
scanf("%d%d%lld", &l, &r, &val);
update(1, val, l, r, 1, n);
} else if (choice == 2) {
scanf("%d%d", &l, &r);
printf("%lld\n",query(1, l, r, 1, n));
}
}
return 0;
}区间乘法和加法
mul[]和add[]
#include<bits/stdc++.h>
using namespace std;
int n, m, mod;
typedef long long ll;
const int MAXN = 1e5 + 10;
ll arr[MAXN], sum[MAXN<<2], add[MAXN<<2], mul[MAXN<<2];
inline int lc(int p) {
return p << 1;
}
inline int rc(int p) {
return p << 1 | 1;
}
void pushUp(int p) {
sum[p] = (sum[lc(p)] + sum[rc(p)]) % mod;
}
void build(int p, int l, int r) {
mul[p] = 1;
if (l == r) {
sum[p] = arr[l];
return;
}
int mid = ((r - l) >> 1) + l;
build(lc(p), l, mid);
build(rc(p), mid + 1, r);
pushUp(p);
}
void pushDown(int p, int l, int r) {
int mid = ((r - l) >> 1) + l;
sum[lc(p)] = (sum[lc(p)] * mul[p] + add[p] * (mid - l + 1)) % mod;
sum[rc(p)] = (sum[rc(p)] * mul[p] + add[p] * (r - mid)) % mod;
mul[lc(p)] = (mul[p] * mul[lc(p)]) % mod;
mul[rc(p)] = (mul[p] * mul[rc(p)]) % mod;
add[lc(p)] = (add[p] + add[lc(p)] * mul[p]) % mod;
add[rc(p)] = (add[p] + add[rc(p)] * mul[p]) % mod;
add[p] = 0;
mul[p] = 1;
}
void updateMul(int p, ll k, int updateL, int updateR, int l, int r) {
if (updateL <= l && r <= updateR) {
add[p] = (add[p] * k) % mod;
mul[p] = (mul[p] * k) % mod;
sum[p] = (sum[p] * k) % mod;
return;
}
int mid = ((r - l) >> 1) + l;
if (add[p] != 0 || mul[p] != 1) {
pushDown(p, l, r);
}
if (updateL <= mid) updateMul(lc(p), k, updateL, updateR, l, mid);
if (updateR > mid) updateMul(rc(p), k, updateL, updateR, mid + 1, r);
pushUp(p);
}
void updateAdd(int p, ll val, int updateL, int updateR, int l, int r) {
if (updateL <= l && r <= updateR) {
add[p] = (add[p] + val) % mod;
sum[p] = (sum[p] + val * (r - l + 1)) % mod;
return;
}
int mid = ((r - l) >> 1) + l;
if (add[p] != 0 || mul[p] != 1) {
pushDown(p, l, r);
}
if (updateL <= mid) updateAdd(lc(p), val, updateL, updateR, l, mid);
if (updateR > mid) updateAdd(rc(p), val, updateL, updateR, mid + 1, r);
pushUp(p);
}
ll query(int p, int queryL, int queryR, int l, int r) {
if (queryL <= l && r <= queryR) {
return sum[p];
}
int mid = ((r - l) >> 1) + l;
if (add[p] != 0 || mul[p] != 1) {
pushDown(p, l, r);
}
ll res = 0;
if (queryL <= mid) res += query(lc(p), queryL, queryR, l, mid) % mod;
if (queryR > mid) res += query(rc(p), queryL, queryR, mid + 1, r) % mod;
return res % mod;
}
int main() {
int l, r;
ll val;
cin >> n >> m >> mod;
for (int i = 1; i <= n; ++i) {
scanf("%lld", &arr[i]);
}
build(1, 1, n);
while (m--) {
int choice; cin >> choice;
if (choice == 1) {
scanf("%d%d%lld", &l, &r, &val);
updateMul(1, val, l, r, 1, n);
} else if (choice == 2) {
scanf("%d%d%lld", &l, &r, &val);
updateAdd(1, val, l, r, 1, n);
} else if (choice == 3) {
scanf("%d%d", &l, &r);
printf("%lld\n",query(1, l, r, 1, n));
}
}
return 0;
}Binary Indexed Tree数状数组
class BIT {
public:
BIT(int n) {
tree.resize(n + 1, 0);
}
static int lowBit(int x) {
return x & (-x);
}
void add(int x, int val) {
while (x < tree.size()) {
tree[x] += val;
x += lowBit(x);
}
}
int query(int x) { // sum from tree[1] to tree[x].
int res = 0;
while (x > 0) {
res += tree[x];
x -= lowBit(x);
}
return res;
}
int query(int l, int r) { // [l, r];
return query(r) - query(l - 1);
}
private:
vector<int> tree; //tree index from 1 -> n
};Quick Power/Multiply快速幂、快速乘
Quick Power
double binaryExponentiation(double x, long long n) {
if (n == 0) {
return 1.0;
}
double half = binaryExponentiation(x, n >> 1);
return n & 1? half * half * x : half * half;
}
double iteration(double x, long long n) {
double res = 1.0;
double xContribution = x;
while (n > 0) {
if (n & 1) {
res *= xContribution;
}
xContribution *= xContribution;
n >>= 1;
}
return res;
}Quick Multiply
long long quickMul(long long x, long long y) {
long long res = 0;
while (y != 0) {
if (y & 1) {
res += x;
}
x += x;
y >>= 1;
}
return res;
}数组排序
- 插入排序
- 选择排序
- 冒泡排序
- 快速排序
- 归并排序
void insertSort(vector<int>& nums) {
for (int i = 0; i < nums.size() - 1; ++i) {
int val = nums[i + 1];
int j = i + 1;
while (j > 0 && nums[j - 1] > val) {
nums[j] = nums[j - 1];
--j;
}
nums[j] = val;
}
}
void selectSort(vector<int>& nums) {
for (int i = 0; i < nums.size() - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < nums.size(); ++j) {
if (nums[j] < nums[minIndex]) {
minIndex = j;
}
}
swap(nums[minIndex], nums[i]);
}
}
void bubbleSort(vector<int>& nums) {
for (int i = nums.size() - 1; i >= 0; --i) {
bool isSorted = true;
for (int j = 0; j < i; ++j) {
if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]);
isSorted = false;
}
}
if (isSorted) {
break;
}
}
}
// 快速排序
int partiion(vector<int>& nums, int l, int r) {
int pivotValue = nums[r];
int p = l;
//保证p左边的值都小于pivotValue
for (int i = l; i < r; ++i) {
if (nums[i] < pivotValue) {
swap(nums[i], nums[p++]);
}
}
//将pivotValue放到中间的位置，此时 左边都小于，右边都大于。
swap(nums[p], nums[r]);
return p;
}
// find pivot, divide and conqure recursively
void quickSort(vector<int>& nums, int l, int r) {
if (l >= r) {
return ;
}
int pivotIndex = rand() % (r - l + 1) + l;
swap(nums[r], nums[pivotIndex]);
int m = partiion(nums, l, r);
quickSort(nums, l, m);
quickSort(nums, m + 1, r);
}
vector<int> quickSort(vector<int>& nums) {
quickSort(nums, 0, nums.size() - 1);
return nums;
}
// 归并排序
// 递归向下，保证左右两部分l、r数组有序，再进行归并。
// 和quickSort不同的是，这个先递归。利用
// 归并，要用到一个临时数组temp
void headSort(vector<int>& nums, vector<int>& temp, int l, int r) {
if (l >= r) {
return;
}
int m = (r - l) / 2 + l;
headSort(nums, temp, l, m);
headSort(nums, temp, m + 1, r);
int ptr = l;
int lPtr = l, rPtr = m + 1;
while (lPtr <= m && rPtr <= r) {
if (nums[lPtr] < nums[rPtr]) {
temp[ptr++] = nums[lPtr++];
} else {
temp[ptr++] = nums[rPtr++];
}
}
while (lPtr <= m) {
temp[ptr++] = nums[lPtr++];
}
while (rPtr <= r) {
temp[ptr++] = nums[rPtr++];
}
copy(temp.begin() + l, temp.begin() + r + 1, nums.begin() + l);
}
vector<int> sortArray(vector<int>& nums) {
vector<int> temp(nums.size());
headSort(nums, temp, 0, nums.size() - 1);
return nums;
}链表排序
- 归并排序
- 堆排序：但需要指定比较器，稍麻烦。
// mergeSort
// 1. 找中点
// 2. 划分l、r两部分链表，设置middle的next为nullptr
// 3. 递归分割l、r两部分，直到l、r两部分有序
// 4. 向上归并
ListNode* findMiddle(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode dummy(0, head);
ListNode* fast = &dummy;
ListNode* slow = &dummy;
while (fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode dummy;
ListNode* tail = &dummy;
while (head1 != nullptr && head2 != nullptr) {
if (head1->val < head2->val) {
tail->next = head1;
head1 = head1->next;
} else {
tail->next = head2;
head2 = head2->next;
}
tail = tail->next;
}
if (head1 != nullptr) {
tail->next = head1;
} else {
tail->next = head2;
}
return dummy.next;
}
ListNode* mergeSort(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
// 找中点，并划分l、r两部分
ListNode* middle = findMiddle(head);
ListNode* left = head, *right = middle->next;
middle->next = nullptr;
// 让l、r两部分有序
left = mergeSort(left);
right = mergeSort(right);
// 有序后，进行归并
return merge(left, right);
}Heap、堆、堆排序
核心操作是heapify，分为在数组最后的heapifyUp和在数组0下标进行的heapifyDown；
- Add时，插入到尾部，再heapifyUp
- delete时，将头部和尾部置换，为新的头部进行heapifyDown
class MinHeap {
private:
std::vector<int> heap;
// 从指定位置开始向上递归调整堆，维护小顶堆性质
void heapifyUp(int index) {
if (index == 0) {
return;
}
int parent = getParent(index);
if (heap[index] < heap[parent]) {
std::swap(heap[index], heap[parent]);
heapifyUp(parent); // 递归调整
}
}
// 从指定位置开始向下递归调整堆，维护小顶堆性质
void heapifyDown(int index) {
int leftChild = getLeftChild(index);
int rightChild = getRightChild(index);
int smallest = index;
if (leftChild < heap.size() && heap[leftChild] < heap[smallest]) {
smallest = leftChild;
}
if (rightChild < heap.size() && heap[rightChild] < heap[smallest]) {
smallest = rightChild;
}
if (smallest != index) {
std::swap(heap[index], heap[smallest]);
heapifyDown(smallest); // 递归调整
}
}
inline int getParent(int index) {
return (index - 1) / 2;
}
inline int getLeftChild(int index) {
return 2 * index + 1;
}
inline int getRightChild(int index) {
return 2 * index + 2;
}
public:
// 构造函数，数组构造时，一个一个添加
MinHeap() {}
MinHeap(const vector<int>& nums) {
for (const auto&num: nums) {
add(num);
}
}
// 添加元素
void add(int value) {
heap.push_back(value);
heapifyUp(heap.size() - 1);
}
// 弹出堆顶元素
int pop() {
if (heap.empty()) {
throw std::out_of_range("Heap is empty");
}
int top = heap[0];
heap[0] = heap.back();
heap.pop_back();
heapifyDown(0);
return top;
}
// 获取堆顶元素（不弹出）
int top() const {
if (heap.empty()) {
throw std::out_of_range("Heap is empty");
}
return heap[0];
}
// 获取堆的大小
size_t size() const {
return heap.size();
}
// 判断堆是否为空
bool empty() const {
return heap.empty();
}
};C++中的优先队列
这块有点反直觉说实话
#include <iostream>
#include <queue> // 包含 priority_queue 头文件
#include <vector>
using namespace std;
// 定义一个结构体
struct MyStruct {
int value;
// 重载 operator<
// C++的priority_queue的默认是最大堆，最优先的在堆顶，
// 意思是，堆顶元素的operator<函数，对于其他非顶元素，都为false。
bool operator<(const MyStruct& other) const {
// 在这里实现自定义的比较逻辑
return value < other.value;
}
};
int main() {
// 定义一个自定义比较器结构体，如果需要的话
struct MyComparator {
bool operator()(const MyStruct& a, const MyStruct& b) const {
return a.value < b.value; // >小顶堆；<大顶堆
}
};
// 使用自定义的结构体类型和比较器创建优先队列
std::priority_queue<MyStruct, vector<MyStruct>, MyComparator> pq;
// std::priority_queue<MyStruct> pq;
// 添加元素到优先队列
pq.push({5});
pq.push({10});
pq.push({3});
// 弹出并输出队列中的元素
while (!pq.empty()) {
std::cout << pq.top().value << " ";
pq.pop();
}
return 0;
}KMP
找到所有匹配子串的位置
vector<int> findAllSubStrPosition(const string& s, const string& subStr) {
int n = subStr.size();
vector<int> next(n, 0);
// next[j]代表[0,j]这个子串的前后相同部分的长度
// 也代表在j + 1匹配失败时，下一个尝试匹配的位置。
for (int i = 1, j = 0; i < subStr.size(); ++i) {
while (j != 0 && subStr[j] != subStr[i]) {
j = next[j - 1];
}
if (subStr[i] == subStr[j]) {
++j;
}
next[i] = j;
}
vector<int> allPosition;
for (int i = 0, j = 0; i < s.size(); ++i) {
// j的位置是尝试匹配的位置，不匹配则需要返回到next[j - 1]（这个也就是下一个尝试的位置）
// 举例 s="abab-ababe" subStr="ababe", 其中next为[0, 0, 1, 2, 0]
// 正常匹配，关键位置举例，此时i、j位置如下
// i
// |
// a b c d - a b a b e
// a b a b e
// |
// j
// 此时尝试匹配e和-，会匹配失败，子串的next为[0, 0, 1, 2, 0]，
// 即在e尝试失败时，需要在已经匹配的部分（即以j - 1结尾的前后部分，这里为2）找共同部分, 如下
// i
// |
// a b c d - a b a b e
// a b a b e
// |
// j
// 此时还是匹配失败，就只能跳到0了（next[2 - 1] = 0）
while (j != 0 && subStr[j] != s[i]) {
j = next[j - 1];
}
if (s[i] == subStr[j]) {
++j;
if (j == subStr.size()) {
allPosition.emplace_back(i - j + 1);
}
}
}
return allPosition;
}前缀树
class Trie {
public:
Trie(): isEnd(false) {}
void insert(const string& word) {
Trie* curr = this;
for (int i = 0; i < word.size(); ++i) {
if (!curr->next.count(word[i])) {
curr->next[word[i]] = new Trie;
}
curr = curr->next[word[i]];
}
curr->isEnd = true;
}
bool search(const string& word) {
Trie* p = searchPtr(word);
return p != nullptr && p->isEnd;
}
bool startsWith(const string& prefix) {
return searchPtr(prefix) != nullptr;
}
private:
Trie* searchPtr(const string& prefix) {
Trie* curr = this;
for (int i = 0; i < prefix.size(); ++i) {
if (!curr->next.count(prefix[i]))
return nullptr;
curr = curr->next[prefix[i]];
}
return curr;
}
unordered_map<char, Trie*> next;
bool isEnd;
};缓存淘汰
LRU
// 要点：
// 1. 哈希表加速node检索
// 2. 从头插，从尾删，保证顺序
class LRUCache {
public:
LRUCache(int capacity): capacity(capacity) {}
int get(int key) {
// 不存在直接返回
auto it = map.find(key);
if (it == map.end()) {
return -1;
}
// 存在则提出来放头部
int value = it->second->second;
updatePosition(key, value);
return value;
}
void put(int key, int value) {
// 存在，提出来放头部并修改value
auto it = map.find(key);
if (it != map.end()) {
updatePosition(key, value);
} else { // 不存在，放入；放入前检查容量，不足则弹出尾部。
insertNewNode(key, value);
}
}
private:
list<pair<int, int>> nodes;
unordered_map<int, list<pair<int, int>>::iterator> map;
int capacity;
void insertNewNode(int key, int value) {
if (full()) {
pop();
}
putIn(key, value);
}
void updatePosition(int key, int value) {
dropOut(key);
putIn(key, value);
}
// 尾部弹出
void pop() {
auto it = --nodes.end();
auto key = it->first;
map.erase(key);
nodes.erase(it);
}
// 放入头部，操作map和list。
void putIn(int key, int value) {
auto it = nodes.emplace_front(key, value);
map[key] = nodes.begin();
}
// 删除节点，操作map和list。
void dropOut(int key) {
auto it = map.find(key)->second;
map.erase(key);
nodes.erase(it);
}
bool full() {
return map.size() == capacity;
}
};LFU
struct Node{
int key;
int value;
int frequency;
Node(int key, int value, int frequency): key(key), value(value), frequency(frequency) {}
};
// 要点：
// 1. 通过minimumFrequency记录最小频率，避免pop时遍历frequencyMap。
// 2. 维护最小频率，只需考虑这两种情况。因为不主动删除，只在满时pop，所以满时要么插入新（为1），要么提高（n + 1）；
// 1. 插入新节点，更新为1。
// 2. 提升频率，最小频率链表为空时提升为。
// 3. 每个链表，从头插，从尾删，保证频率相同时，删除最先插入的。
class LFUCache {
public:
LFUCache(int capacity): capacity(capacity), minimumFrequency(0) {}
int get(int key) {
// 不存在返回错误
auto it = map.find(key);
if (it == map.end()) {
return -1;
}
// 存在，提升频率
int value = it->second->value;
incrementFrequency(key, value);
return value;
}
void put(int key, int value) {
// 不存在，插入频率为1的链表，注意满时pop
auto it = map.find(key);
if (it == map.end()) {
insertNewNode(key, value);
} else { // 存在，提升频率
incrementFrequency(key, value);
}
}
private:
unordered_map<int, std::list<Node>> frequencyMap;
unordered_map<int, std::list<Node>::iterator> map;
int minimumFrequency; // 频率更新情况：1. 插入新节点，更新为1。 2. 提升频率，最小频率链表为空时提升。
int capacity;
private:
bool full() {
return this->map.size() == this->capacity;
}
void insertNewNode(int key, int value) {
if (full()) {
if (this->capacity < 0) {
return ;
}
pop();
}
insertNode(key, value, 1);
this->minimumFrequency = 1; // 1. 插入新节点，更新为1。
}
// 弹出频率最低的节点。
void pop() {
int key = frequencyMap[minimumFrequency].back().key;
removeNode(key);
}
// 删除节点：删除map和frequcnyMap信息，但未更新频率
void removeNode(int key) {
removeFromFrequencyMap(key);
map.erase(key);
}
// 更新频率：涉及value更新、map指向更新、frequency频率更新
void incrementFrequency(int key, int value) {
Node d = *(map.find(key)->second);
removeNode(key);
insertNode(d.key, value, d.frequency + 1);
if (!frequencyMap.count(minimumFrequency)) {// 2. 提升频率，原链表为空时提升。
++minimumFrequency;
}
}
// 只操作frequecnyMap删除key，并删除空链表
void removeFromFrequencyMap(int key) {
auto it = map.find(key)->second;
int frequency = it->frequency;
frequencyMap[frequency].erase(it);
if (frequencyMap[frequency].empty()) {
frequencyMap.erase(frequency);
}
}
// 将node插入到map和frequecnyMap
void insertNode(int key, int value, int frequency) {
auto it = frequencyMap[frequency].emplace_front(key, value, frequency);
map[key] = frequencyMap[frequency].begin();
}
};Template
https://messenger1th.github.io/2024/07/24/LeetCode/Template/