leetcode算法之字符串

1.最长公共前缀

最长公共前缀

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) {//法二：统一比较int n = strs[0].size();for(int i=0;i<n;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];}
};

2.最长回文子串

最长回文子串

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

3.二进制求和

二进制求和

class Solution {
public:string addBinary(string a, string b) {//模仿列竖式相加int t = 0;//表示进位int cur1 = a.size()-1;int cur2 = b.size()-1;string ret;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;}
};

4.字符串相乘

字符串相乘

class Solution {
public:string multiply(string num1, string num2) {//高精度乘法//使用无进位相乘再相加，最后再处理进位//1.准备工作int m = num1.size(),n = num2.size();reverse(num1.begin(),num1.end());reverse(num2.begin(),num2.end());vector<int> tmp(m+n-1);//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;string ret;while(cur<m+n-1 || t!=0){if(cur<m+n-1) t+=tmp[cur++];ret += t%10+'0';t /= 10;}//4.处理前导零while(ret.size()>1 && ret.back() == '0') ret.pop_back();//5.注意输出结果顺序reverse(ret.begin(),ret.end());return ret;}
};