【C++算法刷题营地】—— 【string类面试题】Cyber顶级骇客带你速刷 C++ string类 中的常见算法题

⚡ CYBER_PROFILE ⚡
/// SYSTEM READY ///

[WARNING]: DETECTING HIGH ENERGY

🌊 🌉 🌊 心手合一 · 水到渠成

---------------------------------------
Running Process: 100% | Latency: 0ms

索引与导读

• 一、字符串转换
  • 1）字符串转换整数
    • 关键点拨
    • 完整代码
    • 最直接的替代接口：stoi
    • 小试牛刀：整数转字符串
  • 2）字符串相加
    • 关键点拨
    • 完整代码
  • 3）仅仅反转字母
    • 关键点拨
    • 完整代码
  • 4）反转字符串
    • 4.1）反转字符串|
    • 关键点拨
    • 完整代码
    • 4.2）反转字符串||：区间部分反转
    • 关键点拨
    • 完整代码
    • 4.3）反转字符串|||：反转字符串中的单词
    • 关键点拨
    • 完整代码
  • 5）字符串中第一个唯一字符
    • 关键点拨
    • 完整代码
  • 6）字符串里最后一个单词的长度
    • 关键点拨
    • 完整代码
  • 7）验证一个字符串是否回文
    • 1）验证回文串|
    • 关键点拨
    • 完整代码
    • 2）验证回文串||
    • 关键点拨
    • 完整代码
    • 3）验证回文串|||
    • 关键点拨
    • 完整代码
    • 4）验证回文串||||
    • 关键点拨
    • 完整代码
  • 8）字符串相乘
    • 关键点拨
    • 完整代码
  • 9）找出第N个二进制字符串中的第K位
    • 关键点拨
    • 完整代码
  • 10）无重复字符的排列组合
    • 关键点拨
    • 完整代码
  • 11）回文子串
    • 关键点拨
    • 完整代码
  • 12）最长回文子串
    • 关键点拨
    • 完整代码
  • 13）最长回文子序列
    • 关键点拨
      • 状态转移方程
    • 完整代码
  • 暂时就这么多题 后续还会继续添加在这篇文章上面哦
• 💻结尾— 核心连接协议

一、字符串转换

1）字符串转换整数

🔗Lucy的空间骇客裂缝：牛客网原题

关键点拨

• 字符转数字：str[i] - '0' 利用了 ASCII 码的连续性，这是最基础的技巧。
• 非法输入：题目特别提到 1a33 返回 0，所以在 for 循环中一旦遇到 !isdigit() 的情况就得立刻“跳机”。
• 复杂度：
  • 时间复杂度：( O(n) )，只需扫描一遍字符串。
  • 空间复杂度：( O(1) )，只使用了常数个变量。

完整代码

#include<iostream>#include<string>#include<climits>// 包含 INT_MAX 和 INT_MINusingnamespace std;classSolution{public:intStrToInt(const string& str){// 优化点1：使用常量引用，避免拷贝if(str.empty())return0;int i =0;int n = str.length();// 优化点2：处理前导空格（模拟标准库行为，增强健壮性）while(i < n && str[i]==' '){ i++;}if(i == n)return0;// 优化点3：紧凑的符号处理int sign =1;if(str[i]=='-'|| str[i]=='+'){ sign =(str[i++]=='-')?-1:1;}long res =0;for(; i < n;++i){// 优化点4：利用 unsigned 判断快速筛选非数字字符if(static_cast<unsigned>(str[i]-'0')>9){return0;// 题目要求：出现非合法字符返回 0} res = res *10+(str[i]-'0');// 优化点5：提前溢出保护// 只要 res 超过 INT_MAX，根据符号返回 0 或边界值if(res > INT_MAX){return(sign ==1)?0:(res ==(long)INT_MAX +1? INT_MIN :0);// 注意：题目要求非法或溢出通常返回 0，这里严格遵循你原代码的 0 返回逻辑}}returnstatic_cast<int>(sign * res);}};

最直接的替代接口：stoi

#include<string>usingnamespace std;classSolution{public:intstrToInt(string str){if(str.empty())return0;try{// stoi 会自动处理 '+' 和 '-' returnstoi(str);}catch(...){// 如果字符串非法（比如 "abc"）或溢出，会抛出异常return0;}}};

小试牛刀：整数转字符串

