做好网站建设工作,网络运维面试题,家具网站模版,简单个人网站制作教程最长的回文子串
题目描述
给定一个字符串 s#xff0c;找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
解题思路
可以跟无重复的最长子串一样#xff0c;用一个滑动窗口#xff0c;只不过这个窗口的右边界往右#xff0c;左边界每回要从右边界的下标往左…最长的回文子串
题目描述
给定一个字符串 s找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
解题思路
可以跟无重复的最长子串一样用一个滑动窗口只不过这个窗口的右边界往右左边界每回要从右边界的下标往左。 还需要一个二维数组记录当前窗口中记录的字符串是不是回文串 再需要一个变量记录回文串的长度。比较出最大的回文串 例如baccab
首先定义右边界right左边界left right从右边界的下标开始如何判断当前窗口是否是回文串第一步判断两端值是否相等str[i] str[j] ,第二步判断窗口去除两端外里面的字符串是不是回文串s[i1][j-1]如果长度小于3 right-left2并且两端相同那么去除两端必定为回文串 。经过上述判断则可以说明当前区间就为回文串所以标记i~j区间中array[i][j] true; 并记录回文串并计算长度如果该区间长度大于之前记录的回文串的长度再记录right-leftlength。res susbtr(left,right-left1); 从左边界开始截取长度为right - left 1的长度。length right-left;对于baccab来说首先 str[right] b ,str[left] str[right] b,两端相同又因为长度小于3所以b是回文字符串array[i][j] true; 此时长度大于length记录然后right来到a的位置left也跟着来到a的位置开始往左走走到b判断两端不相同直接下一个循环right再来到c的位置往后依次类推…
代码实现
class Solution {
public:string longestPalindrome(string s) {int n s.size();//记录字符串是否为回文字符串vectorvectorbool array (n,vectorbool(n));string res ;//记录结果返回int length 0; //记录长度比较出最长的回文子串if(n 0)return s;if(n 1)return s;//如果是两个字符则返回第一个字符res s[0]; //外层循环右边界for(int right 0;rightn;right){//内层循环左边界for(int left right;left0;--left){//判断是否为回文字串if(s[left] s[right] //两头相等 (right-left2 //长度小于等于3并且两头相等比为回文串|| array[left1][right-1]) //去掉两头中间也是回文串才是回文串){//标记left~right该区间为回文串array[left][right] true;if(right-leftlength) //如果回文串长度大于之前记录的长度则记录该串{res s.substr(left,right-left1);length right-left; //记录新长度} }}}return res;}
};Z字形变换
题目描述
将一个给定字符串根据给定的行数以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时排列如下
解题思路 一共四行numbers 4 找规律
第0行0-6-12 间隔为6第1行1-5-7-11-13 间隔为4-2-4-2 奇数行 step-2*1(行)-2*1(行)-step-2*1(行)-2*1(行)第2行2-4-8-10-14间隔为2-4-2-4 偶数行 step-2*2(行)-2*2(行)-step-2*2(行)-2*2(行)第3行3-9-15 间隔为6
第一行和和最后一行为step 2*numbers-2 中间是中间层的下标间距总是step-2*行数2*行数交替
代码实现
class Solution {
public:string convert(string s, int numRows) {if(numRows 1) //如果只有一行数据直接返回return s;int step numRows*2 - 2;string res ;int index 0; //记录每行元素的下标int add 0; //中间行间隔for(int i 0; inumRows;i){index i; //标记行数add 2*i ; //出去第0行和numRows-1行中间行的间隔while(indexs.size()) //元素下标大于总个数要换行{ress[index];add step - add ; //变换间隔index (i 0 || i numRows-1) ? step : add; //每行每个元素的下标都在变}}return res;}
};
