第三章 图论 No.2单源最短路之虚拟源点,状压最短路与最短路次短路条数
文章目录
- 1137. 选择最佳线路
- 1131. 拯救大兵瑞恩
- 1134. 最短路计数
- 383. 观光
dp是特殊的最短路,是无环图(拓扑图)上的最短路问题
1137. 选择最佳线路
1137. 选择最佳线路 - AcWing题库

// 反向建图就行
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;typedef pair<int, int> PII;
const int N = 1e3 + 10, M = 2e4 + 10;
int h[N], e[M], ne[M], w[M], idx;
int n, m, s;
int a[N];
int dis[N]; bool st[N];void add(int x, int y, int d)
{e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}void dijkstra()
{priority_queue<PII, vector<PII>, greater<PII>> q;memset(dis, 0x3f, sizeof(dis));memset(st, 0, sizeof(st));dis[s] = 0;q.push({ dis[s], s });while (q.size()){auto t = q.top(); q.pop();int x = t.second, d = t.first;if (st[x]) continue;st[x] = true;for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];if (dis[y] > d + w[i]) {dis[y] = d + w[i];q.push({ dis[y], y });}}}
}int main()
{while (~scanf("%d%d%d", &n, &m, &s)){idx = 0;memset(h, -1, sizeof(h));int x, y, d;while ( m -- ){scanf("%d%d%d", &x, &y, &d);add(y, x, d);}int wn;scanf("%d", &wn);for (int i = 1; i <= wn; ++ i ) scanf("%d", &a[i]);dijkstra();int res = 0x3f3f3f3f;for (int i = 1; i <= wn; ++ i ) res = min(res, dis[a[i]]);if (res == 0x3f3f3f3f) puts("-1");else printf("%d\n", res);}return 0;
}
对于每组测试数据,该重置的数据要重置,我没有重置idx,导致TLE
处理反向建图,还有一种扩展做法:虚拟源点
设置虚拟源点,与每个起点之间连接边权为0的边
原问题:从多个源点出发,到达终点的最短路径
先问题:从虚拟源点出发,到达终点的最短路径
两者的最短路径一一对应,并且路径和相同

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;typedef pair<int, int> PII;
const int N = 1e3 + 10, M = 3e4 + 10;
int h[N], e[M], ne[M], w[M], idx;
int n, m, s;
int a[N];
int dis[N]; bool st[N];void add(int x, int y, int d)
{e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}void dijkstra()
{priority_queue<PII, vector<PII>, greater<PII>> q;memset(dis, 0x3f, sizeof(dis));memset(st, 0, sizeof(st));dis[0] = 0;q.push({ dis[0], 0 });while (q.size()){auto t = q.top(); q.pop();int x = t.second, d = t.first;if (st[x]) continue;st[x] = true;for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];if (dis[y] > d + w[i]) {dis[y] = d + w[i];q.push({ dis[y], y });}}}
}int main()
{while (~scanf("%d%d%d", &n, &m, &s)){idx = 0;memset(h, -1, sizeof(h));int x, y, d;while ( m -- ){scanf("%d%d%d", &x, &y, &d);add(x, y, d);}int wn;scanf("%d", &wn);for (int i = 1; i <= wn; ++ i ) {scanf("%d", &a[i]);add(0, a[i], 0); // 设置虚拟源点}dijkstra();if (dis[s] == 0x3f3f3f3f) puts("-1");else printf("%d\n", dis[s]);}return 0;
}
debug:将虚拟源点与起点之间建立边,要注意M的大小是否足够,又是M开小了…
1131. 拯救大兵瑞恩
1131. 拯救大兵瑞恩 - AcWing题库

从集合的角度分析
状态表示:
集合:起点为左上角,终点为图中任意一点的所有路径,用 f ( x , y ) f(x, y) f(x,y)表示终点为 [ x , y ] [x, y] [x,y]的路径
属性:最小时间(路径和)
所以 f ( x , y ) f(x, y) f(x,y)表示终点为 [ x , y ] [x, y] [x,y]的最小路径和
但是图中存在无法通过的墙以及需要钥匙打开的门,所以用两个维度表示路径将无法更新集合
考虑增加一个维度 s t a t e state state,状态压缩,表示拥有的钥匙状态
即 f ( x , y , s t a t e ) f(x, y, state) f(x,y,state)表示拥有钥匙的状态为 s t a t e state state时,递达 [ x , y ] [x, y] [x,y]的最短路
状态计算:
如何划分 f ( x , y , s t a t e ) f(x, y, state) f(x,y,state)?一般的dp问题是从后往前考虑,图论中的集合分析一般从前往后考虑
即 f ( x , y , s t a t e ) f(x, y, state) f(x,y,state)能推导出哪些集合?
若 [ x , y ] [x, y] [x,y]有钥匙,可以捡起这些钥匙,假设钥匙的状态为key,那么状态推导就是 f ( x , y , s t a t e ) − > f ( x , y , s t a t e ∣ k e y ) f(x, y, state)->f(x, y, state | key) f(x,y,state)−>f(x,y,state∣key)
若 [ x , y ] [x, y] [x,y]无钥匙,那么可以向相邻的位置走, f ( x , y , s t a t e ) − > f ( n x , n y , s t a t e ) f(x, y, state)->f(nx, ny, state) f(x,y,state)−>f(nx,ny,state),此时的最短距离要+1
由于这个问题中存在环路,所以无法用dp更新集合,只能用最短路算法更新集合
这题比较麻烦的是:建边,相邻两个位置若没有墙,那么可以建立一条权值为1的边
如何表示两个二维坐标之间有边?这里涉及到二维坐标到一维的转换,然后用邻接表存储图
若两个位置之间存在门,用边权表示门的种类,但是实际的边权为1
若两个位置之间既不存在门,也不存在墙,那么创建一条权值为0的边,但时间的边权为1。所以 w [ i ] w[i] w[i]为非0表示这个边上有道门,为0表示可以直接通过
对于墙的情况,直接忽略,不建立边(表示不连通)即可
用set存储已经建立的边,防止重复建边
#include <iostream>
#include <cstring>
#include <deque>
#include <set>
using namespace std;typedef pair<int, int> PII;
const int N = 11, P = 1 << N;
const int M = 400;
int h[N * N], e[M], ne[M], w[M], idx;
int g[N][N]; // 二维到一维的转换
int key[N * N]; // 每个坐标的钥匙状态
int dis[N * N][P]; bool st[N * N][P];
set<PII> s;int n, m, p, k;void add(int x, int y, int d)
{e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}void build()
{int dx[4] = { 0, 1, 0, -1}, dy[4] = { 1, 0, -1, 0 };for (int x = 1; x <= n; ++ x )for (int y = 1; y <= m; ++ y )for (int i = 0; i < 4; ++ i ){int nx = x + dx[i], ny = y + dy[i];if (nx > 0 && nx <= n && ny > 0 && ny <= m){int a = g[x][y], b = g[nx][ny];if (!s.count({a, b})) add(a, b, 0);}}
}int bfs()
{memset(dis, 0x3f, sizeof(dis));deque<PII> q;dis[1][0] = 0;q.push_back({1, 0});while (q.size()){auto t = q.front(); q.pop_front();int x = t.first, state = t.second;if (st[x][state]) continue;st[x][state] = true;if (x == n * m) return dis[n * m][state];if (key[x]){int nstate = state | key[x];if (dis[x][nstate] > dis[x][state]){dis[x][nstate] = dis[x][state];q.push_front({x, nstate});}}for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];if (w[i] && !((state >> w[i]) & 1)) continue;if (dis[y][state] > dis[x][state] + 1){dis[y][state] = dis[x][state] + 1;q.push_back({y, state});}}} return -1;
}int main()
{memset(h, -1, sizeof(h));scanf("%d%d%d%d", &n, &m, &p, &k);int cnt = 1;for (int i = 1; i <= n; ++ i )for (int j = 1; j <= m; ++ j ) g[i][j] = cnt ++ ;int x1, y1, x2, y2, x, y, d;while ( k -- ){scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &d);x = g[x1][y1], y = g[x2][y2];s.insert({x, y}), s.insert({y, x});if (d) add(x, y, d), add(y, x, d);}build(); // 建立除了门和墙的边int l;scanf("%d", &l);while ( l -- ){scanf("%d%d%d", &x, &y, &d);key[g[x][y]] |= 1 << d;}printf("%d\n", bfs());return 0;
}
debug:int x = t.first, state = t.second写成int x = t.secnd, state = t.first
只能说是dijkstra写多了
1134. 最短路计数
1134. 最短路计数 - AcWing题库


