裁减近1.6万个工作岗位，员工还挺开心。

1月28日的时候，亚马逊突然宣布组织架构调整，裁掉近1.6万个工作岗位。亚马逊还表示：“在进行这些调整的同时，我们会继续在对公司未来至关重要的战略领域和职能部门招聘及投资”。

亚马逊还会竭尽全力为所有受影响的员工提供支持，将为大多数美国员工提供90天的内部职位调配时间（国际员工的调配时间将根据当地和国家/地区的要求而有所不同）。对于无法在亚马逊找到新职位或选择不寻找新职位的团队成员，亚马逊将提供遣散费、职业介绍服务、医疗保险福利等过渡支持。

裁员还提前90天通知，确实很不错了，我遇到很多企业裁员都是当天走人，怪不得网上一位亚马逊网友说被裁员了，还挺开心的。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第2976题：转换字符串的最小成本 I，难度是中等。

给你两个下标从 0 开始的字符串 source 和 target ，它们的长度均为 n 并且由小写英文字母组成。

另给你两个下标从 0 开始的字符数组 original 和 changed ，以及一个整数数组 cost ，其中 cost[i] 代表将字符 original[i] 更改为字符 changed[i] 的成本。

你从字符串 source 开始。在一次操作中，如果存在任意下标 j 满足 cost[j] == z 、original[j] == x 以及 changed[j] == y 。你就可以选择字符串中的一个字符 x 并以 z 的成本将其更改为字符 y 。

返回将字符串 source 转换为字符串 target 所需的最小成本。如果不可能完成转换，则返回 -1 。

注意，可能存在下标 i 、j 使得 original[j] == original[i] 且 changed[j] == changed[i] 。

示例1：

输入：source = "abcd", target = "acbe", original = ["a","b","c","c","e","d"], changed = ["b","c","b","e","b","e"], cost = [2,5,5,1,2,20] 输出：28 解释： 更改下标 1 处的值 'b' 为 'c' ，成本为 5 。 更改下标 2 处的值 'c' 为 'e' ，成本为 1 。 更改下标 2 处的值 'e' 为 'b' ，成本为 2 。 更改下标 3 处的值 'd' 为 'e' ，成本为 20 。 产生的总成本是 5 + 1 + 2 + 20 = 28 。

示例2：

输入：source = "aaaa", target = "bbbb", original = ["a","c"], changed = ["c","b"], cost = [1,2] 输入：source = “AAAA”，目标 = “bbbb”，原始 = [“a”，“c”]，更改 = [“c”，“b”]，成本 = [1,2] 输出：12 解释：要将字符 'a' 更改为 'b'： - 将字符 'a' 更改为 'c'，成本为 1 - 将字符 'c' 更改为 'b'，成本为 2 产生的总成本是 1 + 2 = 3。 将所有 'a' 更改为 'b'，产生的总成本是 3 * 4 = 12 。

• 1 <= source.length == target.length <= 10^5

• source、target 均由小写英文字母组成

• 1 <= cost.length== original.length == changed.length <= 2000

• original[i]、changed[i] 是小写英文字母

• 1 <= cost[i] <= 10^6

• original[i] != changed[i]

问题分析

这题说的是把字符串source转成target所需要的最小成本，source中的字符并不都是直接转成target中对应的字符的，有可能会通过多次转换。

这个就有点像图论算法中求任意两点之间的最短距离一样。我们用original表示出度节点，changed表示入度节点，cost表示两点之间的权重。那么我们就可以用original，changed和cost构成一个有加权边的有向图。

转换的时候就是求两点之间的最短距离，我们可以使用先求出任意两点之间的最短距离，然后再计算全部转换所需要的最小代价。

JAVA：

public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
    int INF = Integer.MAX_VALUE;
    int[][] g = newint[26][26];// 图的邻接矩阵表示
    for (int i = 0; i < 26; i++) {
        Arrays.fill(g[i], INF);// 每个点到其他的位置给一个很大的值
        g[i][i] = 0;// 每个点到自己的距离为0
    }

     // 初始化图的邻接矩阵
    for (int i = 0; i < original.length; i++) {
        int u = original[i] - 'a';
        int v = changed[i] - 'a';
        g[u][v] = Math.min(g[u][v], cost[i]);
    }

     // Floyd算法
    for (int k = 0; k < 26; k++) {// 中转点
        for (int i = 0; i < 26; i++) {// 起点
            for (int j = 0; j < 26; j++) {// 终点
                if (g[i][k] != INF && g[k][j] != INF)
                    g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }

     long ans = 0;
    for (int i = 0; i < source.length(); i++) {
        int u = source.charAt(i) - 'a';
        int v = target.charAt(i) - 'a';
        // 如果source.charAt(i)不能转成target.charAt(i)，返回-1.
        if (g[u][v] == INF)
            return -1;
        ans += g[u][v];
    }
    return ans;
}

C++：

public:
    long long minimumCost(string source, string target, vector &original,
                          vector &changed, vector &cost) {
        constint INF = INT_MAX;
        // 创建26x26的邻接矩阵
        vector 
                   
          int 
          >> g( 
          26 
          , vector< 
          int 
          >( 
          26 
          , INF)); 
          
 
                   
          // 初始化对角线为0 
          
 
                   
          for 
           ( 
          int 
           i =  
          0 
          ; i <  
          26 
          ; i++) 
          
 
                      g[i][i] =  
          0 
          ; 
          
 
          
 
                   
          // 初始化图的邻接矩阵 
          
 
                   
          for 
           ( 
          int 
           i =  
          0 
          ; i < original.size(); i++) { 
          
 
                       
          int 
           u = original[i] -  
          'a' 
          ; 
          
 
                       
          int 
           v = changed[i] -  
          'a' 
          ; 
          
 
                      g[u][v] = min(g[u][v], cost[i]); 
          
 
                  } 
          
 
          
 
                   
          // Floyd算法 
          
 
                   
          for 
           ( 
          int 
           k =  
          0 
          ; k <  
          26 
          ; k++) { 
          
 
                       
          for 
           ( 
          int 
           i =  
          0 
          ; i <  
          26 
          ; i++) { 
          
 
                           
          for 
           ( 
          int 
           j =  
          0 
          ; j <  
          26 
          ; j++) { 
          
 
                               
          if 
           (g[i][k] != INF && g[k][j] != INF) 
          
 
                                  g[i][j] = min(g[i][j], g[i][k] + g[k][j]); 
          
 
                          } 
          
 
                      } 
          
 
                  } 
          
 
          
 
                   
          long 
          long 
           ans =  
          0 
          ; 
          
 
                   
          for 
           ( 
          int 
           i =  
          0 
          ; i < source.length(); i++) { 
          
 
                       
          int 
           u = source[i] -  
          'a' 
          ; 
          
 
                       
          int 
           v = target[i] -  
          'a' 
          ; 
          
 
                       
          // 如果source[i]不能转成target[i]，返回-1 
          
 
                       
          if 
           (g[u][v] == INF) 
          
 
                           
          return 
           - 
          1 
          ; 
          
 
                      ans += g[u][v]; 
          
 
                  } 
          
 
                   
          return 
           ans; 
          
 
              } 
          
 
         

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解900多题，对算法题有自己独特的解题思路和解题技巧。