الفنون رقم 029

الفنون 029

هذه المادة 29

ARTS هو نشاط بدأه 由左耳朵耗子--陈皓: قم بإجراء سؤال واحد على الأقل عن خوارزمية leetcode كل أسبوع، واقرأ مقالًا تقنيًا واحدًا على الأقل باللغة الإنجليزية وعلق عليه، وتعلم مهارة فنية واحدة على الأقل، وشارك المقالة مع الآراء والأفكار. (أي أن الخوارزمية والمراجعة والنصائح والمشاركة يشار إليها باسم ARTS) وتستمر لمدة عام واحد على الأقل.

سؤال خوارزمية الخوارزمية

5. أطول سلسلة فرعية متناظرة

الصعوبة: متوسطة

بالنظر إلى سلسلة s، ابحث عن أطول سلسلة فرعية متناظرة في s. يمكنك افتراض أن الحد الأقصى لطول s هو 1000.

مثال 1:

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

مثال 2:

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

الحل

اللغة: ج

قانون عنيف

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

خوارزمية ماناشر، خوارزمية العربة التي تجرها الخيول، انظر لمزيد من التفاصيل: 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

الصعوبة: متوسطة

قم بترتيب سلسلة معينة في نمط متعرج من الأعلى إلى الأسفل ومن اليسار إلى اليمين وفقًا لعدد الأسطر المحدد.

على سبيل المثال، عندما تكون سلسلة الإدخال "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```

الحل

اللغة: ج

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

هذا السؤال هو العثور على القواعد

مراجعة

نصائح

شارك