ARTES #029

##ARTES 029

este es el articulo 29

ARTES es una actividad iniciada por 由左耳朵耗子--陈皓: Haga al menos una pregunta sobre el algoritmo leetcode cada semana, lea y comente al menos un artículo técnico en inglés, aprenda al menos una habilidad técnica y comparta un artículo con opiniones y pensamientos. (Es decir, Algoritmo, Revisión, Sugerencia y Compartir se denominan ARTS) y persisten durante al menos un año.

Pregunta sobre el algoritmo del algoritmo

5. Subcadena palíndromo más larga

Dificultad: Media

Dada una cadena s, busque la subcadena palíndromo más larga en s. Puede suponer que la longitud máxima de s es 1000.

Ejemplo 1:

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

Ejemplo 2:

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

Solución

Idioma: C

ley violenta

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

programación dinámica

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

}

método de expansión central

//中心扩展法 时间复杂度为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;
}

Algoritmo de Manacher Algoritmo de carro tirado por caballos, ver para más detalles: 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;
}

Transformación de glifo 6.Z

Dificultad: Media

Organice una cuerda determinada en forma de zigzag de arriba a abajo y de izquierda a derecha de acuerdo con el número de líneas dado.

Por ejemplo, cuando la cadena de entrada es "LEETCODEISHIRING" y el número de líneas es 3, la disposición es la siguiente:

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

Después de eso, su salida debe leerse línea por línea de izquierda a derecha para producir una nueva cadena, como por ejemplo: "LCIRETOESIIGEDHN".

Implemente esta función que transforma una cadena en un número específico de líneas:

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

**Ejemplo 1:**

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

**Ejemplo 2:**

输入: s = “LEETCODEISHIRING”, numRows = 4 输出: “LDREOEIIECIHNTSG” 解释:

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

Solución

Idioma: C

char* convert(char* s, int numRows) {
    
}

Esta pregunta es para encontrar las reglas.

Revisión

Consejos

Compartir