公司网站建设外包流程图,google官网浏览器,建设部网站上怎样查询企业业绩,京东可以做特效的网站文章目录 前言最长公共前缀题目要求题目解析代码如下 最长回文子串题目要求题目解析代码如下 二进制求和题目要求题目解析 字符串相乘题目要求题目解析代码如下 前言
本文将会向你介绍有关字符串的相关题目#xff1a;最长公共前缀、最长回文子串、二进制求和、字符串相乘。本… 文章目录 前言最长公共前缀题目要求题目解析代码如下 最长回文子串题目要求题目解析代码如下 二进制求和题目要求题目解析 字符串相乘题目要求题目解析代码如下 前言
本文将会向你介绍有关字符串的相关题目最长公共前缀、最长回文子串、二进制求和、字符串相乘。本篇并不是介绍字符串相关的算法只是将题目要求为字符串类型的归类
最长公共前缀
https://leetcode.cn/problems/longest-common-prefix/description/
题目要求 题目解析 题目要求找到最长公共前缀我们很简单地就能想到将字符串中的字符一一比较返回最长公共前缀这里采用的是字符串两两比较先拿第一个字符串与第二个字符串比较再拿它们的最长公共前缀与第三个字符串比较最后就能得到最长公共前缀
代码如下
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(vectorstring strs){string ret strs[0];for(int i 1; i strs.size(); i){ret findCommon(ret, strs[i]);}return ret;}
};
最长回文子串
https://leetcode.cn/problems/longest-palindromic-substring/
题目要求 题目解析 给一个字符串要求出字符串中最长的回文子串即需要在一个字符串中找到中间对称的子串ababab都是关于中间对称那么我们可以对所有的可能为中点的点遍历一遍这样才能找出最长的这里采用中心扩展算法即遍历每个点每次把该点当作中点从该点开始向左向右进行移动如果left[i] right[i]则继续向左向右移动直到不相同位置那么就可以找到以某个点为中心对称的字符串 注意点分奇偶 当出现类似回文子串b a b这种格式是需要将left right ii遍历的每个点即子串字符数为奇数情况 当出现类似回文串b b这种格式是需要将left iright i 1 即子串字符数为偶数情况 代码如下
class Solution {
public:string longestPalindrome(string s) {int n s.size();int len 0; //最长回文串长度int begin 0; //回文串的起始位置//遍历所有可能为中点的点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){len right - left - 1;begin left 1;}//字符串为偶数个字符left i, right i 1;while(left 0 right n s[left] s[right]){left--;right;}if(right - left - 1 len){len right - left - 1;begin left 1;}}return s.substr(begin, len);}
};二进制求和
https://leetcode.cn/problems/add-binary/
题目要求 题目解析
给两个字符串按照二进制加法相加我们很自然地能想到遍历每个字符然后按照二进制相加模拟加法过程即可 注意点一字符串模拟加法 在正常加法中我们都是从低位即图中下标为3的位置相加直到加到高位其中还包含低位向高位的进位因此模拟过程中也需要把进位给模拟出来因此我们必须也要从下标为3的位置字符开始相加 也可以看看另一道类似解法的题
两数相加这在篇文章链表专题中也提到过 注意点二结束条件 当其中一个字符串结束都不能作为结束条件而且当两个字符串都遍历完了可能进位不为0也不能结束 ## 代码如下
class Solution {
public:string addBinary(string a, string b) {int t 0; //进位string ret;int cur1 a.size() - 1;int cur2 b.size() - 1;while(cur1 0 || cur2 0 || t 0){if(cur1 0){t a[cur1] - 0;cur1--;}if(cur2 0){t b[cur2] - 0;cur2--;}ret t % 2 0;t/2;}reverse(ret.begin(), ret.end());return ret;}
};字符串相乘
https://leetcode.cn/problems/multiply-strings/
题目要求 题目解析
这道题容易想到的解法就是以其中一个字符串每一位去乘以另一个字符串然后将每次相乘的结果再相加如下图所示 但这种解法并不好写因此将会介绍另一种不好想到但是好写的解法 解法二 无进位相乘再相加再处理进位
由于给定字符串下标的顺序与我们实际乘法进位的顺序相反所以我们先将给定字符串逆序一下注意以后碰到带有进位类似的题目最好也是先逆序一下 一、模拟乘法相加 直接将两个字符串中的字符 - 0相乘再相加即可注意符号 for (int i 0; i sz1; i){for (int j 0; j sz2; j){tmp[i j] ((num1[i] - 0) * (num2[j] - 0));}}二、模拟进位操作 先用t保存相乘再相加的结果将个位上的数留下十位上的数进位 //进位操作string ret;int t 0, cur 0; //进位while(cur sz1 sz2 - 1 || t ! 0){if(cur sz1 sz2 - 1) t tmp[cur];ret t % 10 0;t / 10;}三、去掉前导0 如果123 乘 0 按照我们以上的模拟乘法将会得出000因此需要把前两个0给去掉 while(ret.size() 1 ret.back() 0) ret.pop_back();注意当进位不为0的时候也不能结束循环因为可能存在两个字符串最后一位为3 7进位为 1 最后逆序保存结果的字符串即可
代码如下
class Solution {
public:string multiply(string num1, string num2){reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());int sz1 num1.size();int sz2 num2.size();vectorint tmp(sz1 sz2 - 1); //无进位相乘再相加后的数组for (int i 0; i sz1; i){for (int j 0; j sz2; j){tmp[i j] ((num1[i] - 0) * (num2[j] - 0));}}//进位操作string ret;int t 0, cur 0; //进位while(cur sz1 sz2 - 1 || t ! 0){if(cur sz1 sz2 - 1) t tmp[cur];ret t % 10 0;t / 10;}//去掉前导零while(ret.size() 1 ret.back() 0) ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};
