青岛网站设计,网站建设与管理模拟试卷一,属于教育主管部门建设的专题资源网站是,可以做微网站的第三方平台目录
1、14. 最长公共前缀
2、 5. 最长回文子串
3、 67. 二进制求和
4、43. 字符串相乘 1、14. 最长公共前缀 思路一#xff1a;两两字符串进行比较#xff0c;每次比较过程相同#xff0c;可以添加一个函数辅助比较#xff0c;查找最长公共前缀。 class Solution {
pu…目录
1、14. 最长公共前缀
2、 5. 最长回文子串
3、 67. 二进制求和
4、43. 字符串相乘 1、14. 最长公共前缀 思路一两两字符串进行比较每次比较过程相同可以添加一个函数辅助比较查找最长公共前缀。 class Solution {
public:string longestCommonPrefix(vectorstring strs) {string ret strs[0];for (int i 0; i strs.size(); i) {ret findcommon(ret, strs[i]);}return ret;}string findcommon(string s1, string s2) {int i 0;while (i min(s1.size(), s2.size()) s1[i] s2[i]) {i;}return s1.substr(0, i);}
}; 思路二选取一个字符串与其他字符串逐位比较比较过程中如果有一个字符串能遍历到最后或某个字符与当前比较的字符不相等则该字符串为最长公共前缀。 class Solution {
public:string longestCommonPrefix(vectorstring strs) {for (int i 0; i strs[0].size(); i) {char s strs[0][i];for (int j 1; j strs.size(); j) {if (i strs[j].size() || s ! strs[j][i])return strs[0].substr(0, i);}}return strs[0];}
};
2、 5. 最长回文子串 思路中心扩展法 中心扩展法这种方法的核心思想是回文子串的构造是对称的所以可以从中心开始向两边扩展检查两边的字符是否相等。这种方法需要考虑奇数长度和偶数长度的回文子串因此对每个字符尝试两次扩展一次将其视为中心奇数长度一次将其和下一个字符共同视为中心偶数长度。 时间复杂度由于需要对字符串中的每个字符都尝试向两边扩展最坏情况下每次扩展可能会遍历整个字符串因此总的时间复杂度为O(n^2)其中n是字符串的长度。 空间复杂度这个算法只使用了固定的额外空间begin、len等变量因此空间复杂度为O(1)。 通过这种方法即使在字符串长度较长的情况下也能有效地找到最长的回文子串。 class Solution {
public:string longestPalindrome(string s) {int begin 0, len 0, n s.size();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) {begin left 1;len right - left - 1;}left i, right i 1;while (left 0 right n s[left] s[right]) {left--, right;}if (right - left - 1 len) {begin left 1;len right - left - 1;}}return s.substr(begin, len);}
}; 首先定义了三个变量begin记录最长回文子串的起始位置、len记录最长回文子串的长度、n记录字符串s的长度。 然后通过一个循环遍历字符串s中的每个字符。在循环中以当前字符为中心向两边扩展找到以当前字符为中心的最长回文子串长度。 在第一个循环中以当前字符为中心向左右两边扩展直到不再满足回文条件即字符不相等或越界。在扩展的过程中记录下当前回文子串的起始位置和长度。 接着在第二个循环中以当前字符和下一个字符为中心向左右两边扩展找到以这两个字符为中心的最长回文子串长度。 在每次扩展过程中比较当前找到的回文子串长度与之前记录的最长回文子串长度如果当前找到的更长则更新begin和len。 最后返回找到的最长回文子串通过使用substr函数从原始字符串s中截取出最长回文子串。
3、 67. 二进制求和 思路模拟列竖式计算注意二进制求和逢二进一。 class Solution {
public:string addBinary(string a, string b) {int cur1 a.size() - 1, cur2 b.size() - 1;string ret;int t 0;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、43. 字符串相乘 思路一无进位相加这个算法的关键在于通过逐位相乘和处理进位来实现大数乘法避免了直接使用大数运算使得算法能够处理非常大的数。 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();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);}}int cur 0, t 0;string ret;while (cur m n - 1 || t) {if (cur m n - 1) {t tmp[cur];}ret t % 10 0;t / 10;}while (ret.size() 1 ret.back() 0) {ret.pop_back();}reverse(ret.begin(), ret.end());return ret;}
}; 整个过程模拟了人工进行乘法计算的过程先计算每一位的乘积然后逐步处理进位最后得到结果。这种方法不依赖于任何大数处理库能够处理非常大的数的乘法只受限于内存和处理时间。 反转字符串首先将num1和num2两个字符串反转这样做是为了从最低位开始计算乘积便于后续的逐位相乘和累加。 初始化临时数组创建一个长度为m n - 1的临时数组tmp用于存储乘积的每一位。这里m和n分别是num1和num2的长度。数组的长度之所以是m n - 1是因为两个数最多可以产生这么长的乘积。 逐位相乘遍历num1和num2的每一位将每一位的乘积累加到tmp数组对应的位置上。这里使用(num1[i] - 0) * (num2[j] - 0)来计算两位数字的乘积并累加到tmp[i j]上。 处理进位遍历tmp数组将每一位的值加上前一位的进位t然后计算当前位的值t % 10和新的进位t / 10。这一步确保了每一位上的数字都是单个数字并且正确处理了进位。 去除前导零由于最开始反转了字符串最终得到的结果也是反转的且可能包含前导零。因此需要去除结果字符串尾部的所有0直到结果字符串的长度大于1或者最后一个字符不是0。 反转结果字符串最后将结果字符串再次反转得到正确的乘积结果。 返回结果返回处理后的结果字符串。 思路二 直接模拟 class Solution {
public:string multiply(string num1, string num2) {if (num1 0 || num2 0)return 0;int n1 num1.size(), n2 num2.size();string result(n1 n2, 0);for (int i n1 - 1; i 0; i--) {for (int j n2 - 1; j 0; j--) {int product (num1[i] - 0) * (num2[j] - 0) (result[i j 1] - 0);result[i j 1] product % 10 0;result[i j] product / 10;}}size_t startpos result.find_first_not_of(0);return result.substr(startpos);}
}; 特殊情况处理如果num1或num2中任何一个是0则乘积也是0直接返回0。 初始化结果字符串创建一个长度为n1 n2的字符串result所有位初始化为0。这是因为两个长度分别为n1和n2的数相乘其结果长度最多为n1 n2。 逐位相乘并累加从num1和num2的最低位开始即字符串的末尾对每一对位进行乘法运算并将乘积累加到结果字符串的相应位置。这里需要注意的是乘积需要加上结果字符串中已经存在的数值因为可能之前已经有累加的结果所以使用(result[i j 1] - 0)来获取并更新结果。 处理进位计算每一步的乘积后可能会产生进位。进位被加到下一位的累加结果中。这里通过result[i j 1] product % 10 0;来更新当前位的结果并通过result[i j] product / 10;来处理进位。 去除前导零由于初始化结果字符串时所有位都是0乘积的计算可能会在结果字符串的前面留下一些不必要的零。使用find_first_not_of(0)找到第一个非零字符的位置并使用substr方法截取从这个位置到字符串末尾的子串作为最终结果。 返回结果如果结果字符串中没有找到非零字符即find_first_not_of返回string::npos则说明结果为0否则返回去除前导零后的结果字符串。
