一、相关编程题
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结果相加到ret
for(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;
}
};
