企业官网建设流程全解析

qq代挂网站建设,网站建设的功能需求,网站开发技术路线,银铃建设通官方网站题目链接#xff1a;2976. 转换字符串的最小成本 I#xff08;中等#xff09; 算法原理#xff1a; 解法#xff1a;图论 Floyd-Warshall#xff08;弗洛伊德#xff09; 13ms击败91.30% 时间复杂度O(nm∣Σ∣)#xff0c;其中 n 为 source 的长度#xff0c;m 为 c…题目链接2976. 转换字符串的最小成本 I中等算法原理解法图论 Floyd-Warshall弗洛伊德13ms击败91.30%时间复杂度O(nm∣Σ∣³)其中 n 为 source 的长度m 为 cost 的长度∣Σ∣ 为字符集合的大小本题中字符均为小写字母所以 ∣Σ∣26核心思想字符转换问题转化为「多源最短路径问题」①把 26 个小写字母视为图的 26 个节点②字符 A 转字符 B 的成本视为节点 A 到 B 的有向边权重③求 “source 转 target 的最小总成本” 等价于 “依次求每个对应字符对的最短路径再累加”具体步骤1.问题建模①定义 26×26 的距离矩阵disdis[i][j]表示字符ai转换为aj的最小成本②矩阵初始化dis[i][i] 0自身转自身成本为 0其余值设为极大值INF表示初始不可达2.填充直接转换成本①遍历original、changed、cost数组将字符转换为对应索引c-a②若存在字符x转y的直接成本为处理重复转化的情况更新dis[x][y]为 “当前值” 和 “给定成本” 的最小值3.Floyd-Warshall 求全源最短路径①三层循环中间节点 k → 源节点 i → 目标节点 j核心公式②dis[i][j] min(dis[i][j], dis[i][k] dis[k][j])③剪枝优化若i 到 k 不可达dis[i][k] INF则直接跳过4.计算总转换成本①遍历source和target的每个对应字符取其索引s和t②若该字符转换不可达dis[s][t] INF直接返回 - 1③否则累加dis[s][t]最终返回累加结果用 long 类型避免 int 溢出Java代码class Solution { public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) { //定义为最大值的一半防止后续相加溢出 final int INF0x3f3f3f3f; //dis[i][j]:i处字符转化为j处字符的最小成本 int[][] disnew int[26][26]; //初始化为INF表示初始不可达 for(int i0;i26;i){ Arrays.fill(dis[i],INF); dis[i][i]0;//字符自身转为自身成本为0 } //填充直接转换的成本 for(int i0;icost.length;i){ //将对应字符转化为索引 int xoriginal[i]-a; int ychanged[i]-a; //取最小值遇到相同的转换保留最小值 dis[x][y]Math.min(dis[x][y],cost[i]); } //求任意两个字符间的最短路i-k-j //i:源字符,k:中间转换字符,j:目标字符 for(int k0;k26;k){ for(int i0;i26;i){ //剪枝优化若i-k不可达无需计算i-k-j的路径 if(dis[i][k]INF) continue; for(int j0;j26;j) dis[i][j]Math.min(dis[i][j],dis[i][k]dis[k][j]); } } //计算source转target的总最小成本用long避免int溢出 long ret0; for(int i0;isource.length();i){ //取出索引 int ssource.charAt(i)-a; int ttarget.charAt(i)-a; //若当前字符转换不可达直接返回-1 if(dis[s][t]INF) return -1; retdis[s][t]; } return ret; } }