專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服

專欄：50多種經(jīng)典圖論算法全部掌握

4月2號(hào)京東黑板報(bào)發(fā)文稱：達(dá)達(dá)員工薪酬將在今年升級(jí)至19薪，明年升級(jí)至20薪；此外，部分優(yōu)秀達(dá)達(dá)員工將授予京東集團(tuán)股票，這也是去年以來京東體系給員工第8次加薪。

說實(shí)話京東這加薪頻率確實(shí)很高，一般公司都是一年一加薪，有的甚至一年還加不了一次，而京東自從去年開始宣布加薪以來，到現(xiàn)在一年時(shí)間已經(jīng)加了8次了，明年還要繼續(xù)加，要加到20薪，差不多相當(dāng)于干一年快拿兩年的工資了。

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

來看下今天的算法題，這題是LeetCode的第1347題：制造字母異位詞的最小步驟數(shù)，難度是中等。

給你兩個(gè)長(zhǎng)度相等的字符串 s 和 t。每一個(gè)步驟中，你可以選擇將 t 中的任一字符替換為另一個(gè)字符。返回使 t 成為 s 的字母異位詞的最小步驟數(shù)。

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

示例1：

輸出：s = "bab", t = "aba" 輸出：1 提示：用 'b' 替換 t 中的第一個(gè) 'a'，t = "bba" 是 s 的一個(gè)字母異位詞。

示例2：

輸出：s = "leetcode", t = "practice" 輸出：5 提示：用合適的字符替換 t 中的 'p', 'r', 'a', 'i' 和 'c'，使 t 變成 s 的字母異位詞。

• 1 <= s.length <= 50000

• s.length == t.length

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

問題分析

這題說的是改變最少的字母，讓兩個(gè)字符串成為字母異位詞，所謂的字母異位詞就是兩個(gè)字符串中的字母相同，且每個(gè)字母出現(xiàn)的次數(shù)也是相同的，只不過是排序不同。

這題我們可以先統(tǒng)計(jì)兩個(gè)字符串中每個(gè)字符個(gè)數(shù)的差，最后累加差值，那么最小操作次數(shù)就是這個(gè)差值的一半。比如字符串a(chǎn)bb和aab，第一個(gè)字符串比第二個(gè)字符串少了一個(gè)a但多了一個(gè)b，差值是 2 ，我們只需要把第一個(gè)字符串中的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;     }

筆者簡(jiǎn)介

博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個(gè)算法網(wǎng)站中累計(jì)做題2000多道，在公眾號(hào)中寫算法題解800多題，對(duì)算法題有自己獨(dú)特的解題思路和解題技巧，喜歡的可以給個(gè)關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。