从集合的角度考虑, f ( i ) f(i) f(i)表示图中第i个点的最短路条数,假设与i相连的点由k个,那么 f ( i ) = f ( s 1 ) + f ( s 2 ) + . . . + f ( s k ) f(i) = f(s_1) + f(s_2) + ... + f(s_k) f(i)=f(s1)+f(s2)+...+f(sk),第i个点的最短路条数由与之直接相连的点的最短路条数累加而成
那么要求解 f ( i ) f(i) f(i),就要先算出它的子集,但是图论问题可能存在环,无法确定 f ( i ) f(i) f(i)是否会影响它的子集。所以只能在拓扑图中才能这样更新集合,考虑最短路算法的更新是否具有拓扑序
三种求最短路的方法:1.BFS 2.Dijkstra 3.Bellman-ford
探讨它们求解最短路时,是否具有拓扑序?
对于BFS,由于每个点只会入队一次且只会出队一次,说明BFS的更新天然地具有拓扑序,因为出队的点不会被后续入队的点影响
对于Dijkstra,由于每个点会入队多次,但只会出队一次,也说明了Dijkstra的更新天然地具有拓扑序
对于spfa,由于它是暴力算法的优化,每个点都会入队与出队多次,所以spfa的更新不具有拓扑序,已经出队(更新完成)的点可能影响被后续入队的点影响
即bfs和dijkstra的更新是一颗最短路树,而spfa的更新不是一颗最短路树

