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

Ne0inhk

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



⚡ CYBER_PROFILE ⚡
/// SYSTEM READY ///

[WARNING]: DETECTING HIGH ENERGY

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

分隔符
>>> ACCESS TERMINAL <<<
[ 🦾 作者主页 ][ 🔥 C语言核心 ]
[ 💾 编程百度 ][ 📡 代码仓库 ]

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

索引与导读

一、字符串转换

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
  1. 反转结果： 因为我们是从个位开始计算并依次添加的，最后得到的字符串需要反转过来。

完整代码

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;}

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

💻结尾— 核心连接协议

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

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

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

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

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

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

在这里插入图片描述

Read more

实战篇：Python开发monogod数据库mcp server看完你就会了

实战篇：Python开发monogod数据库mcp server看完你就会了

原创不易,请关注公众号：【爬虫与大模型开发】,大模型的应用开发之路，整理了大模型在现在的企业级应用的实操及大家需要注意的一些AI开发的知识点！持续输出爬虫与大模型的相关文章。 前言 目前mcp协议是给deepseek大模型插上工具链的翅膀，让大模型不仅拥有超高的推理和文本生成能力，还能具备执行大脑意识的工具能力！ 如何开发一个mcp? mcp是一种协议，指的是模型上下文协议 (Model Context Protocol)。 官方结成的mcp https://github.com/modelcontextprotocol/python-sdk mcp库 pip install mcp from mcp.server.fastmcp import FastMCP 我们先来做一个简单的案例 from mcp.server.fastmcp import FastMCP import requests mcp = FastMCP("spider") @mcp.tool() def crawl(

By Ne0inhk
【大模型实战篇】基于Claude MCP协议的智能体落地示例

【大模型实战篇】基于Claude MCP协议的智能体落地示例

1. 背景         之前我们在《MCP(Model Context Protocol) 大模型智能体第一个开源标准协议》一文中，介绍了MCP的概念，虽然了解了其概念、架构、解决的问题，但还缺少具体的示例，来帮助进一步理解整套MCP框架如何落地。         今天我们基于claude的官方例子--获取天气预报【1】，来理解MCP落地的整条链路。 2. MCP示例         该案例是构建一个简单的MCP天气预报服务器，并将其连接到主机，即Claude for Desktop。从基本设置开始，然后逐步发展到更复杂的使用场景。         大模型虽然能力非常强，但其弊端就是内容是过时的，这里的过时不是说内容很旧，只是表达内容具有非实时性。比如没有获取天气预报和严重天气警报的能力。因此我们将使用MCP来解决这一问题。         构建一个服务器，该服务器提供两个工具：获取警报（get-alerts）和获取预报（get-forecast）。然后，将该服务器连接到MCP主机（在本例中为Claude for Desktop）。         首先我们配置下环

By Ne0inhk
AI Agent新范式：FastGPT+MCP协议实现工具增强型智能体构建

AI Agent新范式：FastGPT+MCP协议实现工具增强型智能体构建

AI Agent新范式：FastGPT+MCP协议实现工具增强型智能体构建 作者：高瑞冬 本文目录 * AI Agent新范式：FastGPT+MCP协议实现工具增强型智能体构建 * 一、MCP协议简介 * 二、创建MCP工具集 * 1. 获取MCP服务地址 * 2. 在FastGPT中创建MCP工具集 * 三、测试MCP工具 * 四、AI模型调用MCP工具 * 1. 调用单个工具 * 2. 调用整个工具集 * 五、私有化部署支持 * 1. 环境准备 * 2. 修改docker-compose.yml文件 * 3. 修改FastGPT配置 * 4. 重启服务 * 六、使用MCP-Proxy集成多个MCP服务 * 1. MCP-Proxy简介 * 2. 安装MCP-Proxy * 3. 配置MCP-Proxy * 4. 将MCP-Proxy与FastGPT集成 * 5. 高级配置

By Ne0inhk
AI革命先锋：DeepSeek与蓝耘通义万相2.1的无缝融合引领行业智能化变革

AI革命先锋：DeepSeek与蓝耘通义万相2.1的无缝融合引领行业智能化变革

云边有个稻草人-ZEEKLOG博客 目录 引言 一、什么是DeepSeek？ 1.1 DeepSeek平台概述 1.2 DeepSeek的核心功能与技术 二、蓝耘通义万相2.1概述 2.1 蓝耘科技简介 2.2 蓝耘通义万相2.1的功能与优势 1. 全链条智能化解决方案 2. 强大的数据处理能力 3. 高效的模型训练与优化 4. 自动化推理与部署 5. 行业专用解决方案 三、蓝耘通义万相2.1与DeepSeek的对比分析 3.1 核心区别 3.2 结合使用的优势 四、蓝耘注册流程 五、DeepSeek与蓝耘通义万相2.1的集成应用 5.1 集成应用场景 1. 智能医疗诊断

By Ne0inhk