classIntToStr{IntToStr(longlong n){if(n ==0){return;}elseif(n <0){ cout <<"-";convert(n <0?-(longlong) n : n);}else{convert(n);}}private:voidconvert(longlong n){if(n ==0)return;convert(n /10); n =(n %10)+'0'; cout << n;}};

在 C++ 中，最现代且安全的方式是to_stringC++11 及以后: to_string(value)C 语言: sprintf(str, "%d", value) 或 itoa()

2）字符串相加

🔗Lucy的空间骇客裂缝：Leetcode

关键点拨

1. 从后往前遍历： 使用两个指针分别指向 num1 和 num2 的末尾。
2. 逐位相加： 将对应位置的数字相加，同时加上来自低位的进位（carry）。
3. 处理进位：

• 当前位的数值 = (n1 + n2 + carry) % 10
• 新的进位 = (n1 + n2 + carry) / 10

4. 反转结果： 因为我们是从个位开始计算并依次添加的，最后得到的字符串需要反转过来。

完整代码

classSolution{public: string addStrings(string num1, string num2){//定义双指针int i = num1.length()-1;int j = num2.length()-1;//定义进位int carry =0;//定义初始字符串 string res ="";while(i >=0|| j >=0|| carry !=0){//使用三目运算符的目的是 防止两个字符串长度不同出现越界访问int n1 =(i >=0)? num1[i]-'0':0;int n2 =(j >=0)? num2[j]-'0':0;int sum = n1 + n2 + carry; res +=to_string(sum %10);//向字符串末尾追加（append）结果的顺序 carry = sum /10;//指针前移 i--; j--;}reverse(res.begin(), res.end());return res;}};

3）仅仅反转字母

🔗Lucy的空间骇客裂缝：Leetcode原题

关键点拨

1. 初始化双指针： 设置一个左指针 left 指向字符串的起始位置（索引 0），设置一个右指针 right 指向字符串的末尾位置（索引 s.length() - 1）。
2. 向中间遍历： 当 left < right 时，执行以下循环：
   • 如果 left 指向的字符不是英文字母，则 left 向右移动一步（left++）。
   • 如果 right 指向的字符不是英文字母，则 right 向左移动一步（right--）。
   • 如果 left 和 right 指向的都是英文字母，则交换这两个字符的位置。交换完成后，left 右移，right 左移，继续下一轮比较。
3. 返回结果： 当指针相遇或交错时，遍历结束，返回修改后的字符串 s。

完整代码

classSolution{public:boolisLetter(char c){return(c >='a'&& c <='z')||(c >='A'&& c <='Z');} string reverseOnlyLetters(string s){int left =0;int right = s.length()-1;while(left < right){// 注意：这里应该是 !isLetter，因为我们要跳过非字母，停在字母上while(left < right &&!isLetter(s[left])){ left++;}while(left < right &&!isLetter(s[right])){ right--;}if(left < right){// 修正 1：参数写错了，应该是 s[left] 和 s[right]swap(s[left], s[right]); left++; right--;}}return s;}};

4）反转字符串

4.1）反转字符串|

🔗Lucy的空间骇客裂缝：Leetcode原题

关键点拨

1. 设置两个指针：left 指向数组起始位置，right 指向数组末尾。
2. 当 left < right 时，交换两个指针所指向的字符。
3. 交换后，将 left 向右移动一位，right 向左移动一位。
4. 重复上述过程，直到两个指针相遇，反转完成

完整代码

classSolution{public:voidreverseString(vector<char>& s){int left =0;int right = s.size()-1;while(left < right){// 使用 STL 的 swap 函数进行原地交换swap(s[left], s[right]);// 缩小区间 left++; right--;}}};

4.2）反转字符串||：区间部分反转

🔗Lucy的空间骇客裂缝：Leetcode原题

关键点拨

1. 步进：每次移动 (2k) 个单位。
2. 反转范围：在每一个 (2k) 的区间内，反转 前 (k) 个 字符。
3. 边界处理：
   • 如果剩余字符 不足 (k) 个，全部反转。
   • 如果剩余字符在 (k) 到 (2k) 之间，反转前 (k) 个。
   • 其实这两条可以合并为一句话：反转从当前位置 (i) 开始，长度为 (k) 的区间；如果不够 (k) 个，就反转到末尾。

完整代码

classSolution{public: string reverseStr(string s,int k){// 每次跳跃 2k 步for(int i =0; i < s.length(); i +=2* k){// 判断反转的右边界：// 如果 i + k 小于字符串长度，反转前 k 个；// 否则（剩余少于 k 个），反转到字符串末尾。if(i + k <= s.length()){reverse(s.begin()+ i, s.begin()+ i + k);}else{reverse(s.begin()+ i, s.end());}}return s;}};

4.3）反转字符串|||：反转字符串中的单词

🔗Lucy的空间骇客裂缝：Leetcode原题

关键点拨

1. std::reverse 的妙用
   C++ 标准库 <algorithm> 提供的 reverse(first, last) 是反转容器元素的利器。它直接修改原容器，底层实现通常也是双指针交换。
2. 边界控制
   在处理 s[i] != ' ' 时，必须先判断 i < length。在 C++ 中，访问越界会导致未定义行为（Undefined Behavior），这在编写稳健的代码时非常关键。

完整代码

classSolution{public: string reverseWords(string s){int n = s.length();int left =0;// 左指针：指向单词的起始字符while(left < n){int right = left;// 右指针：从左指针位置开始向后寻找空格// 1. 移动右指针，直到遇到空格或到达字符串末尾while(right < n && s[right]!=' '){ right++;}// 此时 [left, right-1] 就是一个完整的单词// 2. 反转该区间内的字符// 注意：std::reverse 接受 [first, last) 这种左闭右开区间reverse(s.begin()+ left, s.begin()+ right);// 3. 更新左指针，跳过当前的空格，指向下一个单词的可能起点 left = right +1;}return s;}};

5）字符串中第一个唯一字符

🔗Lucy的空间骇客裂缝：Leetcode原题

关键点拨

1. 选择合适的数据结构（计数器）
   题目给出了一个关键提示：“只包含小写字母”。
   • 小写字母只有 26 个（'a' 到 'z'）。
   • 我们可以直接使用一个长度为 26 的整型数组 count[26] 来记录每个字母出现的次数，而不是使用复杂的哈希表。
   • 映射逻辑：字符 'a' 对应索引 0，'b' 对应 1……以此类推。计算公式为：
     [ \text{index} = s[i] - ‘a’ ]
2. 第一次遍历：统计频率
   • 从头到尾扫描一遍字符串 s。
   • 每遇到一个字符，就在计数器数组对应的位置上加 1。
   • 目的：这一步完成后，我们就知道了字符串中每个字母总共出现了多少次。
3. 第二次遍历：寻找目标
   • 再次从头到尾扫描字符串 s（注意：必须按字符串的原有顺序遍历）。
   • 检查当前字符在计数器数组中的数值。
   • 判定条件：如果某个字符的计数等于 1，说明它是第一个在整个字符串中只出现一次的字符。
   • 动作：直接返回当前的索引 i。
4. 边界处理
   • 如果第二次遍历结束了，依然没有找到计数为 1 的字符，说明所有字符都重复了（或者字符串为空，但题目提示长度 ≥ 1）。
   • 按照题目要求，返回 -1。

完整代码

classSolution{public:intfirstUniqChar(std::string s){// 使用原生静态数组，大小固定为 26（对应 a-z）// 初始化为 0int count[26]={0};// 第一次遍历：统计每个字符出现的频率// s.length() 返回的是 size_t，转换为 int 匹配索引int n = s.length();for(int i =0; i < n; i++){// 通过 s[i] - 'a' 将字符映射到 0-25 的索引 count[s[i]-'a']++;}// 第二次遍历：找到第一个出现次数为 1 的字符for(int i =0; i < n; i++){if(count[s[i]-'a']==1){return i;}}// 如果遍历结束都没有找到，返回 -1return-1;}};

6）字符串里最后一个单词的长度

🔗Lucy的空间骇客裂缝：Leetcode原题

关键点拨

1. 从后往前找：最快的方法是从字符串末尾开始向前遍历，跳过末尾可能存在的空格（虽然题目说单词间单个空格，但防御性编程总没错），遇到第一个非空格字符开始计数，直到遇到下一个空格或到达字符串开头。
2. 内置拆分：利用语言自带的 split() 或 StringTokenizer 快速定位最后一个元素。

完整代码

classStringHandler{public:intgetLastWordLength(const string& s){int length =0;int n = s.length();// 从后往前遍历for(int i = n -1; i >=0; i--){// 如果遇到空格if(s[i]==' '){// 如果已经开始计数了，说明最后一个单词结束了if(length >0){break;}// 如果还没开始计数就遇到空格（处理末尾多余空格），继续向前找continue;} length++;}return length;}};

7）验证一个字符串是否回文

1）验证回文串|

🔗Lucy的空间骇客裂缝：Leetcode原题

关键点拨

1. 设置两个指针：left 指向字符串开头，right 指向字符串末尾。
2. 跳过非法字符： 如果指针指向的不是字母或数字，就继续移动（left++ 或 right--）。
3. 比较字符： 将两端的字符都转为小写后进行比较。如果不相等，直接返回 false。
4. 循环结束： 如果 left >= right，说明所有有效字符都匹配成功，返回 true。

完整代码

classSolution{public:// 手动实现：判断是否为字母或数字boolisAlphaNum(char c){return(c >='a'&& c <='z')||(c >='A'&& c <='Z')||(c >='0'&& c <='9');}// 手动实现：统一转小写chartoLower(char c){if(c >='A'&& c <='Z'){return c +32;// 大写转小写}return c;}boolisPalindrome(string s){int left =0;int right = s.length()-1;while(left < right){// 跳过非字母数字while(left < right &&!isAlphaNum(s[left])){ left++;}while(left < right &&!isAlphaNum(s[right])){ right--;}// 比较if(toLower(s[left])!=toLower(s[right])){returnfalse;} left++; right--;}returntrue;}};

2）验证回文串||

🔗Lucy的空间骇客裂缝：Leetcode原题

关键点拨

由于字符串长度可达 ( 10^5 )，我们不能尝试删除每一个字符再进行检查（那样复杂度会达到 ( O(n^2) )）。最有效的做法是使用双指针法：

1. 首尾推进：设定两个指针 left 和 right，分别指向字符串的头和尾。
2. 逐一比对：
   • 如果 s[left] == s[right]，则两个指针同时向中间移动。
   • 如果 s[left] != s[right]，说明遇到了阻碍。此时我们有一次机会尝试删除一个字符：
     • 方案 A：忽略左侧字符，检查剩下的中间部分 [left + 1, right] 是否是回文。
     • 方案 B：忽略右侧字符，检查剩下的中间部分 [left, right - 1] 是否是回文。
3. 结论：如果方案 A 或方案 B 其中之一成立，则返回 true；否则返回 false。

完整代码

classSolution{public:// 辅助函数：检查子串是否为纯回文boolisPalindrome(const std::string& s,int left,int right){while(left < right){if(s[left++]!= s[right--]){returnfalse;}}returntrue;}boolvalidPalindrome(std::string s){int left =0;int right = s.length()-1;while(left < right){if(s[left]== s[right]){ left++; right--;}else{// 遇到不匹配，尝试删除左边字符 OR 删除右边字符returnisPalindrome(s, left +1, right)||isPalindrome(s, left, right -1);}}returntrue;}};

return 执行后会立即退出当前函数

3）验证回文串|||

🔗Lucy的空间骇客裂缝：

关键点拨

如果一个长度为 ( n ) 的字符串 ( s )，在删除了最多 ( k ) 个字符后能变成回文串，这意味着 ( s ) 中原本就存在一个长度至少为 ( n - k ) 的回文子序列

因此，解题步骤如下：

1. 计算字符串 ( s ) 的最长回文子序列 (LPS) 的长度
2. 判断 L P S ≥ n − k LPS \ge n - k LPS≥n−k 是否成立

我们可以使用动态规划来求 L P S ≥ n − k LPS \ge n - k LPS≥n−k。设 ( dp[i][j] ) 表示字符串从索引 ( i ) 到 ( j ) 范围内的最长回文子序列长度。

• 如果 ( s[i] == s[j] )，则 ( dp[i][j] = dp[i+1][j-1] + 2 )。
• 如果 ( s[i] \neq s[j] )，则 ( dp[i][j] = \max(dp[i+1][j], dp[i][j-1]) )。

完整代码

#include<iostream>#include<vector>#include<string>#include<algorithm>usingnamespace std;classSolution{public:boolisValidPalindrome(string s,int k){int n = s.length();// dp[i][j] 表示 s[i...j] 的最长回文子序列长度 vector<vector<int>>dp(n,vector<int>(n,0));// 每个单一字符都是长度为 1 的回文for(int i =0; i < n; i++){ dp[i][i]=1;}// 从下往上，从左往右计算for(int i = n -2; i >=0; i--){for(int j = i +1; j < n; j++){if(s[i]== s[j]){ dp[i][j]= dp[i +1][j -1]+2;}else{ dp[i][j]=max(dp[i +1][j], dp[i][j -1]);}}}// 只要 长度 - 最长回文子序列 <= k，即为 truereturn n - dp[0][n -1]<= k;}};// 测试代码intmain(){ Solution sol; cout << boolalpha;// 输出 true/false 而不是 1/0 cout << sol.isValidPalindrome("abcdeca",2)<< endl;// 输出: true cout << sol.isValidPalindrome("abbababa",1)<< endl;// 输出: truereturn0;}

4）验证回文串||||

🔗Lucy的空间骇客裂缝：Leetcode原题

关键点拨

我们用两个指针 i 和 j 分别指向字符串的头和尾。如果 s[i] != s[j]，就记为一个“不对称对”，数量记为 diff。

根据 diff 的数量，我们分情况讨论：

1. 如果 diff > 2：
   • 两步操作最多只能修补 2 个不对称对，所以无论如何也变不成回文。返回 false。
2. 如果 diff == 1 或 diff == 2：
   • 可以通过 1 次或 2 次修改对应的字符使其匹配。返回 true。
3. 如果 diff == 0（原串已经是回文）：
   • 重点来了！题目要求“恰好”执行一到两步。
   • 如果字符串长度 n 为奇数，我们可以修改最中间那个字符，它不影响回文性，这算 1 步；或者修改任意一对字符（2 步）。所以奇数长度一定可以。
   • 如果字符串长度 n 为偶数，我们可以通过 2 步操作（比如把 s[0] 和 s[n-1] 同时改成另一个字符 'z'）使其保持回文。所以偶数长度也可以。
   • 注意：除非题目要求操作后必须是“不同的回文串”，否则只要原串是回文且 n >= 1，通常都能满足 1-2 步的要求。

完整代码

#include<iostream>#include<string>usingnamespace std;classSolution{public:boolcanMakePalindrome(string s){int n = s.length();int diff =0;// 统计不对称的字符对数量for(int i =0; i < n /2;++i){if(s[i]!= s[n -1- i]){ diff++;}}// 情况 1: 需要修改的地方超过 2 处，两步救不回来if(diff >2)returnfalse;// 情况 2: 有 1 或 2 处不同，刚好对应 1 步或 2 步操作if(diff >0)returntrue;// 情况 3: diff == 0 (已经是回文)// 题目要求“恰好”一到两步。// 只要长度足够（比如 n >= 1），我们总能通过改中间位或改一对来消耗步数returntrue;}};

8）字符串相乘

🔗Lucy的空间骇客裂缝：Leetcode原题

关键点拨

如果我们有两个数字，长度分别为 ( M ) 和 ( N )，它们的乘积长度最多为 ( M + N )

1. 初始化数组：创建一个长度为 ( m + n ) 的数组 res 来存储每一位的计算结果。
2. 嵌套循环：从后往前遍历 num1 和 num2。
   • num1[i] 和 num2[j] 的乘积记为 mul。
   • 该乘积会影响到 res 中的两个位置：i + j 和 i + j + 1
3. 累加与进位：
   • mul 加上 res[i + j + 1] 原有的值。
   • 更新 res[i + j + 1] = mul % 10。
   • 将进位加到 res[i + j] += mul / 10。
4. 结果转换：跳过数组开头的 0，将剩余数字转回字符串。

完整代码

classSolution{public: string multiply(string num1, string num2){// 边界处理：任何数乘以 0 结果都是 0if(num1 =="0"|| num2 =="0")return"0";int m = num1.size();int n = num2.size();// 结果的最大长度为 m + n// 初始化为一个全为 '0' 的字符串作为“画布” string res(m + n,'0');// 从后往前遍历 num1 和 num2for(int i = m -1; i >=0; i--){for(int j = n -1; j >=0; j--){// 计算当前位的乘积int mul =(num1[i]-'0')*(num2[j]-'0');// 找到对应的结果位置（低位在 i + j + 1）int p2 = i + j +1;// 将乘积累加到当前位（注意要减去字符 '0' 得到数值）int sum = mul +(res[p2]-'0');// 更新当前位数值 res[p2]=(sum %10)+'0';// 处理进位：直接加到前一位 (p1 = i + j)// 这里的进位可能会产生连环进位，但在嵌套循环中下一次会处理到它 res[i + j]+=(sum /10);}}// 移除前导零 size_t startpos = res.find_first_not_of('0');if(string::npos != startpos){return res.substr(startpos);}return"0";}};

🔗Lucy的空间骇客裂缝：string类的常用构造

9）找出第N个二进制字符串中的第K位

🔗Lucy的空间骇客裂缝：

关键点拨

• using namespace std; 的作用：它让你不再需要写 std::string、std::reverse 或 std::cout，使代码在视觉上更“清爽”，非常符合你在 ZEEKLOG 上分享代码的简洁风格。
• 字符串操作：代码中直接利用了 string 的 + 运算符进行拼接。由于你对 C 语言内存管理有深入理解，你会发现 C++ 的这种写法虽然方便，但底层涉及多次内存重分配。
• 复杂度分析：
  • 时间复杂度：( O(2^n) )，因为字符串长度随 ( n ) 指数增长。
  • 空间复杂度：( O(2^n) )，用于存储生成的字符串。

完整代码

#include<iostream>#include<string>#include<algorithm>usingnamespace std;// 使用标准命名空间classSolution{public:charfindKthBit(int n,int k){ string s ="0";// 对应 S1for(int i =2; i <= n;++i){ string temp = s;// 1. 执行 invert (取反)for(char&c : temp){ c =(c =='0'?'1':'0');}// 2. 执行 reverse (反转)reverse(temp.begin(), temp.end());// 3. 构造 Si = Si-1 + "1" + reverse(invert(Si-1)) s = s +"1"+ temp;// 如果字符串长度已经覆盖了 k，可以考虑提前停止以节省内存if(s.length()>= k && i < n){// 性能优化点：在处理 n 较大的情况时，可以截断不需要的部分}}// k 从 1 开始计数，索引需要 -1return s[k -1];}};// 简单的测试入口intmain(){ Solution sol; cout <<"n=3, k=1 Result: "<< sol.findKthBit(3,1)<< endl;// 输出 '0' cout <<"n=4, k=11 Result: "<< sol.findKthBit(4,11)<< endl;// 输出 '1'return0;}

10）无重复字符的排列组合

🔗Lucy的空间骇客裂缝：Leetcode原题

关键点拨

最直观的方法是使用“交换”策略：

1. 固定位：从字符串的第 0 位开始，尝试将它与后面（包括自己）的每一位进行交换。
2. 递归：固定好当前位置后，对剩余的子字符串进行递归排列。
3. 回溯：递归返回后，将字符交换回来，以保证不影响下一次同层级的尝试。

完整代码

classSolution{public:/** * 计算无重复字符串的所有排列组合 * 核心逻辑：通过交换字符原地生成排列，不依赖额外容器 */voidpermutation(string s){if(s.empty())return;backtrack(s,0);}private:// start 表示当前需要确定的字符位置voidbacktrack(string& s,int start){// 递归终止条件：已经确定到了字符串末尾if(start == s.length()){ cout << s << endl;// 直接输出当前排列return;}for(int i = start; i < s.length(); i++){// 1. 做选择：把后面的字符换到当前位置swap(s[start], s[i]);// 2. 递归：去确定下一个位置 (start + 1)backtrack(s, start +1);// 3. 撤销选择（回溯）：换回来，恢复原始状态// 这一步至关重要，保证了后续循环能从正确的初始状态开始swap(s[start], s[i]);}}};

11）回文子串

🔗Lucy的空间骇客裂缝：

关键点拨

回文串的特点是对称的。我们可以遍历字符串的每一个位置，把它当作“中心”，然后向两边扩展，只要两边的字符相等，就说明找到了一个回文子串。

注意：中心点有两种情况：

1. 奇数长度：中心是一个字符（如 "aba" 的中心是 'b'）。
2. 偶数长度：中心是两个字符之间的间隙（如 "abba" 的中心是两个 'b' 之间）。

完整代码

classSolution{public:/** * 计算字符串中回文子串的总数 * 时间复杂度: O(n^2) * 空间复杂度: O(1) */intcountSubstrings(string s){int n = s.length();int totalCount =0;for(int i =0; i < n; i++){// 情况 1: 奇数长度回文，以 s[i] 为中心向两边扩展 totalCount +=expandFromCenter(s, i, i);// 情况 2: 偶数长度回文，以 s[i] 和 s[i+1] 为中心向两边扩展 totalCount +=expandFromCenter(s, i, i +1);}return totalCount;}private:/** * 从指定的中心向外扩展，并返回找到的回文串数量 */intexpandFromCenter(const string& s,int left,int right){int count =0;int n = s.length();// 只要不越界且左右字符相等，就是回文while(left >=0&& right < n && s[left]== s[right]){ count++; left--;// 向左扩展 right++;// 向右扩展}return count;}};

12）最长回文子串

🔗Lucy的空间骇客裂缝：

关键点拨

中心扩展法

完整代码

// 针对最长回文子串 string longestPalindrome(string s){if(s.length()<2)return s;int start =0, maxLen =0;for(int i =0; i < s.length(); i++){// 奇数长度中心 (i) 和 偶数长度中心 (i, i+1)expand(s, i, i, start, maxLen);expand(s, i, i +1, start, maxLen);}return s.substr(start, maxLen);}voidexpand(const string& s,int l,int r,int& start,int& maxLen){while(l >=0&& r < s.length()&& s[l]== s[r]){if(r - l +1> maxLen){ start = l; maxLen = r - l +1;} l--; r++;}}

13）最长回文子序列

🔗Lucy的空间骇客裂缝：

关键点拨

动态规划 (DP)

我们可以使用一个二维数组 dp[i][j] 来表示字符串从索引 i 到 j 之间的最长回文子序列的长度。

状态转移方程

• 基本情况：当 i == j 时，单个字符本身就是一个回文，所以 dp[i][i] = 1。
• 当 s[i] == s[j] 时：这两个字符可以分别作为回文序列的首尾，因此长度在中间部分的基础上加 2。dp[i][j] = dp[i+1][j-1] + 2
• 当 s[i] != s[j] 时：说明 s[i] 和 s[j] 不能同时出现在最长回文序列中，我们需要在“忽略 s[i]”和“忽略 s[j]”两种情况下取最大值。dp[i][j] = max(dp[i+1][j], dp[i][j-1])

完整代码

#include<iostream>#include<vector>#include<string>#include<algorithm>usingnamespace std;intlongestPalindromeSubseq(string s){int n = s.length();// dp[i][j] 表示 s[i...j] 的最长回文子序列长度 vector<vector<int>>dp(n,vector<int>(n,0));// 从后往前遍历，保证计算 dp[i][j] 时，dp[i+1][j-1] 等子问题已解决for(int i = n -1; i >=0; i--){ dp[i][i]=1;// 单个字符for(int j = i +1; j < n; j++){if(s[i]== s[j]){ dp[i][j]= dp[i +1][j -1]+2;}else{ dp[i][j]=max(dp[i +1][j], dp[i][j -1]);}}}return dp[0][n -1];}intmain(){ string s1 ="bbbab"; cout <<"Example 1: "<<longestPalindromeSubseq(s1)<< endl;// 输出 4 string s2 ="cbbd"; cout <<"Example 2: "<<longestPalindromeSubseq(s2)<< endl;// 输出 2return0;}

暂时就这么多题 后续还会继续添加在这篇文章上面哦

💻结尾— 核心连接协议

警告：🌠🌠正在接入底层技术矩阵。如果你已成功破解学习中的逻辑断层，请执行以下指令序列以同步数据：🌠🌠

【📡】 建立深度链接：关注本终端。在赛博丛林中深耕底层架构，从原始代码到进阶协议，同步见证每一次系统升级。

【⚡】 能量过载分发：执行点赞操作。通过高带宽分发，让优质模组在信息流中高亮显示，赋予知识跨维度的传播力。

【💾】 离线缓存核心：将本页加入收藏。把这些高频实战逻辑存入你的离线存储器，在遭遇系统崩溃或需要离线检索时，实现瞬时读取。

【💬】 协议加密解密：在评论区留下你的散列码。分享你曾遭遇的代码冲突或系统漏洞（那些年踩过的坑），通过交互式编译共同绕过技术陷阱。

【🛰️】 信号频率投票：通过投票发射你的选择。你的每一次点击都在重新定义矩阵的进化方向，决定下一个被全量拆解的技术节点。