中国建设教育网站,网站备案和域名备案区别,开发公司年度工作总结及明年工作计划,wordpress qq快捷登陆关于字符串操作
这类题一般是和其它算法合起来#xff0c;比如模拟#xff0c;双指针#xff0c;动态规划或者回溯等#xff0c;所以字符串相关的题目类型一般是非常非常丰富的#xff0c;这里我们选取几道经典的题目进行讲解
部分OJ题详解
14. 最长公共前缀
14. 最长…关于字符串操作
这类题一般是和其它算法合起来比如模拟双指针动态规划或者回溯等所以字符串相关的题目类型一般是非常非常丰富的这里我们选取几道经典的题目进行讲解
部分OJ题详解
14. 最长公共前缀
14. 最长公共前缀 - 力扣LeetCode 题目题意还是很简单的就是返回单词的公共前缀没有公共前缀就返回空下面来分析下这道题
解法一两两比较找公共前缀假设有四个字符串分成三组每两组找公共前缀然后再两个前缀再找公共前缀最终结果就是所有字符串的公共前缀这道题我们主要就是解决“如何找到两个字符串的公共前缀”很简单定义两个指针即可解法二统一比较就是定义一个指针然后一次性比较所有字符串的前缀当有空或者有一个字符不一样停止遍历返回结果。
解法一
class Solution {
public:string longestCommonPrefix(vectorstring strs) {string ret strs[0];for(int i 1; 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;//i是遍历两个字符串的指针所以i的大小必须小于等于最短的那个字符串不然会越界访问return s1.substr(0, i);}
};
解法二
class Solution {
public:string longestCommonPrefix(vectorstring 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() || tmp ! strs[j][i])return strs[0].substr(0, i);}return strs[0];}
};
5. 最长回文字串
5. 最长回文子串 - 力扣LeetCode 题目要我们找出一个字符串s中的最长回文字串其中这个字串是一串连续的字串下面我们来分析下这道题
解法中心扩展算法这个算法的本质还是暴力枚举但是这里是利用了回文串的特性来做枚举的比正常枚举要快我们先固定一个位置假设为i然后定义两个指针向前向后移动因为如果是回文左边和右边的字符是对称的所以指针移动的时候如果指针指向的值相同就继续移动如果不一样了记录结果但是这样只能找奇数的回文字串偶数的找不了所以我们固定i先left right找奇数找一次然后再right left 1再找偶数找一次就能把奇数偶数全找到步骤1固定一个中心点 2从中心开始向两边扩展奇数偶数各找一次
class Solution {
public:string longestPalindrome(string s) {int begin 0, len 0; for(int i 0; i s.size(); i) //依次枚举所有的中点{//先找奇数的扩展int left i, right i;while(left 0 right s.size()){if(s[left] s[right]){left--;right;}elsebreak;}if(right - left - 1 len){begin left 1;len right - left - 1;}//再做偶数的扩展left i, right left 1;while(left 0 right s.size()){if(s[left] s[right]){left--;right;}elsebreak;}if(right - left - 1 len){begin left 1;len right - left - 1;}} return s.substr(begin, len);}
};
67. 二进制求和
67. 二进制求和 - 力扣LeetCode 这个题目是一道经典的算法题用到的算法是“高精度加法”而同样的还是高精度减法乘法和触发。而高精度顾名思义就是一个数实在是太大平常的数据类型存不下然后我们要对这种很大的数字进行运算用到的算法就是“高精度运算” 下面我们来分析下这道题
解法模拟列竖式运算。这道题和我们链表章节的“两数相加”那个题目很相似我们定义一个t 0记录相加的结果具体步骤和链表的“两数相加”很像算法学习八 —— 链表-CSDN博客
class Solution {
public:string addBinary(string a, string b) {string ret;int cur1 a.size() - 1, cur2 b.size() - 1, 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;}
};
43. 字符串相乘
43. 字符串相乘 - 力扣LeetCode 这一题用到的就是我们上一题提到的“高精度乘法”这个算法题目很简单就是把字符串的值相乘注意不能使用stoi和to_string等字符串整型转换函数因为这时题目要求的下面来解释下这道题
解法一模拟列竖式运算步骤一单独拿nums2的一位和num1相乘 步骤而再把所有的结果累加起来。细节一高位相乘的时候要补0 细节二处理前导0 细节三注意计算结果的顺序可以看到解法一思路很简单但是细节很多很多稍不注意就会出错所以解法一的代码不太好写解法二对解法一做优化 -- 五进位相乘再相加最后处理进位对于步骤②我们可以搞一个数组int[m n - 1] tmpm是num1的程度n是num2的长度然后我们就可以直接相加因为同一列算出来的数存进数组时下标是一样的可以直接相加对于步骤③就是处理进位就是遍历一次数组然后一边累加再放到最终字符串ret里细节处理前导零 解法一的代码太复杂就不写了我们直接用解法二来写
class Solution {
public:string multiply(string num1, string num2) {//解法二无进位相乘然后相加最后处理进位//1准备工作reverse(num1.begin(), num1.end()); reverse(num2.begin(), num2.end()); //逆序是为了方便处理前导零int m num1.size(), n num2.size();vectorint tmp(m n - 1); //存储步骤②的结果顺便实现相加//2无进位相乘再相加for(int i 0; i m; i){for(int j 0; j n; j)tmp[i j] ((num1[i] - 0) * (num2[j] - 0));}//3处理进位int cur 0, t 0; //cur遍历数组t表示进位string ret; //存储最终结果while(cur m n - 1 || t ! 0){if(cur m n - 1) t tmp[cur];ret (t % 10) 0;t / 10;}//4处理前导零while(ret.size() 1 ret.back() 0) ret.pop_back();reverse(ret.begin(), ret.end());return ret;}
};
