ARTES #029

ARTES 029

Este é o artigo 29

ARTS é uma atividade iniciada por 由左耳朵耗子--陈皓: Faça pelo menos uma pergunta sobre o algoritmo leetcode toda semana, leia e comente pelo menos um artigo técnico em inglês, aprenda pelo menos uma habilidade técnica e compartilhe um artigo com opiniões e pensamentos. (Ou seja, Algoritmo, Revisão, Dica e Compartilhamento são chamados de ARTS) e persistem por pelo menos um ano.

Pergunta sobre algoritmo de algoritmo

5. Substring do palíndromo mais longa

Dificuldade: Média

Dada uma string s, encontre a substring do palíndromo mais longa em s. Você pode assumir que o comprimento máximo de s é 1000.

Exemplo 1:

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

Exemplo 2:

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

Solução

Idioma: C

lei 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;
}

programação 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 expansão 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ça puxada por cavalo, veja para detalhes: 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;
}

transformação de glifo 6.Z

Dificuldade: Média

Organize uma determinada corda em zigue-zague de cima para baixo e da esquerda para a direita de acordo com o número determinado de linhas.

Por exemplo, quando a string de entrada é "LEETCODEISHIRING" e o número de linhas é 3, a organização é a seguinte:

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

Depois disso, sua saída precisa ser lida linha por linha, da esquerda para a direita, para produzir uma nova string, como: "LCIRETOESIIGEDHN".

Implemente esta função que transforma uma string em um número especificado de linhas:

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

**Exemplo 1:**

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

**Exemplo 2:**

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

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

Solução

Idioma: C

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

Esta questão é encontrar as regras

Revisão

Dicas

Compartilhar