统计最短路条数时,可以遍历最短路树
若统计i节点的最短路条数,只需要累乘父节点的数量即可
而spfa的更新不具有拓扑序,即不存在最短路树,要是图中存在负权边,无法使用天然具有拓扑序的bfs和dijkstra时,只能先用spfa求出最短路,维护出最短路树,再求最短路条数
一般情况下,图中不能存在权值为0的点,否则无法建立出最短路树,因为达到某一个点的最短路不能确定
这题直接用bfs更新最短路,在更新过程中完成最短路条数的统计:用x更新y时,dis[y] > dis[x] + 1时,y的最短路数量等于x的最短路数量
若dis[y] == dix[x] + 1,y的最短路条数等于两者的数量累加
#include <iostream>
#include <cstring>
using namespace std;const int N = 1e5 + 10, M = 4e5 + 10, mod = 100003;
int h[N], e[M], ne[M], idx;
int dis[N], q[N], hh, tt = -1;
int cnt[N];
int n, m;void add(int x, int y)
{e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}void bfs()
{memset(dis, 0x3f, sizeof(dis));q[++ tt ] = 1;dis[1] = 0, cnt[1] = 1;while (tt >= hh){int x = q[hh ++ ];for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];if (dis[y] > dis[x] + 1){dis[y] = dis[x] + 1;q[++ tt ] = y;cnt[y] = cnt[x];}else if(dis[y] == dis[x] + 1) cnt[y] = (cnt[y] + cnt[x]) % mod;}}
}int main()
{memset(h, -1, sizeof(h));scanf("%d%d", &n, &m);int x, y;while ( m -- ){scanf("%d%d", &x, &y);add(x, y), add(y, x);}bfs();for (int i = 1; i <= n; ++ i ) {if (cnt[i] == 0x3f3f3f3f) puts("0");else printf("%d\n", cnt[i]);}return 0;
}
383. 观光
383. 观光 - AcWing题库

