一、相关编程题

1.1 最长公共前缀

题目链接

14. 最长公共前缀 - 力扣（LeetCode）

题目描述

算法原理

编写代码

// 解法一：两两比较
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {int k = strs[0].size(); //表示最长公共前缀的结束位置for(int i = 0; i < strs.size()-1; ++i){for(int j = 0; j < k; ++j){if(j==min(strs[i].size(), strs[i+1].size()) || strs[i][j] != strs[i+1][j]){k = j;break;}}}return string(strs[0], 0, k);}
};// 解法二：统一比较
class Solution {
public:string longestCommonPrefix(vector<string>& strs) {int k = 0;while(k < strs[0].size()){char ch = strs[0][k];for(int i = 1; i < strs.size(); ++i){if(k==strs[i].size() || strs[i][k]!=ch)return string(strs[0], 0, k);}   ++k;}return strs[0];}
};

---

1.2 最长回文子串

题目链接

5. 最长回文子串 - 力扣（LeetCode）

题目描述

算法原理

编写代码

//中心扩展算法
class Solution {
public:string longestPalindrome(string s) {int maxlen = 0, maxi = 0, n = s.size();for(int i = 0; i < n; ++i) //依次枚举所有的中点{//奇数长度的扩展int j = i, k = i;for(; j>=0 && k<n; --j, ++k)if(s[j] != s[k]) break;if(maxlen < k-j-1){maxlen = k-j-1;maxi = j+1;}//偶数长度的扩展j = i; k = i+1;for(; j>=0 && k<n; --j, ++k)if(s[j] != s[k]) break;if(maxlen < k-j-1){maxlen = k-j-1;maxi = j+1;}}return s.substr(maxi, maxlen);}
};

---

1.3 二进制求和

题目链接

67. 二进制求和 - 力扣（LeetCode）

题目描述

算法原理

• 应该从低位到高位进行加法运算，将每一位的加法结果%2(进制数)就是这一位的结果，/2就是这一位的进位。
• 要保证将两个运算量的每一位都遍历相加，并不再有进位，此时结束循环。
• 要将最终的计算结果逆序才能得到正确的答案。

编写代码

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

---

1.4 字符串相乘

题目链接

43. 字符串相乘 - 力扣（LeetCode）

题目描述

算法原理

编写代码

//解法一：模拟
class Solution {
public:string multiply(string num1, string num2) {//为了从低位到高位相乘，先将两字符串逆序reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());string tmp, ret; //tmp存储每位相乘的结果，ret是最终结果//用num1的每一位与num2相乘，再将tmp结果相加到retfor(int i = 0; i < num1.size(); ++i) {tmp.clear();for(int k = 0; k < i; ++k) tmp+='0'; //高位相乘补'0'int mul = 0; //保存每位相乘的结果及进位for(int j = 0; j < num2.size(); ++j){mul += (num1[i]-'0')*(num2[j]-'0');tmp+=mul%10+'0';mul/=10;}while(mul>0){tmp+=mul%10+'0';mul/=10;}ret = StrSum(ret, tmp); }//处理前导'0'int i = ret.size()-1;while(i>0) //注意个位的'0'保留{if(ret[i] != '0') break;else --i;}ret.resize(i+1);//将结果翻转reverse(ret.begin(), ret.end());return ret;}//两逆序字符串相加，返回的结果也是逆序的（从低位到高位）string StrSum(const string& str1,const string& str2){int i = 0, j = 0, t = 0;string ret;while(i<str1.size() || j<str2.size() || t>0){if(i<str1.size()) t+=str1[i++]-'0';if(j<str2.size()) t+=str2[j++]-'0';ret += t%10+'0';t/=10;}return ret;}
};//解法二：无进位相乘再相加，最后处理进位
class Solution {
public:string multiply(string num1, string num2) {//为了从低位到高位相乘，先将两字符串逆序reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());//无进位相乘然后相加int m = num1.size(), n = num2.size();vector<int> tmp(m+n-1, 0);for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){tmp[i+j] += (num1[i]-'0')*(num2[j]-'0');}}//最后处理进位string ret;int t = 0, i = 0;while(i<tmp.size() || t>0){if(i<m+n-1) t+=tmp[i++];ret+=t%10+'0';t/=10;}//处理前导'0'while(ret.size()>1 && ret.back() == '0') ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};