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

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

傳智教育大家應該都比較熟悉，也就是我們經常聽到的傳智播客，黑馬程序員，即使沒有在那里培訓過，也會在網上經常看到。2025年4月22日傳智教育股票暫停交易，4月23日股票被st（Special Treatment）了，開盤即跌停。

4月21日，傳智教育公布2024年年報，公司營業收入為2.46億元，同比下降54.0%；歸母凈利潤虧損1.34億元，同比下降956.8%；扣非歸母凈利潤虧損1.48億元。

我印象中IT行業有兩大培訓機構，一個是達內，由于學員的減少，后來轉型搞少兒編程，改名叫童程童美，在去年的時候直接跑路。另一個就是傳智播客，雖然現在沒有倒閉，但由于一直虧損，上市4年多，昨天被st了，有退市的風險。

中國互聯網真正的發展是從上世紀90年代開始的，我們現在常見的一大批互聯網公司，比如：網易，新浪，搜狐，百度，騰訊，阿里等，都是在那個年代創建的，（百度創建最晚，是2000年1月1日）。

然而好景不長，2000年3月美國納斯達克指數崩盤，美國互聯網泡沫破裂，后來蔓延到全球，中國互聯網行業也受到波及。

后來的幾年互聯網發展都是以PC端為主，還算是平靜，沒有太大波瀾，也沒有出現需求過熱。2007年IPhone和Android的橫空出世打破了這種平靜（IOS是2007年1月發布，Android是2007年11月發布），后來很快蔓延到國內。

2011年諾基亞在中國市場的份額已降至19.7%，已經被智能手機反超，而會移動開發的程序員少之又少，已經遠遠不能滿足公司的需求，大概從2012年開始，中國大地上搞移動開發的培訓機構如雨后春筍般的成立了起來。

這其中有很多不知名的培訓機構，到底有多家，我沒有統計過，很多培訓機構只要你認字，交錢都能培訓，市場一片火熱。我記得在2014年的時候，有次招聘網站上我的簡歷沒有隱藏，結果一上午接到十幾個電話，邀我去面試，實際上我并沒有投，只是想看看行情怎么樣，結果下午我趕緊隱藏了。

在加上后來2015年p2p，現金貸等一大批互聯網金融公司的出現，更加導致了程序員的短缺，可以這樣說，那個時候只有招不到程序員的公司，沒有找不到工作的程序員。

但很遺憾，這種好景持續時間并不長，2015年底，e租寶500億暴雷，徹底撕下了互聯網金融的遮羞布，后來p2p暴雷不斷，很多人的投資打了水漂。2017年12月現金貸app全部強制下架，已經上架的也在陸續下架，p2p的經營資質也在不斷收緊，資質不夠的也都在下架。

隨著互聯網金融的退去，導致了一大批程序員失業，后來2019年底疫情又有不少公司倒閉，其中我之前所在的一家公司就是沒抗住疫情，全部裁員。

疫情過了之后，很多公司又在降本增效，有不少在大規模的裁員，程序員的就業更加艱難，導致一份工作有幾百人來投的現象出現。在加上這幾年智能Ai的出現，雖然不會取代程序員，但它可以大大減少程序員的工作量，使程序員的崗位又進一步變少。

怎么說呢，IT行業從曾經的火熱到現在歸于平靜（不算沒落，我個人認為比其他行業稍微好一點），我都經歷過。其實從達內的轉型到跑路，以及傳智教育可能被退市，我們應該能發現，IT行業程序員已經太多了，不需要他們培訓了。這里并不是說IT行業不行了，從最近可以看出，IT行業還是有很大的市場的，只不過競爭也會更加激烈。

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

來看下今天的算法題，這題是LeetCode的第1525題：字符串的好分割數目，難度是中等。

給你一個字符串 s ，一個分割被稱為 「好分割」 當它滿足：將 s 分割成 2 個字符串 p 和 q ，它們連接起來等于 s 且 p 和 q 中不同字符的數目相同。請你返回 s 中好分割的數目。

示例1：

輸入：s = "aacaba" 輸出：2 解釋：總共有 5 種分割字符串 "aacaba" 的方法，其中 2 種是好分割。 ("a", "acaba") 左邊和右邊分別包含 1 個和 3 個不同的字符。 ("aa", "caba") 左邊和右邊分別包含 1 個和 3 個不同的字符。 ("aac", "aba") 左邊和右邊分別包含 2 個和 2 個不同的字符。這是一個好分割。 ("aaca", "ba") 左邊和右邊分別包含 2 個和 2 個不同的字符。這是一個好分割。 ("aacab", "a") 左邊和右邊分別包含 3 個和 1 個不同的字符。

示例2：

輸入：s = "abcd" 輸出：1 解釋：好分割為將字符串分割成 ("ab", "cd") 。

• s 只包含小寫英文字母。

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

問題分析

這題說的是把字符串分割成兩個子串，并且這兩個子串中不同的字符數量相同，問有多少種分法。

首先我們統計字符串中不同字符的個數，然后再遍歷該字符串，分別計算遍歷過的子串中不同字符的個數，和未遍歷的子串中不同字符的個數，如果個數相同，說明遍歷過的子串和未遍歷過的子串是可以劃分的，最后累加可劃分的次數即可。

JAVA：

public int numSplits(String s) {     int left = 0, ans = 0;     int[] mp1 = newint[26];// 記錄每個字符的個數。     int[] mp2 = newint[26];     int right = 0;// 總的字符數，相同的字符只能算一個。     for (char ch : s.toCharArray()) {         if (mp1[ch - 'a']++ == 0)             right++;     }     for (char ch : s.toCharArray()) {         if (mp2[ch - 'a']++ == 0)// 出現一個新字符             left++;         if (--mp1[ch - 'a'] == 0)// 消失一個字符。             right--;         if (left == right)// 左邊的和右邊的字符一樣             ans++;     }     return ans; }

C++：

public:     int numSplits(string s) {         int left = 0, ans = 0;         vector

  mp1(26, 0);// 記錄每個字符的個數。         vector

  mp2(26, 0);         int right = 0;// 總的字符數，相同的字符只能算一個。         for (constauto &ch: s) {             if (mp1[ch - 'a']++ == 0)                 right++;         }         for (constauto &ch: s) {             if (mp2[ch - 'a']++ == 0)// 出現一個新字符                 left++;             if (--mp1[ch - 'a'] == 0)// 消失一個字符。                 right--;             if (left == right)// 左邊的和右邊的字符一樣                 ans++;         }         return ans;     }

筆者簡介

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