案列网站,企业网站托管后果,关键词优化策略有哪些,移动网站系统文章目录 1. 前言2. 解决 字符串类算法题14.最长公共前缀5.最长回文子串67.二进制求和43.字符串相乘 1. 前言
字符串题目有很多种#xff0c;这里筛选几个考察模拟、双指针等的题目#xff0c;并用相关算法解决。
2. 解决 字符串类算法题
14.最长公共前缀 思路
题意分析这里筛选几个考察模拟、双指针等的题目并用相关算法解决。
2. 解决 字符串类算法题
14.最长公共前缀 思路
题意分析题目要求找到字符串数组中的最长公共前缀。解法一两两比较 遍历数组每次比较后更新最长公共前缀并循环比较找最长公共前缀 解法二统一比较 遍历第一个字符串的所有字符将当前字符与其他字符串相同位置的字符进行比较。如果发现不匹配的字符或某个字符串已经达到最终长度即没有更多字符可比较则返回第一个字符串的前缀子串
代码
解法一
class Solution {
public:string longestCommonPrefix(vectorstring 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];elsebreak;}return tmp;}
};解法二
class Solution {
public:string longestCommonPrefix(vectorstring 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];}
};5.最长回文子串 思路 解法中心扩展算法 如图所示我们遍历数组依次固定数组每一位通过左右两指针找最长回文串。 细节注意 奇数长的回文串与偶数长的回文串计算时两指针起始位置不同所以我们分别进行计算。
代码
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);
}67.二进制求和 思路 解法模拟二进制列式相加的过程 分别用两指针遍历两字符串每次用变量carry累加二进制每一位后将此次carry加到最终结果中carry / 2由于字符串ret是逐渐累加结果的翻转后的字符串才是二进制顺序
代码
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;
}43.字符串相乘 思路
题意分析要求求出 两个字符串表示的整数 的乘积且不得使用库函数直接进行整形和字符串的转换。解法模拟列式相乘的过程 与上题类似我们对两字符串首先进行不进位相乘 将输入的两个字符串逆序从个位开始计算对应位置上的数字相乘并将结果存储在临时数组中后将所有相乘结果相加 处理进位 定义一个变量carry来记录进位数然后从数组的第一位开始将当前位置上的数字与carry相加得到当前位置上的数字的和并更新carry为下一位的进位数将每一位上的结果转换为字符并添加到结果字符串ret中去掉结果字符串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();vectorint 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. 去掉前导0while(ret.size() 1 ret.back() 0)ret.pop_back();reverse(ret.begin(), ret.end());return ret;
}
