来源：编程网事
大家好，我就是那个在B站讲算法的「华南溜达虎」。
今天在网上看到一份小米员工职级和薪资一览表，感觉挺实用，分享给大家。小米的职级大致分成10个等级，从13级到22级，一般应届生入职就是13级，奋斗3年左右就可以达到15级，从16级开始有股权激励，到了18级就可以实现年薪百万了。为了方便大家对比，我直接把每一级别的薪资组成列出来如下，当然以下信息仅供参考。
14级：年薪30.5万（基本工资24.5万＋年终奖6万）
15级：年薪36.3万（基本工资31.5万＋年终奖4.8万）
16级：年薪62.6万（基本工资46万＋年终奖7.6万+股权9万）
17级：年薪76万（基本工资56万＋股权20万）
18级：年薪135万（基本工资60万＋年终奖15万＋股权60万）
19级（总监）：年薪252万
言归正传，今天我们来分享一道高频面试题「回文子串」。
题目描述
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
举个例子：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"
思路解析
首先我们可以通过暴力遍历的方式枚举字符串s所有的子串，统计其中回文串的个数，但是时间复杂度太高，这里不再详细的讲解。下面介绍一种中心扩散法。
分两情况来考虑：
回文子串的长度为奇数，这时我们就枚举回文子串所有可能的中心s[i]，0 <= i < s.length，以中心s[i]向两边扩散寻找所有的回文子串。如下图a就是回文串"cbabc"的中心。
回文子串的长度为偶数，这时我们就枚举回文子串所有可能的中心s[i]s[i+1]，0 <= i < s.length - 1，以中心s[i]s[i+1]向两边扩散寻找所有的回文子串。如下图aa就是回文串"cbaabc"的中心。
所以本题的关键是枚举回文子串的中心，下面我们给出c++和python两种代码实现。
C++代码
class Solution {
public:
int countSubstrings(string s) {
int res = 0;
int s_len = s.length();
for (int i = 0; i < s_len; ++i) {
//若回文串长度为奇数,以s[i]为中心向两边扩散寻找以s[i]为中心的所有回文子串
int left = i, right = i;
while (left >= 0 && right < s_len && s[left] == s[right]) {
++res;
--left;
++right;
}
//若回文串长度为偶数，以s[i]s[i+1]为中心向两边扩散寻找以s[i]s[i+1]为中心的所有回文子串
left = i;
right = i + 1;
while (left >= 0 && right < s_len && s[left] == s[right]) {
++res;
--left;
++right;
}
}
return res;
}
};
class Solution:
def countSubstrings(self, s: str) -> int:
res = 0
sLen = len(s)
for i in range(sLen):
# 若回文串长度为奇数，以s[i]为中心向两边扩散寻找以s[i]为中心的所有回文子串
left = i
right = i
while left >= 0and right < sLen and s[left] == s[right]:
res += 1
left -= 1
right += 1
# 若回文串长度为偶数，以s[i]s[i+1]为中心向两边扩散寻找以s[i]s[i+1]为中心的所有回文子串
left = i
right = i + 1
while left >= 0and right < sLen and s[left] == s[right]:
res += 1
left -= 1
right += 1
return res
特别声明：以上内容仅代表作者本人的观点或立场，不代表新浪财经头条的观点或立场。如因作品内容、版权或其他问题需要与新浪财经头条联系的，请于上述内容发布后的30天内进行。
海量资讯、精准解读，尽在新浪财经APP