ARTS 029
这是第29篇
ARTS是
由左耳朵耗子--陈皓发起的一个活动: 每周至少做一个leetcode的算法题、阅读并点评至少一篇英文技术文章、学习至少一个技术技巧、分享一篇有观点和思考的文章。（也就是Algorithm、Review、Tip、Share简称ARTS），至少坚持一年。
Algorihm 算法题
5. 最长回文子串
Difficulty: 中等
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
Solution
Language: C
暴力法
//暴力法 时间复杂度为O(N^3)
char* longestPalindrome_1(char* s) {
int len = strlen(s); //字符串长度
printf("==： %d",len);
int maxlen = 1; //最长回文字符串长度
int start = 0; //最长回文字符串起始地址
for(int i = 0; i < len; i++) //起始地址
{
for(int j = i + 1; j < len; j++) //结束地址
{
int tmp1 = i, tmp2 = j;
while(tmp1 < tmp2 && s[tmp1] == s[tmp2])//判断是不是回文
{
tmp1++;
tmp2--;
}
if(tmp1 >= tmp2 && j - i + 1 > maxlen)
{
maxlen = j - i + 1;
start = i;
}
}
}
char *res = (char*)malloc(sizeof(char) * (maxlen + 1));
for (int i = 0; i < maxlen; i++) {
res[i] = s[start +i];
}
res[maxlen] = '\0';
return res;
}
动态规划
//动态规划 时间复杂度为O(N^2)
char* longestPalindrome_2(char* s) {
const int n = strlen(s);
if (n==0) {
return s;
}
int dp[n][n];
memset(dp, 0, sizeof(dp));
int maxlen = 1; //保存最长回文子串长度
int start = 0; //保存最长回文子串起点
for(int i = 0; i < n; ++i)
{
for(int j = 0; j <= i; ++j)
{
if(i - j < 2)
{
dp[j][i] = (s[i] == s[j]);
}
else
{
dp[j][i] = (s[i] == s[j] && dp[j + 1][i - 1]);
}
if(dp[j][i] && maxlen < i - j + 1)
{
maxlen = i - j + 1;
start = j;
}
}
}
char *res = (char*)malloc(sizeof(char) * (maxlen + 1));
for (int i = 0; i < maxlen; i++) {
res[i] = s[start +i];
}
res[maxlen] = '\0';
return res;
}
中心扩展法
//中心扩展法 时间复杂度为O(N^2)
char* longestPalindrome_3(char* s)
{
const int len = strlen(s);
if (len == 0) {
return s;
}
int maxlen = 1;
int start = 0;
for(int i = 0; i < len; i++)//求长度为奇数的回文串
{
int j = i - 1, k = i + 1;
while(j >= 0 && k < len && s[j] == s[k])
{
if(k - j + 1 > maxlen)
{
maxlen = k - j + 1;
start = j;
}
j--;
k++;
}
}
for(int i = 0; i < len; i++)//求长度为偶数的回文串
{
int j = i, k = i + 1;
while(j >= 0 && k < len && s[j] == s[k])
{
if(k - j + 1 > maxlen)
{
maxlen = k - j + 1;
start = j;
}
j--;
k++;
}
}
char *res = (char*)malloc(sizeof(char) * (maxlen + 1));
for (int i = 0; i < maxlen; i++) {
res[i] = s[start +i];
}
res[maxlen] = '\0';
return res;
}
Manacher’s Algorithm 马拉车算法,具体参见： https://www.cnblogs.com/grandyang/p/4475985.html
char* longestPalindrome(char* s){
const int len = strlen(s);
if (len == 0) {
return s;
}
char *t = (char*)malloc(sizeof(char) * (len*2 + 2 +1));
t[0] = '$';
t[1] = '#';
for (int i = 0; i < len; i++) {
t[2+i*2]= s[i];
t[2+i*2 +1]= '#';
}
t[len*2 + 2 ] = '\0';
const int tLen = strlen(t);
int* p = (int* )malloc(sizeof(int) * (tLen));
int mx = 0, id = 0, resLen = 0, resCenter = 0;
for (int i = 1; i < tLen; ++i) {
int tem = 0;
if (2 * id - i >= 0 ) {
if (p[2 * id - i] > mx - i) {
tem = mx - i;
}
else{
tem = p[2 * id - i];
}
}
p[i] = mx > i ? tem : 1;
while (t[i + p[i]] == t[i - p[i]]) ++p[i];
if (mx < i + p[i]) {
mx = i + p[i];
id = i;
}
if (resLen < p[i]) {
resLen = p[i];
resCenter = i;
}
}
free(t);
free(p);
int start = (resCenter - resLen) / 2;
int maxlen = resLen - 1;
char *res = (char*)malloc(sizeof(char) * (maxlen + 1));
for (int i = 0; i < maxlen; i++) {
res[i] = s[start +i];
}
res[maxlen] = '\0';
return res;
}
6. Z 字形变换
Difficulty: 中等
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);```
**示例 1:**
输入: s = “LEETCODEISHIRING”, numRows = 3 输出: “LCIRETOESIIGEDHN”
**示例 2:**
输入: s = “LEETCODEISHIRING”, numRows = 4 输出: ”LDREOEIIECIHNTSG” 解释:
L D R E O E I I E C I H N T S G```
Solution
Language: C
char* convert(char* s, int numRows) {
}
这个题就是找规律
