专栏：50多种数据结构彻底征服

专栏：50多种经典图论算法全部掌握

4月2号京东黑板报发文称：达达员工薪酬将在今年升级至19薪，明年升级至20薪；此外，部分优秀达达员工将授予京东集团股票，这也是去年以来京东体系给员工第8次加薪。

说实话京东这加薪频率确实很高，一般公司都是一年一加薪，有的甚至一年还加不了一次，而京东自从去年开始宣布加薪以来，到现在一年时间已经加了8次了，明年还要继续加，要加到20薪，差不多相当于干一年快拿两年的工资了。

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

来看下今天的算法题，这题是LeetCode的第1347题：制造字母异位词的最小步骤数，难度是中等。

给你两个长度相等的字符串 s 和 t。每一个步骤中，你可以选择将 t 中的任一字符替换为另一个字符。返回使 t 成为 s 的字母异位词的最小步骤数。

字母异位词指字母相同，但排列不同（也可能相同）的字符串。

示例1：

输出：s = "bab", t = "aba" 输出：1 提示：用 'b' 替换 t 中的第一个 'a'，t = "bba" 是 s 的一个字母异位词。

示例2：

输出：s = "leetcode", t = "practice" 输出：5 提示：用合适的字符替换 t 中的 'p', 'r', 'a', 'i' 和 'c'，使 t 变成 s 的字母异位词。

  • 1 <= s.length <= 50000

  • s.length == t.length

  • s 和 t 只包含小写英文字母

问题分析

这题说的是改变最少的字母，让两个字符串成为字母异位词，所谓的字母异位词就是两个字符串中的字母相同，且每个字母出现的次数也是相同的，只不过是排序不同。

这题我们可以先统计两个字符串中每个字符个数的差，最后累加差值，那么最小操作次数就是这个差值的一半。比如字符串abb和aab，第一个字符串比第二个字符串少了一个a但多了一个b，差值是 2 ，我们只需要把第一个字符串中的b变成a，它俩就是字母异位词了。

JAVA：

public int minSteps(String s, String t) {     int n = s.length();     int[] mp = new int[128];     for (int i = 0; i < n; i++) {         mp[s.charAt(i)]++;         mp[t.charAt(i)]--;     }     int cnt = 0;     for (int num : mp)         cnt += Math.abs(num);     return cnt >> 1; }

C++：

public:     int minSteps(string s, string t) {         int n = s.length();         vector

  mp(128, 0);         for (int i = 0; i < n; i++) {             mp[s[i]]++;             mp[t[i]]--;         }         int cnt = 0;         for (int num: mp)             cnt += abs(num);         return cnt >> 1;     }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。