专题十——字符串
目录
1最长公共前缀
2最长回文子串
3二进制求和
4字符串相乘
1最长公共前缀
oj链接：最长公共前缀
// 解法1
class Solution
{
public:string longestCommonPrefix(vector<string> &strs){string ret = strs[0];for (int i = 1; i < strs.size(); i++){ret = FindComm(ret, strs[i]);}return ret;}string FindComm(string &s1, 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(vector<string> &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];}
};2最长回文子串
oj链接：最长回文子串
//动态规划版本 很重要！！
class Solution
{
public:string longestPalindrome(string s){int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n, false));for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){if (s[i] == s[j]){if (i == j || i + 1 == j || dp[i + 1][j - 1])dp[i][j] = true;}}}int begin = 0, len = 0;for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (dp[i][j]){if (j - i + 1 > len){len = j - i + 1;begin = i;}}}}return s.substr(begin, len);}
};//中心扩展算法
class Solution
{
public:string longestPalindrome(string s){int n = s.size();int begin = 0, len = 0;for (int i = 0; i < n; i++){// 奇数扩展int left = i - 1, right = i + 1;while (left >= 0 && right < n && s[left] == s[right]){left--; // 细节right++;}int newlen = right - left - 1; // 细节if (newlen > len){begin = left + 1; // 细节len = newlen;}// 偶数扩展left = i, right = i + 1;while (left >= 0 && right < n && s[left] == s[right]){left--;right++;}newlen = right - left - 1;if (newlen > len){begin = left + 1;len = newlen;}}return s.substr(begin, len);}
};3二进制求和
oj链接： 二进制求和
class Solution
{
public:string addBinary(string a, string b){int cur1 = a.size() - 1, cur2 = b.size() - 1, t = 0;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字符串相乘
oj链接：字符串相乘
// 解法1
class Solution
{
public:string multiply(string num1, string num2){if (num1 == "0" || num2 == "0")return "0";string ret = "0";reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());for (int i = 0; i < num1.size(); i++){string tmp;for (int a = 0; a < i; a++)tmp += "0"; // 高位补0int flag = 0;for (int j = 0; j < num2.size(); j++){int sum = (num1[i] - '0') * (num2[j] - '0') + flag;flag = sum / 10;tmp += (sum % 10) + '0';}if (flag != 0)tmp += flag + '0';// tmp类加到ret中int cur1 = 0, cur2 = 0, t = 0;string ret1;while (cur1 < ret.size() || cur2 < tmp.size() || t){if (cur1 < ret.size())t += ret[cur1++] - '0';if (cur2 < tmp.size())t += tmp[cur2++] - '0';ret1 += t % 10 + '0';t /= 10;}ret = ret1;}// 记得要逆序回去reverse(ret.begin(), ret.end());return ret;}
};// 解法2
class Solution
{
public:string multiply(string num1, string num2){if (num1 == "0" || num2 == "0")return "0";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;// tmp的数据写成string类型int flag = 0;for (int i = m + n - 2; i >= 0; i--){int sum = tmp[i] + flag;ret += sum % 10 + '0';flag = sum / 10;cout << ret << endl;}if (flag != 0)ret += flag + '0';reverse(ret.begin(), ret.end());return ret;}
};class Solution
{
public:// 无进位相加string multiply(string num1, string num2){if (num1 == "0" || num2 == "0")return "0";int n1 = num1.size(), n2 = num2.size();// 为了能让数组与下标对应reverse(num1.begin(), num1.end());reverse(num2.begin(), num2.end());vector<int> ret(n1 + n2 - 1);for (int i = 0; i < n1; i++){for (int j = 0; j < n2; j++){ret[i + j] += ((num1[i] - '0') * (num2[j] - '0'));}}string s = "0";int cur = 0, t = 0;string ans;while (cur < n1 + n2 - 1 || t != 0){if (cur < n1 + n2 - 1)t += ret[cur++];ans += t % 10 + '0';t /= 10;}reverse(ans.begin(), ans.end());return ans;}
};以上便是全部内容，有问题欢迎在评论区指正：感谢观看！