ARTS #029

ARTS 029

This is article 29

ARTS is an activity initiated by 由左耳朵耗子--陈皓: Do at least one leetcode algorithm question every week, read and comment on at least one English technical article, learn at least one technical skill, and share an article with opinions and thoughts. (That is, Algorithm, Review, Tip, and Share are referred to as ARTS) and persist for at least one year.

Algorihm algorithm question

5. Longest palindrome substring

Difficulty: Medium

Given a string s, find the longest palindrome substring in s. You can assume that the maximum length of s is 1000.

Example 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

Example 2:

输入: "cbbd"
输出: "bb"

Solution

Language: C

violent law

//暴力法 时间复杂度为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;
}

dynamic programming

//动态规划 时间复杂度为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;

}

central expansion method

//中心扩展法 时间复杂度为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 Horse-drawn cart algorithm, see for details: 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 glyph transformation

Difficulty: Medium

Arrange a given string in a zigzag pattern from top to bottom and from left to right according to the given number of lines.

For example, when the input string is "LEETCODEISHIRING" and the number of lines is 3, the arrangement is as follows:

L   C   I   R
E T O E S I I G
E   D   H   N

After that, your output needs to be read line by line from left to right to produce a new string, such as: "LCIRETOESIIGEDHN".

Please implement this function that transforms a string to a specified number of lines:

string convert(string s, int numRows);```

**Example 1:**

输入: s = “LEETCODEISHIRING”, numRows = 3 输出: “LCIRETOESIIGEDHN”

**Example 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) {
    
}

This question is to find the rules

Review

Tips

Share