- 找满足条件的最大值
while (left < right) {
mid = left + (right - left + 1) / 2;
if (check(price, k, mid)) {
left = mid;
} else {
right = mid - 1;
}
}/**
* @Description: 线段树（动态开点）
* @Author: LFool
* @Date 2022/6/7 09:15
**/
public class SegmentTreeDynamic {
class Node {
Node left, right;
int val, add;
}
private int N = (int) 1e9;
private Node root = new Node();
// 在区间 [start, end] 中更新区间 [l, r] 的值，将区间 [l, r] ➕ val
public void update(Node node, int start, int end, int l, int r, int val) {
if (l <= start && end <= r) {
node.val += (end - start + 1) * val;
node.add += val;
return ;
}
int mid = (start + end) >> 1;
pushDown(node, mid - start + 1, end - mid);
if (l <= mid) update(node.left, start, mid, l, r, val);
if (r > mid) update(node.right, mid + 1, end, l, r, val);
pushUp(node);
}
// 在区间 [start, end] 中查询区间 [l, r] 的结果，即 [l ,r] 保持不变
public int query(Node node, int start, int end, int l, int r) {
if (l <= start && end <= r) return node.val;
int mid = (start + end) >> 1, ans = 0;
pushDown(node, mid - start + 1, end - mid);
if (l <= mid) ans += query(node.left, start, mid, l, r);
if (r > mid) ans += query(node.right, mid + 1, end, l, r);
return ans;
}
private void pushUp(Node node) {
node.val = node.left.val + node.right.val;
}
private void pushDown(Node node, int leftNum, int rightNum) {
if (node.left == null) node.left = new Node();
if (node.right == null) node.right = new Node();
if (node.add == 0) return ;
node.left.val += node.add * leftNum;
node.right.val += node.add * rightNum;
// 对区间进行「加减」的更新操作，下推懒惰标记时需要累加起来，不能直接覆盖
node.left.add += node.add;
node.right.add += node.add;
node.add = 0;
}
}
class NumArray {
public:
vector<int> tree;
int lowbit(int x) {
return x & -x;
}
int query(int x) {
int ans = 0;
for(int i = x; i > 0; i -= lowbit(i))
ans += tree[i];
return ans;
}
void add(int x, int u) {
for(int i = x; i <= n; i += lowbit(i))
tree[i] += u;
}
vector<int> nums;
int n;
NumArray(vector<int>& nums) {
this->nums = nums;
n = nums.size();
tree.resize(n+1, 0);
for(int i = 0; i < n; i++)
add(i+1, nums[i]);
}
void update(int index, int val) {
add(index+1, val-nums[index]);
nums[index] = val;
}
int sumRange(int left, int right) {
return query(right+1) - query(left);
}
};if (i > 0 && arr[i] == arr[i - 1]) {
continue;
}-
0-1背包
int knapsack(vector<int> weights, vector<int> values, int N, int W) { // dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值 vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0)); for (int i = 1; i <= N; ++i) { int w = weights[i-1], v = values[i-1]; for (int j = 1; j <= W; ++j) { if (j >= w) { dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v); } else { dp[i][j] = dp[i-1][j]; } } } return dp[N][W]; }
-
空间优化版本
int knapsack(vector<int> weights, vector<int> values, int N, int W) { vector<int> dp(W + 1, 0); for (int i = 1; i <= N; ++i) { int w = weights[i-1], v = values[i-1]; for (int j = W; j >= w; --j) { dp[j] = max(dp[j], dp[j-w] + v); } } return dp[W]; }
-
完全背包
int knapsack(vector<int> weights, vector<int> values, int N, int W) { vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0)); for (int i = 1; i <= N; ++i) { int w = weights[i-1], v = values[i-1]; for (int j = 1; j <= W; ++j) { if (j >= w) { dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v); } else { dp[i][j] = dp[i-1][j]; } } } return dp[N][W]; }
-
空间优化
int knapsack(vector<int> weights, vector<int> values, int N, int W) { vector<int> dp(W + 1, 0); for (int i = 1; i <= N; ++i) { int w = weights[i-1], v = values[i-1]; for (int j = w; j <= W; ++j) { dp[j] = max(dp[j], dp[j-w] + v); } } return dp[W]; }
public int kmp (char[] hasyarr, int halen, char[] nearr, int nelen) {
//获取next 数组
int[] next = next(nearr,nelen);
int j = 0;
for (int i = 0; i < halen; ++i) {
//发现不匹配的字符，然后根据 next 数组移动指针，移动到最大公共前后缀的，
//前缀的后一位,和咱们移动模式串的含义相同
while (j > 0 && hasyarr[i] != nearr[j]) {
j = next[j - 1] + 1;
//超出长度时，可以直接返回不存在
if (nelen - j + i > halen) {
return -1;
}
}
//如果相同就将指针同时后移一下，比较下个字符
if (hasyarr[i] == nearr[j]) {
++j;
}
//遍历完整个模式串，返回模式串的起点下标
if (j == nelen) {
return i - nelen + 1;
}
}
return -1;
}
//这一块比较难懂，不想看的同学可以忽略，了解大致含义即可，或者自己调试一下，看看运行情况
//我会每一步都写上注释
public int[] next (char[] needle,int len) {
//定义 next 数组
int[] next = new int[len];
// 初始化
next[0] = -1;
int k = -1;
for (int i = 1; i < len; ++i) {
//我们此时知道了 [0,i-1]的最长前后缀，但是k+1的指向的值和i不相同时，我们则需要回溯
//因为 next[k]就时用来记录子串的最长公共前后缀的尾坐标（即长度）
//就要找 k+1前一个元素在next数组里的值,即next[k+1]
while (k != -1 && needle[k + 1] != needle[i]) {
k = next[k];
}
// 相同情况，就是 k的下一位，和 i 相同时，此时我们已经知道 [0,i-1]的最长前后缀
//然后 k - 1 又和 i 相同，最长前后缀加1，即可
if (needle[k+1] == needle[i]) {
++k;
}
next[i] = k;
}
return next;
}时间复杂度：O（|V|+|E|）
性质：到所有顶点都是最短路径（对于无权图）
-
7.3.1Dijkstra算法：
-
堆写法
- 时间复杂度：O(n2）
- 空间复杂度：O(n2)
int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; // 定义小根堆 priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); // 先将最短的距离添加到小根堆中 while (heap.size()) { auto t = heap.top(); // 取出当前已经确定的最短距离的点 heap.pop(); int ver = t.second; if (st[ver]) continue; // 如果已经被标记过，说明当前的点的边是比较长的重边，直接跳过。 st[ver] = true; // 使用当前距离最短的点来更新其出边 for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; // j 为 ver 出边所到达的点 if (dist[j] > dist[ver] + w[i]) { /* 如果源点直接到 j 点的距离比源点先到 ver 点再从 ver 点到 j 点的距离大， 那么就更新 dist[j]，使dist[j] 到源点的距离最短 */ dist[j] = dist[ver] + w[i]; // 将下一个距离源点最近的点添加到小根堆中 heap.push({dist[j], j}); } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; }
-
朴素写法
- 时间复杂度：$O(n^2)$
- 空间复杂度：$O(n^2)$
class Solution { int N = 110, M = 6010; // 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边 int[][] w = new int[N][N]; // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y int[] dist = new int[N]; // 记录哪些点已经被更新过 boolean[] vis = new boolean[N]; int INF = 0x3f3f3f3f; int n, k; public int networkDelayTime(int[][] ts, int _n, int _k) { n = _n; k = _k; // 初始化邻接矩阵 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { w[i][j] = w[j][i] = i == j ? 0 : INF; } } // 存图 for (int[] t : ts) { int u = t[0], v = t[1], c = t[2]; w[u][v] = c; } // 最短路 dijkstra(); // 遍历答案 int ans = 0; for (int i = 1; i <= n; i++) { ans = Math.max(ans, dist[i]); } return ans > INF / 2 ? -1 : ans; } void dijkstra() { // 起始先将所有的点标记为「未更新」和「距离为正无穷」 Arrays.fill(vis, false); Arrays.fill(dist, INF); // 只有起点最短距离为 0 dist[k] = 0; // 迭代 n 次 for (int p = 1; p <= n; p++) { // 每次找到「最短距离最小」且「未被更新」的点 t int t = -1; for (int i = 1; i <= n; i++) { if (!vis[i] && (t == -1 || dist[i] < dist[t])) t = i; } // 标记点 t 为已更新 vis[t] = true; // 用点 t 的「最小距离」更新其他点 for (int i = 1; i <= n; i++) { dist[i] = Math.min(dist[i], dist[t] + w[t][i]); } } } }
边权为正
-
时间复杂度：O(|V + E|log(|V|))
-
bellman-ford算法
- 负权图中求最短路，该算法也是「单源最短路」算法
- 时间复杂度：O(n∗m)
- 空间复杂度：O(m)
class Solution { class Edge { int a, b, c; Edge(int _a, int _b, int _c) { a = _a; b = _b; c = _c; } } int N = 110, M = 6010; // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y int[] dist = new int[N]; int INF = 0x3f3f3f3f; int n, m, k; // 使用类进行存边 List<Edge> es = new ArrayList<>(); public int networkDelayTime(int[][] ts, int _n, int _k) { n = _n; k = _k; m = ts.length; // 存图 for (int[] t : ts) { int u = t[0], v = t[1], c = t[2]; es.add(new Edge(u, v, c)); } // 最短路 bf(); // 遍历答案 int ans = 0; for (int i = 1; i <= n; i++) { ans = Math.max(ans, dist[i]); } return ans > INF / 2 ? -1 : ans; } void bf() { // 起始先将所有的点标记为「距离为正无穷」 Arrays.fill(dist, INF); // 只有起点最短距离为 0 dist[k] = 0; // 迭代 n 次 for (int p = 1; p <= n; p++) { int[] prev = dist.clone(); // 每次都使用上一次迭代的结果，执行松弛操作 for (Edge e : es) { int a = e.a, b = e.b, c = e.c; dist[b] = Math.min(dist[b], prev[a] + c); } } } }
-
Floyd 算法
复杂度为$O(n^3)$ 的「多源汇最短路」算法,跑一遍 Floyd，可以得到「从任意起点出发，到达任意起点的最短距离」。
- 时间复杂度：$O(n^3)$
- 空间复杂度：$O(n^2)$
class Solution {
int N = 110, M = 6010;
// 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
int[][] w = new int[N][N];
int INF = 0x3f3f3f3f;
int n, k;
public int networkDelayTime(int[][] ts, int _n, int _k) {
n = _n; k = _k;
// 初始化邻接矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = w[j][i] = i == j ? 0 : INF;
}
}
// 存图
for (int[] t : ts) {
int u = t[0], v = t[1], c = t[2];
w[u][v] = c;
}
// 最短路
floyd();
// 遍历答案
int ans = 0;
for (int i = 1; i <= n; i++) {
ans = Math.max(ans, w[k][i]);
}
return ans >= INF / 2 ? -1 : ans;
}
void floyd() {
// floyd 基本流程为三层循环：
// 枚举中转点 - 枚举起点 - 枚举终点 - 松弛操作
for (int p = 1; p <= n; p++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = Math.min(w[i][j], w[i][p] + w[p][j]);
}
}
}
}
}-
spfa算法
- SPFA 是对 Bellman Ford 的优化实现，可以使用队列进行优化，也可以使用栈进行优化
- 时间复杂度：O(n∗m)
- 空间复杂度：O(m)
class Solution { int N = 110, M = 6010; // 邻接表 int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M]; // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y int[] dist = new int[N]; // 记录哪一个点「已在队列」中 boolean[] vis = new boolean[N]; int INF = 0x3f3f3f3f; int n, k, idx; void add(int a, int b, int c) { e[idx] = b; ne[idx] = he[a]; he[a] = idx; w[idx] = c; idx++; } public int networkDelayTime(int[][] ts, int _n, int _k) { n = _n; k = _k; // 初始化链表头 Arrays.fill(he, -1); // 存图 for (int[] t : ts) { int u = t[0], v = t[1], c = t[2]; add(u, v, c); } // 最短路 spfa(); // 遍历答案 int ans = 0; for (int i = 1; i <= n; i++) { ans = Math.max(ans, dist[i]); } return ans > INF / 2 ? -1 : ans; } void spfa() { // 起始先将所有的点标记为「未入队」和「距离为正无穷」 Arrays.fill(vis, false); Arrays.fill(dist, INF); // 只有起点最短距离为 0 dist[k] = 0; // 使用「双端队列」存储，存储的是点编号 Deque<Integer> d = new ArrayDeque<>(); // 将「源点/起点」进行入队，并标记「已入队」 d.addLast(k); vis[k] = true; while (!d.isEmpty()) { // 每次从「双端队列」中取出，并标记「未入队」 int poll = d.pollFirst(); vis[poll] = false; // 尝试使用该点，更新其他点的最短距离 // 如果更新的点，本身「未入队」则加入队列中，并标记「已入队」 for (int i = he[poll]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > dist[poll] + w[i]) { dist[j] = dist[poll] + w[i]; if (vis[j]) continue; d.addLast(j); vis[j] = true; } } } } }
图中所有的环都必须有偶数个顶点，这等价于图是二分图
int8_t color[n]; memset(color, 0, sizeof(color));
vector<int> nodes;
function<bool(int, int8_t)> is_bipartite = [&](int x, int8_t c) -> bool { // 二分图判定，原理见视频讲解
nodes.push_back(x);
color[x] = c;
for (int y : g[x])
if (color[y] == c || color[y] == 0 && !is_bipartite(y, -c))
return false;
return true;
};思路：拓扑排序之后，自后向前动态规划
#include <iostream>
#include <vector>
#include <deque>
#define NODE_COUNT 6
#define INF 255
using namespace std;
struct Node {
int pos;
int weight;
};
vector<Node> graph[NODE_COUNT];
int indegree[NODE_COUNT] = {0};
int beginPos;
int endPos;
void setEdge(vector<Node> graph[NODE_COUNT],int from, int to, int weight, int indegree[NODE_COUNT]) {
//邻接表
Node node;
node.pos = to;
node.weight = weight;
graph[from].push_back(node);
indegree[to]++;
}
void topoSort(vector<Node> graph[NODE_COUNT], int indegree[NODE_COUNT], vector<int>& linearList) {
deque<int> queue;
for (int i = 0; i < NODE_COUNT; i++) {
if (indegree[i] == 0) {
queue.push_back(i);
}
}
while (!queue.empty()) {
int pos = queue.front();
queue.pop_front();
linearList.push_back(pos);
for (int j = 0; j < graph[pos].size(); j++) {
if (!--indegree[graph[pos].at(j).pos]) {
queue.push_back(graph[pos].at(j).pos);
}
}
}
}
int getWeight(vector<Node> graph[NODE_COUNT],int from,int to) {
for (int i = 0; i < graph[from].size(); i++) {
if (graph[from][i].pos == to) {
return graph[from][i].weight;
}
}
return INF;
}
void findMinRoute(vector<Node> graph[NODE_COUNT], int beginPos, int endPos,vector<int> linearlist) {
int nextPos[NODE_COUNT];
int dist[NODE_COUNT];
for (int i = 0; i < NODE_COUNT; i++) {
dist[i] = getWeight(graph, i, endPos);
}
dist[endPos] = 0;
for (int i = NODE_COUNT - 2; i >= 0; i--) {
int nowpos = linearlist[i];
for (int j = 0; j < graph[nowpos].size(); j++) {
if (graph[nowpos][j].weight + dist[graph[nowpos][j].pos] <= dist[nowpos]) {
nextPos[nowpos] = graph[nowpos][j].pos;
dist[nowpos] = graph[nowpos][j].weight + dist[graph[nowpos][j].pos];
}
}
}
cout << "最短路径长为:" << dist[beginPos] << endl;
cout << "最短路径为:";
int temp = beginPos;
cout << beginPos;
while (temp != endPos) {
cout << "-->" << nextPos[temp];
temp = nextPos[temp];
}
cout << "\n";
}
int main(void) {
beginPos = 0;
endPos = 5;
setEdge(graph, 0, 1, 1, indegree);
setEdge(graph, 0, 2, 2, indegree);
setEdge(graph, 1, 3, 6, indegree);
setEdge(graph, 2, 1, 4, indegree);
setEdge(graph, 2, 4, 3, indegree);
setEdge(graph, 3, 4, 1, indegree);
setEdge(graph, 3, 5, 2, indegree);
setEdge(graph, 4, 5, 1, indegree);
vector<int> list;
topoSort(graph, indegree, list);
cout << "拓扑排序:";
for (int i = 0; i < list.size(); i++) {
cout << list[i] << " ";
}
cout << "\n";
findMinRoute(graph, beginPos, endPos, list);
system("pause");
return 0;
}另一种更好理解的思路：
初始化 dist[] = {INF, INF, …} 和 dist[s] = 0 其中 s 是源顶点。
创建所有顶点的拓扑顺序。
按照拓扑顺序对每个顶点 u 执行以下操作。
…………对 u 的每个相邻顶点 v 执行以下操作
………………if (dist[v] > dist[u] + weight(u, v))
………………………dist[ v] = dist[u] + weight(u, v)- 法1
bool isPrime(int n) {
if (n <= 3) {
return n > 1;
}
//只需判断一个数能否被小于sqrt(n)的奇数整除
int sqrt = (int)sqrt(n);
for (int i = 3; i <= sqrt; i += 2) {
if(n % 2 == 0 || n % i == 0) {
return false;
}
}
return true;
}- 法2
bool isPrime(int n) {
if (n <= 3) {
return n > 1;
}
// 只有6x-1和6x+1的数才有可能是质数
if (n % 6 != 1 && n % 6 != 5) {
return false;
}
// 判断这些数能否被小于sqrt(n)的奇数整除
int sqr = (int)sqrt(n);
for (int i = 5; i <= sqr; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
vector<int> parent;
int find(int x) {
while (x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
void connect(int x, int y) {
int root_x = find(x);
int root_y = find(y);
if (root_x == root_y) {
return;
} else if (root_x < root_y) {
size[root_x] += size[root_y];
parent[root_y] = root_x;
} else {
size[root_y] += size[root_x];
parent[root_x] = root_y;
}
}
bool is_connect(int x, int y) {
return find(x) == find(y);
}
iota(parent.begin(), parent.end(), 0);
size = vector<int>(m * n, 1);int countSpecialNumbers(int n) {
auto s = to_string(n);
int m = s.length(), memo[m][1 << 10];
memset(memo, -1, sizeof(memo)); // -1 表示没有计算过
function<int(int, int, bool, bool)> f = [&](int i, int mask, bool is_limit, bool is_num) -> int {
if (i == m)
return is_num; // is_num 为 true 表示得到了一个合法数字
if (!is_limit && is_num && memo[i][mask] != -1)
return memo[i][mask];
int res = 0;
if (!is_num) // 可以跳过当前数位
res = f(i + 1, mask, false, false);
int up = is_limit ? s[i] - '0' : 9; // 如果前面填的数字都和 n 的一样，那么这一位至多填数字 s[i]（否则就超过 n 啦）
for (int d = 1 - is_num; d <= up; ++d) // 枚举要填入的数字 d
if ((mask >> d & 1) == 0) // d 不在 mask 中
res += f(i + 1, mask | (1 << d), is_limit && d == up, true);
if (!is_limit && is_num)
memo[i][mask] = res;
return res;
};
return f(0, 0, true, false);
}int quickSelect(vector<int>& a, int l, int r, int index) {
int q = randomPartition(a, l, r);
if (q == index) {
return a[q];
} else {
return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index);
}
}
inline int randomPartition(vector<int>& a, int l, int r) {
int i = rand() % (r - l + 1) + l;
swap(a[i], a[r]);
return partition(a, l, r);
}
inline int partition(vector<int>& a, int l, int r) {
int x = a[r], i = l - 1;
for (int j = l; j < r; ++j) {
if (a[j] <= x) {
swap(a[++i], a[j]);
}
}
swap(a[i + 1], a[r]);
return i + 1;
}
int findKthLargest(vector<int>& nums, int k) {
srand(time(0));
return quickSelect(nums, 0, nums.size() - 1, nums.size() - k);
}该模板可以做到
- 求出所有子数组的按位或的结果，以及值等于该结果的子数组的个数。
- 求按位或结果等于任意给定数字的子数组的最短长度/最长长度。
class Solution {
public:
vector<int> smallestSubarrays(vector<int> &nums) {
int n = nums.size();
vector<int> ans(n);
vector<pair<int, int>> ors; // 按位或的值 + 对应子数组的右端点的最小值
for (int i = n - 1; i >= 0; --i) {
ors.emplace_back(0, i);
ors[0].first |= nums[i];
int k = 0;
for (int j = 1; j < ors.size(); ++j) {
ors[j].first |= nums[i];
if (ors[k].first == ors[j].first)
ors[k].second = ors[j].second; // 合并相同值，下标取最小的
else ors[++k] = ors[j];
}
ors.resize(k + 1);
// 本题只用到了 ors[0]，如果题目改成任意给定数字，可以在 ors 中查找
ans[i] = ors[0].second - i + 1;
}
return ans;
}
};class CountIntervals {
typedef pair<int, int> pii;
int ans = 0;
set<pii> st;
public:
CountIntervals() {
}
void add(int left, int right) {
int L = left, R = right;
// 这里 (R1, L1) >= (R2, L2)，若 R1 > R2 或 R1 = R2 且 L1 >= L2
auto it = st.lower_bound(pii(left - 1, -2e9));
while (it != st.end()) {
if (it->second > right + 1) break;
L = min(L, it->second);
R = max(R, it->first);
ans -= it->first - it->second + 1;
st.erase(it++);
}
ans += R - L + 1;
st.insert(pii(R, L));
}
int count() {
return ans;
}
};// 利用桶思想
int getId(int val, long w) {
return val < 0 ? (val + 1) / w - 1 : val / w;
}