專欄：50多種數(shù)據(jù)結構徹底征服
專欄：50多種經(jīng)典圖論算法全部掌握
昨天華為發(fā)文稱：華為2026屆實習生招聘計劃正式啟動，主要面向的是海內外高校學生，提供的實習崗位有研發(fā)類，銷售類等，工作地點包括深圳、北京、上海、杭州、南京、武漢、西安、成都、東莞、蘇州等地。
官方?jīng)]有具體公布招聘的人群要求，只提到了“高?！眱蓚€字，網(wǎng)上查了一下沒有“高?！边@個詞，只有高等學校，而高等學校包含普通高等學校，職業(yè)高等學校，成人高等學校，但結合以往華為招聘信息來看，本次招聘應該是高校本科生起步。如果有需要的可以點擊下面的原文鏈接去注冊簡歷投遞。
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第132：分割回文串 II。
問題描述
來源：LeetCode第132題
難度：困難
給你一個字符串 s，請你將 s 分割成一些子串，使每個子串都是回文串。返回符合要求的最少分割次數(shù) 。
示例1：
輸入：s = "aab" 輸出：1 解釋：只需一次分割就可將 s 分割成 ["aa","b"] 這樣兩個回文子串。
示例2：
輸入：s = "a" 輸出：0
1 <= s.length <= 2000
s 僅由小寫英文字母組成
問題分析
這題讓把字符串分割成一些子串，并且每個子串都是回文串，求最小分割次數(shù)。之前我們講過 ，之前那道題讓返回的是所有可能的分割方案，而這題讓求的是最小分割次數(shù)。
這題我們可以使用動態(tài)規(guī)劃來解決，定義dp[i]表示前 i 個字符的最小分割次數(shù)。
1，如果前 i 個字符構成的子串s[0,i]是回文串，則不需要分割，也就是dp[i]=0。
2，否則就嘗試分割，從前 i 個字符中不斷截取子串s[j,i]，判斷子串s[j,i]是否是回文串，如果是回文串，表示子串s[j,i]可以單獨分割，然后前面分割的最少次數(shù)就是dp[j-1]，這里要枚舉 j ，求最小的dp[i]，所以dp[i]=min(dp[i],dp[j-1]+1); 。
為了快速判斷一個子串是否是回文串，我們需要先對所有的子串進行預處理，提前知道哪些是回文的，哪些不是。
JAVA：
public int minCut(String s) { int length = s.length(); int[] dp = newint[length]; // 判斷子串[i…j]是否是回文串 boolean[][] palindrome = newboolean[length][length]; for (int j = 0; j < length; j++) { for (int i = 0; i <= j; i++) { // 如果子串s[j,i]是回文串，則兩邊的字符s[i]和s[j]必須相同，并且 // 中間的子串s[i+1,j-1]如果存在，也必須是回文串。 if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || palindrome[i + 1][j - 1])) palindrome[i][j] = true; } } // 字符串s的回文子串最大也只能是字符串的長度，這里都默認初始化為最大值。 Arrays.fill(dp, length); for (int i = 0; i < length; i++) { // 如果子串s[0,i]本身就是回文的，就不需要分隔。 if (palindrome[0][i]) { dp[i] = 0; } else { // 否則就要分隔，找出最小的分隔方案 for (int j = 0; j <= i; ++j) { if (palindrome[j][i]) dp[i] = Math.min(dp[i], dp[j - 1] + 1); } } } return dp[length - 1]; }C++：
public: int minCut(string s) { int length = s.length(); // 判斷子串[i…j]是否是回文串 vector
> palindrome(length, vector
(length, false)); for (int j = 0; j < length; j++) { for (int i = 0; i <= j; i++) { // 如果子串s[j,i]是回文串，則兩邊的字符s[i]和s[j]必須相同，并且 // 中間的子串s[i+1,j-1]如果存在，也必須是回文串。 if (s[i] == s[j] && (j - i <= 2 || palindrome[i + 1][j - 1])) palindrome[i][j] = true; } } // 字符串s的回文子串最大也只能是字符串的長度，這里都默認初始化為最大值。 vector
dp(length, length); for (int i = 0; i < length; i++) { // 如果子串s[0,i]本身就是回文的，就不需要分隔。 if (palindrome[0][i]) { dp[i] = 0; } else { // 否則就要分隔，找出最小的分隔方案 for (int j = 0; j <= i; ++j) { if (palindrome[j][i]) dp[i] = min(dp[i], dp[j - 1] + 1); } } } return dp[length - 1]; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數(shù)據(jù)結構和算法 的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