Leetcode每日一题练习 ------ 2976. 转换字符串的最小成本 I

Leetcode 每日一题练习继续讨论:

2976. 转换字符串的最小成本 I
2976. Minimum Cost to Convert String I

题解

本题和昨天的题目核心思路上基本相同, 只需要遍历原始字母和其映射字母以及相应的花费, 将字母对应的映射字母和其花费保存起来, 这里可以使用一个map, 也可以把字母当成下标, 用一个26*26的数组来保存(只有小写字母). 关键还是当原始字母和映射字母均相同时如果有多个不同的花费, 要将最小的花费保存下来. 因为这里我们只关心最小花费, 每个映射都是最小花费最终得到的即为最小花费, 是一个比较清晰的贪心法. 需要注意的是可能存在c->e, e->b这样的转换的花费比c->b小得多, 是不是感觉很熟悉, 实际上这个问题完全可以把字母当成节点, 花费当成边的花费, 这样问题就转换成了和昨天完全一样的问题. 使用同样的方法求解即可. 本题中求解最短路径我们使用Floyd-Warshall算法, 该算法的原理为动态规划.

代码

func minimumCost(source string, target string, original []byte, changed []byte, cost []int) int64 {
    costs := make([][]int, 26)
    for i,_ := range costs{
        costs[i] = make([]int, 26)
        for j:= range costs[i]{
            costs[i][j] = math.MaxInt32
        }
        costs[i][i] = 0
    }
    for i,_ := range original{
        costs[original[i]-'a'][changed[i]-'a'] = min(cost[i],costs[original[i]-'a'][changed[i]-'a'])
    }
    for k:=0;k<26;k++{
        for i:=0;i<26;i++{
            for j:=0;j<26;j++{
                if costs[i][j] > costs[i][k]+costs[k][j] {
						costs[i][j] = costs[i][k] + costs[k][j]
				}
            }
        }
    }
    result := 0
    for i := range source{
        if costs[source[i]-'a'][target[i]-'a'] == math.MaxInt32{
            return -1
        }else{
            result += costs[source[i]-'a'][target[i]-'a']
        }
    }
    return int64(result)
}

总结

如果点特别多并且图为稀疏图, 用map来保存边的权重并执行Floyd算法效率会更高, 避免了不连通的边的遍历.

1 个赞

刷题佬!

1 个赞

刷题佬!

1 个赞

刷题大佬

1 个赞

力扣大佬!

1 个赞

刷题佬!

1 个赞

From 算法 to 开发调优