專欄：50多種數(shù)據(jù)結(jié)構(gòu)徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
最近一網(wǎng)友發(fā)文稱：在字節(jié)一面二面三面都很順利，面試官還夸他優(yōu)秀，結(jié)果三面的時候直接把他給掛了。另一網(wǎng)友評論說他們組會把面試者照片發(fā)到群里讓大家選哪個最好看選擇哪個。我聽過卡學(xué)歷，卡年齡，甚至卡性別的，但卡顏值的還是第一次聽過。
如果是面向大眾的工作，比如車模，銷售，服務(wù)員，卡顏值還能理解，畢竟他們面向的是客戶，顏值高的確有優(yōu)勢。如果是對著電腦工作，卡顏值就沒必要了。不過一般來說一份工作不會只找一個人來面試，如果所有面試者都很優(yōu)秀，學(xué)歷，年齡都難分伯仲，卡顏值也未嘗不可。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第1400題：構(gòu)造 K 個回文字符串，難度是中等。
給你一個字符串 s 和一個整數(shù) k 。請你用 s 字符串中所有字符構(gòu)造 k 個非空回文串。如果你可以用 s 中所有字符構(gòu)造 k 個回文字符串，那么請你返回 True ，否則返回 False 。
示例1：
輸入：s = "annabelle", k = 2 輸出：true 解釋：可以用 s 中所有字符構(gòu)造 2 個回文字符串。 一些可行的構(gòu)造方案包括："anna" + "elble"，"anbna" + "elle"，"anellena" + "b"
示例2：
輸入：s = "leetcode", k = 3 輸出：false 解釋：無法用 s 中所有字符構(gòu)造 3 個回文串。
示例3：
輸入：s = "true", k = 4 輸出：true 解釋：唯一可行的方案是讓 s 中每個字符單獨構(gòu)成一個字符串。
1 <= s.length <= 10^5
s 中所有字符都是小寫英文字母。
1 <= k <= 10^5
問題分析
這題說的是使用字符串中的所有字符構(gòu)造 k 個回文串，如果字符串的長度小于 k ，無論如何也是完成不了的。如果字符串的長度不小于 k ，我們需要統(tǒng)計字符串中每個字符出現(xiàn)的次數(shù)。
如果每個字符出現(xiàn)的次數(shù)都是偶數(shù)，我們可以構(gòu)造成任意 1<=k<=n 個回文子串，比如字符串a(chǎn)abbcccc，可構(gòu)造的回文子串如下：
[abccccba]
[abba,cccc]
[aa,bb,cccc]
[aa,bb,cc,cc]
[aa,bb,cc,c,c]
[aa,bb,c,c,c,c]
[aa,b,b,c,c,c,c]
[a,a,b,b,c,c,c,c]
如果某個字符出現(xiàn)的個數(shù)是奇數(shù)，要想構(gòu)造最少的回文串，該字符串必須要在回文串的中間，比如aaabbcc要構(gòu)成一個回文串，則aaa必須要放到中間，如果有構(gòu)成兩個回文串則不需要放到中間。
再來看一個示例，比如字符串a(chǎn)aabbbcc，如果要構(gòu)成一個回文串，無論如何也是實現(xiàn)不了的，因為字符 a 和字符 b 出現(xiàn)的次數(shù)都是奇數(shù)，但要構(gòu)成兩個回文串是可以的。
所以我們可以得出如果字符串中出現(xiàn)奇數(shù)次的字符個數(shù)大于 k 的時候，我們是無法分割成 k 個回文串的，否則是可以的。我們只需要統(tǒng)計出現(xiàn)奇數(shù)次字符的個數(shù)即可。
JAVA：
public boolean canConstruct(String s, int k) { if (k > s.length()) return false; int[] mp = new int[128]; for (char ch : s.toCharArray()) mp[ch]++; int odd = 0;// 奇數(shù)的個數(shù) for (int cnt : mp) { if (cnt % 2 == 1) odd++; } return k >= odd; }C++：
public: bool canConstruct(string s, int k) { if (k > s.length()) returnfalse; vector
mp(128, 0); for (constauto &ch: s) mp[ch]++; int odd = 0;// 奇數(shù)的個數(shù) for (constauto cnt: mp) { if (cnt % 2 == 1) odd++; } return k >= odd; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結(jié)構(gòu)和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關(guān)注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