万网网站流量,wordpress重复评论,制作相册影集软件,企业信息管理系统登录本篇博客记录了关于字符串相关的几道题目#xff0c;包括最长公共前缀、最长回文子串、二进制求和、字符串相乘。 //解法1
class Solution {
public:string longestCommonPrefix(vectorstring strs) {string ret strs[0];for(int i 1 ; i strs.size() ; i… 本篇博客记录了关于字符串相关的几道题目包括最长公共前缀、最长回文子串、二进制求和、字符串相乘。 //解法1
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;}string FindCommon(const string s1, const string s2){int i 0;while(i min(s1.size(),s2.size()) s1[i] s2[i]) i;return s1.substr(0, i);}
};
//解法2
class Solution {
public:string longestCommonPrefix(vectorstring 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() || strs[j][i] ! tmp) return strs[0].substr(0,i);}}return strs[0];}
};题目分析本道题有两种思路 第一种方法是两个进行查找最长公共子串最后返回这两个字符串的公共子串再把这个公共子串和下一个字符串进行查找返回这两个字符串的公共子串依次查找下去。 第二种方法是同时比较所有子串先比较第一个字符串的第一个字母和剩下字符串的第一个字母然后再比较第一个字符串的剩下字符串的第二个字母依次类推。 class Solution {
public:string longestPalindrome(string s) {int begin 0, len 0;int 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);}
}; 题目分析这道题是要找回文子串而回文子串是对称的我们可以利用这样的特性来结题。把这个字符串的每个字母依次作为中心点i如果回文子串是奇数个那么先让right和left都指向i判断s[left]和s[right]是否相等如果相等那么让left--right如果回文子串是偶数个让left指向iright指向i1或者让left指向i-1right指向i判断s[left]和s[right]是否相等如果相等那么让left--right。 class Solution {
public:string addBinary(string a, string b) {string ret; int cur1 a.size() - 1, cur2 b.size() - 1;int tmp 0;while(cur1 0 || cur2 0 || tmp){if(cur1 0) tmp a[cur1--] - 0;if(cur2 0) tmp b[cur2--] - 0;ret tmp%2 0;tmp / 2;}reverse(ret.begin(), ret.end());return ret;}
}; 题目分析这道题就是模拟相加过程把两个字符串的最低位加到tmp变量上然后%2得到最后结果的倒数第一位然后tmp/2是进位然后再去把倒数第二位都加到tmp再%2最后结果的倒数第二位然后tmp/2是进位依次这样下去。 class Solution {
public:string multiply(string num1, string num2) {//1.处理为0的情况if(num1 0 || num2 0) return 0;string ret;int m num1.size();int n num2.size();vectorint tmp(m n - 1, 0);reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());//2.先无进位相乘后相加for(int i 0; i n ; i){for(int j 0 ; j m ; j){tmp[i j] (num2[i] - 0)*(num1[j] - 0);}}//3.处理进位int cur 0 , t 0;while(cur m n -1 || t){if(cur m n -1) t tmp[cur];ret t % 10 0;t / 10;}reverse(ret.begin(), ret.end());return ret;}
}; 题目分析有两种思路无论哪种思路都要将两个字符串先逆序这样下标0、1、2代表的是真实列竖式运算从低位到高位的顺序1模拟列竖式计算string ret 0string tmptmp存的是每次相乘后的结果然后把tmp累加到ret上再计算下一位相乘的结果再累加到ret上。要注意几个细节高位相乘的时候要补上0处理为0的情况。 2无进位相乘然后相加最后处理进位。创建一个大小为mn-1的数组tmptmp存放无进位累加的结果然后处理tmp的进位问题。
