最長的回文子串

題目描述

給定一個字符串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為 1000。

解題思路

可以跟無重復的最長子串一樣，用一個滑動窗口，只不過這個窗口的右邊界往右，左邊界每回要從右邊界的下標往左。
還需要一個二維數(shù)組記錄當前窗口中記錄的字符串是不是回文串
再需要一個變量記錄回文串的長度。比較出最大的回文串
例如：baccab

首先定義右邊界right，左邊界left = right；從右邊界的下標開始，如何判斷當前窗口是否是回文串？第一步：判斷兩端值是否相等str[i] == str[j] ,第二步：判斷窗口去除兩端外，里面的字符串是不是回文串：s[i+1][j-1]，如果長度小于3 right-left<=2，并且兩端相同，那么去除兩端必定為回文串 。經(jīng)過上述判斷則可以說明當前區(qū)間就為回文串，所以標記i~j區(qū)間中array[i][j] = true; 并記錄回文串并計算長度，如果該區(qū)間長度大于之前記錄的回文串的長度再記錄right-left>length。res = susbtr(left,right-left+1); 從左邊界開始截取長度為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，判斷兩端不相同，直接下一個循環(huán)

right再來到c的位置，往后依次類推…

代碼實現(xiàn)

class Solution { public:string longestPalindrome(string s) {int n = s.size();//記錄字符串是否為回文字符串vector<vector<bool>> array (n,vector<bool>(n));string res = "";//記錄結果返回int length = 0; //記錄長度，比較出最長的回文子串if(n == 0)return s;if(n == 1)return s;//如果是兩個字符，則返回第一個字符res = s[0]; //外層循環(huán)右邊界for(int right = 0;right<n;++right){//內(nèi)層循環(huán)左邊界for(int left = right;left>=0;--left){//判斷是否為回文字串if(s[left] == s[right] //兩頭相等&& (right-left<=2 //長度小于等于3，并且兩頭相等比為回文串|| array[left+1][right-1]) //去掉兩頭，中間也是回文串才是回文串){//標記left~right該區(qū)間為回文串array[left][right] = true;if(right-left>length) //如果回文串長度大于之前記錄的長度，則記錄該串{res = s.substr(left,right-left+1);length = right-left; //記錄新長度} }}}return res;} };

Z字形變換

題目描述

將一個給定字符串根據(jù)給定的行數(shù)，以從上往下、從左到右進行 Z 字形排列。

比如輸入字符串為 “LEETCODEISHIRING” 行數(shù)為 3 時，排列如下：

解題思路

一共四行numbers = 4
找規(guī)律，

第0行，0-6-12 ， 間隔為6

第1行，1-5-7-11-13 間隔為4-2-4-2 奇數(shù)行
step-2*1(行)-2*1(行)-step-2*1(行)-2*1(行)

第2行，2-4-8-10-14，間隔為2-4-2-4 偶數(shù)行
step-2*2(行)-2*2(行)-step-2*2(行)-2*2(行)

第3行，3-9-15 ，間隔為6

第一行和和最后一行，為step = 2*numbers-2
中間是中間層的下標間距總是step-2*行數(shù)，2*行數(shù)交替

代碼實現(xiàn)

class Solution { public:string convert(string s, int numRows) {if(numRows == 1) //如果只有一行數(shù)據(jù)直接返回return s;int step = numRows*2 - 2;string res = "";int index = 0; //記錄每行元素的下標int add = 0; //中間行間隔for(int i = 0; i<numRows;++i){index = i; //標記行數(shù)add = 2*i ; //出去第0行和numRows-1行中間行的間隔while(index<s.size()) //元素下標大于總個數(shù)要換行{res+=s[index];add = step - add ; //變換間隔，index += (i == 0 || i == numRows-1) ? step : add; //每行每個元素的下標都在變}}return res;} };

總結

以上是生活随笔為你收集整理的LeetCode【5--最长的回文子串】 LeetCode【6--Z字形变换】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。