【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
关键点拨
- 从后往前遍历： 使用两个指针分别指向
num1和num2的末尾。 - 逐位相加： 将对应位置的数字相加，同时加上来自低位的进位（
carry）。 - 处理进位：
- 当前位的数值 =
(n1 + n2 + carry) % 10 - 新的进位 =
(n1 + n2 + carry) / 10
- 反转结果： 因为我们是从个位开始计算并依次添加的，最后得到的字符串需要反转过来。
完整代码
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原题
关键点拨
- 初始化双指针： 设置一个左指针
left指向字符串的起始位置（索引0），设置一个右指针right指向字符串的末尾位置（索引s.length() - 1）。 - 向中间遍历： 当
left < right时，执行以下循环：- 如果
left指向的字符不是英文字母，则left向右移动一步（left++）。 - 如果
right指向的字符不是英文字母，则right向左移动一步（right--）。 - 如果
left和right指向的都是英文字母，则交换这两个字符的位置。交换完成后，left右移，right左移，继续下一轮比较。
- 如果
- 返回结果： 当指针相遇或交错时，遍历结束，返回修改后的字符串
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原题
关键点拨
- 设置两个指针：
left指向数组起始位置，right指向数组末尾。 - 当
left < right时，交换两个指针所指向的字符。 - 交换后，将
left向右移动一位，right向左移动一位。 - 重复上述过程，直到两个指针相遇，反转完成
完整代码
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原题
关键点拨
- 步进：每次移动 (2k) 个单位。
- 反转范围：在每一个 (2k) 的区间内，反转 前 (k) 个 字符。
- 边界处理：
- 如果剩余字符 不足 (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原题
关键点拨
std::reverse的妙用
C++ 标准库<algorithm>提供的reverse(first, last)是反转容器元素的利器。它直接修改原容器，底层实现通常也是双指针交换。- 边界控制
在处理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原题
关键点拨
- 选择合适的数据结构（计数器）
题目给出了一个关键提示：“只包含小写字母”。- 小写字母只有
26个（'a'到'z'）。 - 我们可以直接使用一个长度为
26的整型数组count[26]来记录每个字母出现的次数，而不是使用复杂的哈希表。 - 映射逻辑：字符
'a'对应索引0，'b'对应1……以此类推。计算公式为：
[ \text{index} = s[i] - ‘a’ ]
- 小写字母只有
- 第一次遍历：统计频率
- 从头到尾扫描一遍字符串
s。 - 每遇到一个字符，就在计数器数组对应的位置上加
1。 - 目的：这一步完成后，我们就知道了字符串中每个字母总共出现了多少次。
- 从头到尾扫描一遍字符串
- 第二次遍历：寻找目标
- 再次从头到尾扫描字符串
s（注意：必须按字符串的原有顺序遍历）。 - 检查当前字符在计数器数组中的数值。
- 判定条件：如果某个字符的计数等于
1，说明它是第一个在整个字符串中只出现一次的字符。 - 动作：直接返回当前的索引
i。
- 再次从头到尾扫描字符串
- 边界处理
- 如果第二次遍历结束了，依然没有找到计数为
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原题
关键点拨
- 从后往前找：最快的方法是从字符串末尾开始向前遍历，跳过末尾可能存在的空格（虽然题目说单词间单个空格，但防御性编程总没错），遇到第一个非空格字符开始计数，直到遇到下一个空格或到达字符串开头。
- 内置拆分：利用语言自带的
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原题
关键点拨
- 设置两个指针：
left指向字符串开头，right指向字符串末尾。 - 跳过非法字符： 如果指针指向的不是字母或数字，就继续移动（
left++或right--）。 - 比较字符： 将两端的字符都转为小写后进行比较。如果不相等，直接返回
false。 - 循环结束： 如果
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) )）。最有效的做法是使用双指针法：
- 首尾推进：设定两个指针
left和right，分别指向字符串的头和尾。 - 逐一比对：
- 如果
s[left] == s[right]，则两个指针同时向中间移动。 - 如果
s[left] != s[right]，说明遇到了阻碍。此时我们有一次机会尝试删除一个字符：- 方案 A：忽略左侧字符，检查剩下的中间部分
[left + 1, right]是否是回文。 - 方案 B：忽略右侧字符，检查剩下的中间部分
[left, right - 1]是否是回文。
- 方案 A：忽略左侧字符，检查剩下的中间部分
- 如果
- 结论：如果方案 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 ) 的回文子序列
因此，解题步骤如下：
- 计算字符串 ( s ) 的最长回文子序列 (LPS) 的长度
- 判断 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 的数量，我们分情况讨论：
- 如果
diff > 2：- 两步操作最多只能修补
2个不对称对，所以无论如何也变不成回文。返回false。
- 两步操作最多只能修补
- 如果
diff == 1或diff == 2：- 可以通过
1次或2次修改对应的字符使其匹配。返回true。
- 可以通过
- 如果
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 )
- 初始化数组：创建一个长度为 ( m + n ) 的数组
res来存储每一位的计算结果。 - 嵌套循环：从后往前遍历
num1和num2。num1[i]和num2[j]的乘积记为mul。- 该乘积会影响到
res中的两个位置：i + j和i + j + 1
- 累加与进位：
mul加上res[i + j + 1]原有的值。- 更新
res[i + j + 1] = mul % 10。 - 将进位加到
res[i + j] += mul / 10。
- 结果转换：跳过数组开头的
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原题
关键点拨
最直观的方法是使用“交换”策略：
- 固定位：从字符串的第
0位开始，尝试将它与后面（包括自己）的每一位进行交换。 - 递归：固定好当前位置后，对剩余的子字符串进行递归排列。
- 回溯：递归返回后，将字符交换回来，以保证不影响下一次同层级的尝试。
完整代码
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的空间骇客裂缝：
关键点拨
回文串的特点是对称的。我们可以遍历字符串的每一个位置，把它当作“中心”，然后向两边扩展，只要两边的字符相等，就说明找到了一个回文子串。
注意：中心点有两种情况：
- 奇数长度：中心是一个字符（如
"aba"的中心是'b'）。 - 偶数长度：中心是两个字符之间的间隙（如
"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;}暂时就这么多题 后续还会继续添加在这篇文章上面哦
💻结尾— 核心连接协议
警告：🌠🌠正在接入底层技术矩阵。如果你已成功破解学习中的逻辑断层，请执行以下指令序列以同步数据：🌠🌠
【📡】 建立深度链接：关注本终端。在赛博丛林中深耕底层架构，从原始代码到进阶协议，同步见证每一次系统升级。
【⚡】 能量过载分发：执行点赞操作。通过高带宽分发，让优质模组在信息流中高亮显示，赋予知识跨维度的传播力。
【💾】 离线缓存核心：将本页加入收藏。把这些高频实战逻辑存入你的离线存储器，在遭遇系统崩溃或需要离线检索时，实现瞬时读取。
【💬】 协议加密解密：在评论区留下你的散列码。分享你曾遭遇的代码冲突或系统漏洞（那些年踩过的坑），通过交互式编译共同绕过技术陷阱。
【🛰️】 信号频率投票：通过投票发射你的选择。你的每一次点击都在重新定义矩阵的进化方向，决定下一个被全量拆解的技术节点。
