專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近一網友發文稱：在字節一面二面三面都很順利，面試官還夸他優秀，結果三面的時候直接把他給掛了。另一網友評論說他們組會把面試者照片發到群里讓大家選哪個最好看選擇哪個。我聽過卡學歷，卡年齡，甚至卡性別的，但卡顏值的還是第一次聽過。

如果是面向大眾的工作，比如車模，銷售，服務員，卡顏值還能理解，畢竟他們面向的是客戶，顏值高的確有優勢。如果是對著電腦工作，卡顏值就沒必要了。不過一般來說一份工作不會只找一個人來面試，如果所有面試者都很優秀，學歷，年齡都難分伯仲，卡顏值也未嘗不可。

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

來看下今天的算法題，這題是LeetCode的第1400題：構造 K 個回文字符串，難度是中等。

給你一個字符串 s 和一個整數 k 。請你用 s 字符串中所有字符構造 k 個非空回文串。如果你可以用 s 中所有字符構造 k 個回文字符串，那么請你返回 True ，否則返回 False 。

示例1：

輸入：s = "annabelle", k = 2 輸出：true 解釋：可以用 s 中所有字符構造 2 個回文字符串。 一些可行的構造方案包括："anna" + "elble"，"anbna" + "elle"，"anellena" + "b"

示例2：

輸入：s = "leetcode", k = 3 輸出：false 解釋：無法用 s 中所有字符構造 3 個回文串。

輸入：s = "true", k = 4 輸出：true 解釋：唯一可行的方案是讓 s 中每個字符單獨構成一個字符串。

• 1 <= s.length <= 10^5

• s 中所有字符都是小寫英文字母。

• 1 <= k <= 10^5

問題分析

這題說的是使用字符串中的所有字符構造 k 個回文串，如果字符串的長度小于 k ，無論如何也是完成不了的。如果字符串的長度不小于 k ，我們需要統計字符串中每個字符出現的次數。

如果每個字符出現的次數都是偶數，我們可以構造成任意 1<=k<=n 個回文子串，比如字符串aabbcccc，可構造的回文子串如下：

[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]

如果某個字符出現的個數是奇數，要想構造最少的回文串，該字符串必須要在回文串的中間，比如aaabbcc要構成一個回文串，則aaa必須要放到中間，如果有構成兩個回文串則不需要放到中間。

再來看一個示例，比如字符串aaabbbcc，如果要構成一個回文串，無論如何也是實現不了的，因為字符 a 和字符 b 出現的次數都是奇數，但要構成兩個回文串是可以的。

所以我們可以得出如果字符串中出現奇數次的字符個數大于 k 的時候，我們是無法分割成 k 個回文串的，否則是可以的。我們只需要統計出現奇數次字符的個數即可。

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;// 奇數的個數     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;// 奇數的個數         for (constauto cnt: mp) {             if (cnt % 2 == 1)                 odd++;         }         return k >= odd;     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。