刷题训练之字符串

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：熟练掌握字符串算法。

> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。

> 专栏选自：刷题训练营

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

🌟前言分析

最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推，求职就业一站解决_牛客网

⭐知识讲解

基本思想：

一般都是定义指针来遍历字符串
利用容器
采用模拟

🌙topic-->1

题目链接：1. 最长公共前缀 - 力扣（LeetCode）

题目分析：

编写一个函数来查找字符串数组中的最长公共前缀。

算法原理：

解法一：两个比较

图解：

解法二：统一比较

图解：

代码演示：

// 方法一：
class Solution 
{
public:string longestCommonPrefix(vector<string>& strs) {// 两两比较string ret = strs[0];//返回值// 循环for(int i = 1; i < strs.size(); i++)ret = findCommon(ret,strs[i]);return ret; // 返回}string findCommon(string& s1, string& s2){int i = 0;while(i < min(s1.size(), s2.size()) && s1[i] == s2[i])i++;return s1.substr(0,i);// 切割}
};// 方法二：
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {// 方法二：统一比较for(int i = 0; i < strs[0].size(); i++) // 字符串一起比较{char tmp = strs[0][i];for(int j = 1; j < strs.size(); j++) // 再比较两个字符串{if(i == strs[j].size() || tmp != strs[j][i])return strs[0].substr(0,i);}}return strs[0];}
};

🌙topic-->2

题目链接：2. - 力扣（LeetCode）

题目分析：

给你一个字符串 s，找到 s 中最长的回文子串（如果字符串向前和向后读都相同）

算法原理：

解法：中心扩展算法

图解：

代码演示：

class Solution {
public:string longestPalindrome(string s) {// 中⼼扩展算法int begin = 0, len = 0, n = s.size();for (int i = 0; i < n; i++) // 依次枚举所有的中点{// 先做⼀次奇数⻓度的扩展int left = i, right = i;while (left >= 0 && right < n && s[left] == s[right]) {left--;right++;}if (right - left - 1 > len) {begin = left + 1;len = right - left - 1;}// 偶数⻓度的扩展left = i, right = i + 1;while (left >= 0 && right < n && s[left] == s[right]) {left--;right++;}if (right - left - 1 > len) {begin = left + 1;len = right - left - 1;}}return s.substr(begin, len);}
};

🌙topic-->3

题目链接：3. - 力扣（LeetCode）

题目分析：

给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

算法原理：

解法：两个比较

图解：

代码演示：

class Solution {
public:string addBinary(string a, string b) {string ret;int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;while (cur1 >= 0 || cur2 >= 0 || t) {if (cur1 >= 0)t += a[cur1--] - '0';if (cur2 >= 0)t += b[cur2--] - '0';ret += t % 2 + '0';t /= 2;}reverse(ret.begin(), ret.end());return ret;}
};

🌙topic-->4

题目链接：4. - 力扣（LeetCode）

题目分析：

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

算法原理：

解法：两个比较

图解：

代码演示：

class Solution {
public:string multiply(string n1, string n2) {// 解法：⽆进位相乘后相加，然后处理进位int m = n1.size(), n = n2.size();reverse(n1.begin(), n1.end());reverse(n2.begin(), n2.end());vector<int> tmp(m + n - 1);// 1. ⽆进位相乘后相加for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)tmp[i + j] += (n1[i] - '0') * (n2[j] - '0');// 2. 处理进位int cur = 0, t = 0;string ret;while (cur < m + n - 1 || t) {if (cur < m + n - 1)t += tmp[cur++];ret += t % 10 + '0';t /= 10;}// 3. 处理前导零while (ret.size() > 1 && ret.back() == '0')ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};