由于无负权边,所以用dijkstra更新最短路,同时维护最短路条数
但是题目还要维护最短路条数,所以这里用了个类似拯救大兵瑞恩的思想:状压
dis[i][0]表最短路距离,dis[i][1]表示次短路距离,由于次短路的更新也具有拓扑序,所以我们可以在更新次短路的时候维护次短路条数
d i s [ i ] [ 1 ] dis[i][1] dis[i][1]如何计算?与i相连的所有点的最短路以及次短路中,第二大的数
代码体现在:
若dis[y][0] > dis[x][0] + w[i],则更新最短路 d i s [ y ] [ 0 ] dis[y][0] dis[y][0],那么最短路成为次短路 d i s [ y ] [ 1 ] dis[y][1] dis[y][1],更新次短路,同时更新最短路
若dis[y][0] == dis[x][0] + w[i],那么最短路条数累加,cnt[y][0] += cnt[x][0]
若dis[y][1] > dis[x][0] + w[i],那么更新次短路 d i s [ y ] [ 1 ] dis[y][1] dis[y][1]
若dis[y][1] == dis[x][0] + w[i],那么次短路条数累加,cnt[y][1] += cnt[x][1]
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;const int N = 1010, M = 10010;
int h[N], e[M], ne[M], w[M], idx;
int n, m, s, t;
int dis[N][2], cnt[N][2]; bool st[N][2];struct Ver
{int x, d, type;bool operator>(const Ver& v) const // 建小堆重载>{return d > v.d;}
};void add(int x, int y, int d)
{e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}int dijkstra()
{memset(dis, 0x3f, sizeof(dis));memset(st, 0, sizeof(st));memset(cnt, 0, sizeof(cnt));priority_queue<Ver, vector<Ver>, greater<Ver>> q;q.push({s, 0, 0});dis[s][0] = 0, cnt[s][0] = 1;while (q.size()){auto t = q.top(); q.pop();int x = t.x, d = t.d, type = t.type;int count = cnt[x][type];if (st[x][type]) continue;st[x][type] = true;for (int i = h[x]; i != -1; i = ne[i]){int y = e[i];if (dis[y][0] > d + w[i]){dis[y][1] = dis[y][0], cnt[y][1] = cnt[y][0];q.push({y, dis[y][1], 1});dis[y][0] = d + w[i], cnt[y][0] = count;q.push({y, dis[y][0], 0});}else if (dis[y][0] == d + w[i]) cnt[y][0] += count;else if(dis[y][1] > d + w[i]){dis[y][1] = d + w[i], cnt[y][1] = count;q.push({y, dis[y][1], 1});}else if (dis[y][1] == d + w[i]) cnt[y][1] += count;}}int res = cnt[t][0];if (dis[t][0] + 1== dis[t][1]) res += cnt[t][1];return res;
}int main()
{int T;scanf("%d", &T);while ( T -- ){idx = 0;memset(h, -1, sizeof(h));scanf("%d%d", &n, &m);int x, y, d;while ( m -- ){scanf("%d%d%d", &x, &y, &d);add(x, y, d);}scanf("%d%d", &s, &t);printf("%d\n", dijkstra());}return 0;
}
相关文章:
第三章 图论 No.2单源最短路之虚拟源点,状压最短路与最短路次短路条数
文章目录 1137. 选择最佳线路1131. 拯救大兵瑞恩1134. 最短路计数383. 观光 dp是特殊的最短路,是无环图(拓扑图)上的最短路问题 1137. 选择最佳线路 1137. 选择最佳线路 - AcWing题库 // 反向建图就行 #include <iostream> #include…...
汉诺塔问题
一本通1205:汉诺塔问题 【题目描述】 约19世纪末,在欧州的商店中出售一种智力玩具,在一块铜板上有三根杆,最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上,条件…...
Java on Azure Tooling 6月更新|标准消费和专用计划及本地存储账户(Azurite)支持
作者:Jialuo Gan - Program Manager, Developer Division at Microsoft 排版:Alan Wang 大家好,欢迎阅读 Java on Azure 工具的六月更新。在本次更新中,我们将介绍 Azure Spring Apps 标准消费和专用计划支持以及本地存储账户&…...
Prometheus(八)-网络嗅探-黑盒监控
介绍 Blackbox Exporter是Prometheus社区提供的官方黑盒监控解决方案,其允许用户通过:HTTP、HTTPS、DNS、TCP以及ICMP的方式对网络进行探测。用户可以直接使用go get命令获取Blackbox Exporter源码并生成本地可执行文件: go get prometheus…...
modbus TCP 通信测试
modbus TCP 通信测试 读取单个或多个线圈 发送指令:00 00 00 00 00 06 00 01 03 10 00 08 00 00 00 00 00 06 00 01 03 10 00 08 事务 处理 标识 协议 标识 长度 单元 标识 功能码 起始 线圈 地址 线圈 个数 06:后面的字节长度。 01&am…...
GDB Debug
使用gdb带着参数启动程序 在gdb中启动程序并传递命令行参数: gdb ./my_program (gdb) run arg1 arg2 arg3 这将在gdb中启动程序"my_program",并将参数"arg1"、"arg2"和"arg3"传递给程序。 在启动gdb之前&…...
【项目流程】前端项目的开发流程
1. 项目中涉及的所有角色及其职责 - PM 产品经理 产品经理(Product Manager,简称PM)负责明确和定义产品的愿景和战略,与客户、用户、业务部门和其他利益相关者进行沟通,收集并分析他们的需求和期望。负责制定产品的详…...
JS监听浏览器关闭、刷新及切换标签页触发事件
蛮简单的东西,知道就会,不知道就不会,没什么逻辑可言。简单记录一下,只为加深点儿印象。 visibilitychange visibilitychange可以监听到浏览器的切换标签页。 直接上代码: <script>document.addEventListe…...
Unity 引擎做残影效果——3、顶点偏移方式
Unity实现残影效果 大家好,我是阿赵。 继续讲Unity引擎的残影做法。这次的残影效果和之前两种不太一样,是通过顶点偏移来实现的。 具体的效果是这样: 与其说是残影,这种效果更像是移动速度很快时造成的速度线,所以在移…...
【Linux】权限
1、shell命令以及运行原理 Linux 严格意义上说的是一个操作系统,我们称之为“核心(kernel)“ ,但我们一般用户,不能直接使用 kernel。而是通过 kernel 的“外壳”程序,也就是所谓的shell,来与 k…...
Excel导入日期格式时自动转为五位数文本
问题描述:Excel导入数据时,当数据是日期可能会存在问题,日期格式转为文本了,例如“2023-07-31”接收时变为“45138”,导致后端解析日期出错,无法导入。 解决方法: 方法一:将Excel日…...
Mac使用brew安装软件报错
在使用brew安装软件时报错Failed to upgrade Homebrew Portable Ruby! brew install --cask --appdir/Applications docker> Downloading https://ghcr.io/v2/homebrew/portable-ruby/portable-ruby/blobs/sha256:0cb1cc7af109437fe0e020c9f3b7b95c3c709b140bde9f991ad2c143…...
Android 实现MQTT客户端,用于门禁消息推送
添加MQTT依赖 implementation ‘org.eclipse.paho:org.eclipse.paho.client.mqttv3:1.2.2’ implementation ‘org.eclipse.paho:org.eclipse.paho.android.service:1.1.1’ 在Manifest清单文件中添加服务 <service android:name"org.eclipse.paho.android.service.Mq…...
跨境电商的广告推广怎么做?7个方法
在跨境电商竞争日趋激烈的市场环境下,跨境电商店铺引流成了制胜关键点。这里给大家分享一套引流推广的方法。 一、搜索引擎营销推广 搜索引擎有两个最大的优点是更灵活、更准确。搜索引擎营销的目标定位更精确,且不受时间和地理位置上的限制࿰…...
《Java-SE-第二十八章》之CAS
前言 在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!” 博客主页:KC老衲爱尼姑的博客主页 博主的github,平常所写代码皆在于此 共勉:talk is cheap, show me the code 作者是爪哇岛的新手,水平很有限&…...
git之reflog分析
写在前面 本文一起看下reflog命令。 1:场景描述 在开发的过程中,因为修改错误,想要通过git reset命令恢复到之前的某个版本,但是选择提交ID错误,导致多恢复了一个版本,假定,该版本对应的内容…...
《吐血整理》进阶系列教程-拿捏Fiddler抓包教程(18)-Fiddler如何接口测试,妈妈再也不担心我不会接口测试了
1.简介 Fiddler最大的优势在于抓包,我们大部分使用的功能也在抓包的功能上,fiddler做接口测试也是非常方便的。 领导或者开发给你安排接口测试的工作任务,但是没有给你接口文档(由于开发周期没有时间出接口文档)&…...
Oracle open JDK和 Amazon Corretto JDK的区别
Oracle OpenJDK和Amazon Corretto JDK都是基于Java开放源代码项目的发行版,它们之间有一些区别。 1. 来源:Oracle OpenJDK是由Oracle公司领导和支持的,它是Java的官方参考实现之一。而Amazon Corretto JDK是由亚马逊公司开发和支持的…...
Spark写PGSQL分区表
这里写目录标题 需求碰到的问题格式问题分区问题(重点) 解决完整代码效果 需求 spark程序计算后的数据需要往PGSQL中的分区表进行写入。 碰到的问题 格式问题 使用了字符串格式,导致插入报错。 val frame df.withColumn("insert_t…...
Git 命令行登录
有时候登录命令行版本的git会出现这个错误 1remote: Support for password authentication was removed on August 13, 2021. 2remote: Please see https://docs.github.com/en/get-started/getting-started-with-git/about-remote-repositories#cloning-with-https-urls for …...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
