字符串题目有很多种,这里筛选几个考察模拟、双指针等的题目,并用相关算法解决。
思路
代码
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string ret = strs[0];
// 解法一:两两比较,找公共前缀
for(int i = 0; i < strs.size(); i++)
{
ret = findCommonPrefix(ret, strs[i]);
}
return ret;
}
string findCommonPrefix(string &s1, string& s2) {
// 找公共前缀
string tmp = "";
for(int i = 0; i < min(s1.size(), s2.size()); ++i)
{
if(s1[i] == s2[i])
tmp += s1[i];
else
break;
}
return tmp;
}
};
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
// 解法二:统一比较
for(int i = 0; i < strs[0].size(); ++i) // 遍历第一个字符串的所有字符
{
char tmp = strs[0][i]; // tmp与其他字符比较
for(int j = 0; j < strs.size(); ++j)
{
if(tmp != strs[j][i] || i == strs[j].size()) // 如果字符不匹配or有字符串最终长度截止到当前位置
return strs[0].substr(0, i);
}
}
return strs[0];
}
};
思路
代码
string longestPalindrome(string s) {
// 遍历每一位,双指针按从左右方向移动,并比较
int len = 0, n = s.size(), begin = 0; // begin存储最长子串的开始位置
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,更新结果
{
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);
}
思路
代码
string addBinary(string a, string b) {
int carry = 0; // 记录是否有进位
int cur1 = a.size()-1, cur2 = b.size()-1;
string ret = "";
while(cur1 >= 0 || cur2 >= 0 || carry)
{
if(cur1 >= 0) carry += a[cur1--] - '0';
if(cur2 >= 0) carry += b[cur2--] - '0';
ret += carry % 2 + '0'; // carry%2即为相加的和
carry /= 2; // 下一位的进位
}
// 由于字符串是逐渐累加结果的,翻转后的字符串才是二进制顺序
reverse(ret.begin(), ret.end());
return ret;
}
思路
代码
string multiply(string num1, string num2) {
// 解法:模拟列式运算过程
// 1. 逆序字符串,从个位开始计算
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
// 2. 不进位相乘后相加
int m = num1.size(), n = num2.size();
vector<int> tmp(m + n - 1);
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
// 3. 处理进位
string ret = "";
int cur = 0, carry = 0;
while(cur < m + n - 1 || carry)
{
if(cur < m + n - 1) carry += tmp[cur++]; // 记录当前位置元素
ret += (carry % 10) + '0'; // ret加上个位
carry /= 10; // 下一位的进位数
}
cout << ret;
// 4. 去掉前导0
while(ret.size() > 1 && ret.back() == '0')
ret.pop_back();
reverse(ret.begin(), ret.end());
return ret;
}