專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
4月2號京東黑板報發(fā)文稱：達達員工薪酬將在今年升級至19薪，明年升級至20薪；此外，部分優(yōu)秀達達員工將授予京東集團股票，這也是去年以來京東體系給員工第8次加薪。
說實話京東這加薪頻率確實很高，一般公司都是一年一加薪，有的甚至一年還加不了一次，而京東自從去年開始宣布加薪以來，到現(xiàn)在一年時間已經(jīng)加了8次了，明年還要繼續(xù)加，要加到20薪，差不多相當(dāng)于干一年快拿兩年的工資了。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第1347題：制造字母異位詞的最小步驟數(shù)，難度是中等。
給你兩個長度相等的字符串 s 和 t。每一個步驟中，你可以選擇將 t 中的任一字符替換為另一個字符。返回使 t 成為 s 的字母異位詞的最小步驟數(shù)。
字母異位詞指字母相同，但排列不同（也可能相同）的字符串。
示例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 只包含小寫英文字母
問題分析
這題說的是改變最少的字母，讓兩個字符串成為字母異位詞，所謂的字母異位詞就是兩個字符串中的字母相同，且每個字母出現(xiàn)的次數(shù)也是相同的，只不過是排序不同。
這題我們可以先統(tǒng)計兩個字符串中每個字符個數(shù)的差，最后累加差值，那么最小操作次數(shù)就是這個差值的一半。比如字符串a(chǎn)bb和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; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