企业官网建设流程全解析

网站中的宣传册翻页动画怎么做,wordpress商城主题修改,百度指数怎么看排名,广告在线制作图片Problem: 2976. 转换字符串的最小成本 I 文章目录 整体思路1. 核心问题2. 算法与逻辑步骤 完整代码时空复杂度1. 时间复杂度#xff1a; O ( N M C 3 ) O(N M C^3) O(NMC3)2. 空间复杂度#xff1a; O ( C 2 ) O(C^2) O(C2) 整体思路 1. 核心问题 我们需要将 source 字…Problem: 2976. 转换字符串的最小成本 I文章目录整体思路1. 核心问题2. 算法与逻辑步骤完整代码时空复杂度1. 时间复杂度O ( N M C 3 ) O(N M C^3)O(NMC3)2. 空间复杂度O ( C 2 ) O(C^2)O(C2)整体思路1. 核心问题我们需要将source字符串转换为target字符串。转换规则由original,changed,cost数组给出表示将字符original[i]变为changed[i]需要花费cost[i]。转换具有传递性例如a - b - c我们需要求出总的最小成本。如果无法转换返回 -1。2. 算法与逻辑步骤这是一个典型的多源最短路径问题。图的建模将 26 个小写英文字母看作图中的 26 个节点‘a’ 对应 0…‘z’ 对应 25。输入的转换规则即为图中的有向边权重为转换成本。我们需要计算任意两个字符之间的最小转换代价。Floyd-Warshall 算法由于节点数固定且非常少仅 26 个Floyd-Warshall 算法是解决此问题的最佳选择。它可以一次性计算出所有节点对之间的最短路径。初始化创建一个26 × 26 26 \times 2626×26的矩阵minCosts。对角线自己转自己设为 0。其他位置初始化为无穷大这里用Integer.MAX_VALUE / 2防止加法溢出。根据输入的边 (original,changed,cost) 更新矩阵。注意可能有重边多条规则描述同一种转换取最小值。三重循环松弛通过中间节点k尝试优化从i到j的路径minCosts[i][j] min(minCosts[i][j], minCosts[i][k] minCosts[k][j])。计算总成本预处理完成后我们拥有了一个查找表minCosts可以在O ( 1 ) O(1)O(1)时间内查询任意字符转换的最优代价。遍历source和target字符串逐个字符查询转换成本并累加。如果在任意位置查询到的成本为无穷大UNREACHABLE说明不可达立即返回 -1。完整代码importjava.util.Arrays;classSolution{publiclongminimumCost(Stringsource,Stringtarget,char[]original,char[]changed,int[]cost){// 定义一个足够大的数表示不可达但不能是 Integer.MAX_VALUE否则相加会溢出finalintUNREACHABLEInteger.MAX_VALUE/2;// 字母表大小固定为 26finalintALPHABET_SIZE26;// minCosts[i][j] 存储从字符 i 转换到字符 j 的最小成本int[][]minCostsnewint[ALPHABET_SIZE][ALPHABET_SIZE];// 1. 初始化距离矩阵for(inti0;iALPHABET_SIZE;i){// 默认所有转换都不可达Arrays.fill(minCosts[i],UNREACHABLE);// 字符转换为自身的成本为 0minCosts[i][i]0;}// 2. 根据输入构建初始图for(inti0;icost.length;i){intfromIndexoriginal[i]-a;inttoIndexchanged[i]-a;// 注意输入中可能存在多条相同起止点的边必须取最小值minCosts[fromIndex][toIndex]Math.min(minCosts[fromIndex][toIndex],cost[i]);}// 3. 使用 Floyd-Warshall 算法计算所有节点对的最短路径// k 是中间节点for(intk0;kALPHABET_SIZE;k){// i 是起始节点for(inti0;iALPHABET_SIZE;i){// 剪枝如果起点到中间点不可达就没必要继续看了if(minCosts[i][k]UNREACHABLE){continue;}// j 是终点for(intj0;jALPHABET_SIZE;j){// 状态转移比较 直接从 i 到 j 和 经由 k 从 i 到 j 的成本if(minCosts[k][j]!UNREACHABLE){minCosts[i][j]Math.min(minCosts[i][j],minCosts[i][k]minCosts[k][j]);}}}}// 4. 计算 source 转换到 target 的总成本longtotalCost0;// 使用 long 防止总成本溢出 int 范围intlensource.length();for(inti0;ilen;i){intsourceCharIdxsource.charAt(i)-a;inttargetCharIdxtarget.charAt(i)-a;// 查表获取最小转换成本intcurrentPairCostminCosts[sourceCharIdx][targetCharIdx];// 如果某个字符无法转换说明整个任务失败if(currentPairCostUNREACHABLE){return-1;}totalCostcurrentPairCost;}returntotalCost;}}时空复杂度假设source的长度为N NN转换规则数组边的长度为M MM字符集大小为C CC本题中C 26 C26C26。1. 时间复杂度O ( N M C 3 ) O(N M C^3)O(NMC3)初始化图遍历M MM条边耗时O ( M ) O(M)O(M)。Floyd-Warshall 算法包含三重循环每重循环次数为C CC耗时O ( C 3 ) O(C^3)O(C3)。由于C 26 C26C26这是一个非常小的常数26 3 ≈ 1.7 × 10 4 26^3 \approx 1.7 \times 10^4263≈1.7×104。计算总成本遍历长度为N NN的字符串每次查表O ( 1 ) O(1)O(1)耗时O ( N ) O(N)O(N)。总计O ( N M C 3 ) O(N M C^3)O(NMC3)。在实际应用中N NN通常是主导项。2. 空间复杂度O ( C 2 ) O(C^2)O(C2)距离矩阵我们需要一个C × C C \times CC×C的二维数组minCosts来存储最短路径。结论O ( C 2 ) O(C^2)O(C2)对于C 26 C26C26空间消耗极小且固定。