专栏：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算法文档 。