SENI #029

SENI 029

Ini adalah pasal 29

SENI adalah kegiatan yang diprakarsai oleh 由左耳朵耗子--陈皓: Kerjakan setidaknya satu pertanyaan algoritma leetcode setiap minggu, baca dan komentari setidaknya satu artikel teknis berbahasa Inggris, pelajari setidaknya satu keterampilan teknis, dan bagikan artikel yang berisi opini dan pemikiran. (Artinya, Algoritma, Review, Tip, dan Share disebut sebagai SENI) dan bertahan setidaknya selama satu tahun.

Pertanyaan algoritma algoritma

5. Substring palindrom terpanjang

Kesulitan: Sedang

Diberikan string s, temukan substring palindrom terpanjang di s. Anda dapat berasumsi bahwa panjang maksimum s adalah 1000.

Contoh 1:

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

Contoh 2:

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

Solusi

Bahasa: C

hukum kekerasan

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

pemrograman dinamis

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

}

metode ekspansi sentral

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

Algoritma Manacher Algoritma kereta kuda, lihat detailnya: 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 transformasi mesin terbang

Kesulitan: Sedang

Susunlah senar tertentu dalam pola zigzag dari atas ke bawah dan dari kiri ke kanan sesuai dengan jumlah garis yang ditentukan.

Misalnya string inputnya adalah "LEETCODEISHIRING" dan jumlah barisnya 3, maka susunannya adalah sebagai berikut:

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

Setelah itu output Anda perlu dibaca baris demi baris dari kiri ke kanan untuk menghasilkan string baru, seperti: "LCIRETOESIIGEDHN".

Harap terapkan fungsi ini yang mengubah string menjadi sejumlah baris tertentu:

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

**Contoh 1:**

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

**Contoh 2:**

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

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

Solusi

Bahasa: C

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

Pertanyaan ini untuk menemukan aturannya

Ulasan

Kiat

Bagikan