الفنون رقم 031

الفنون 031

هذه المادة 31

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

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

9. عدد المتناظرات

الصعوبة: سهل

تحديد ما إذا كان العدد الصحيح هو متناظر. الرقم المتناظر هو عدد صحيح يقرأ نفسه بالترتيب الأمامي (من اليسار إلى اليمين) والترتيب العكسي (من اليمين إلى اليسار).

مثال 1:

输入: 121
输出: true

مثال 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

مثال 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

متقدم:

هل يمكنك حل هذه المشكلة دون تحويل العدد الصحيح إلى سلسلة؟

الحل

اللغة: ج

​
​
bool isPalindrome(int x){
    if (x < 0) {
        return false;
    }
    
    int bak = x;
    
    int tem = 0;
    while (x !=0) {
        tem = 10 *tem + x%10;
        x = x / 10;
    }
    
    if (tem == bak) {
        return true;
    }
    
    return false;
}
​
​

10. مطابقة التعبير العادي

الصعوبة: الصعوبة

إعطاء سلسلة (s) ونمط الأحرف (p). تنفيذ مطابقة التعبير العادي التي تدعم '.' و'*'.

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。

يجب أن يغطي التطابق السلسلة بأكملها (s)، وليس جزءًا منها.

الوصف:

• قد يكون s فارغًا ويحتوي فقط على أحرف صغيرة من a-z.
• قد يكون p فارغًا ويحتوي فقط على أحرف صغيرة من a-z والأحرف . و*.

مثال 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

مثال 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。

مثال 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个('*')任意字符('.')。

مثال 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 'c' 可以不被重复, 'a' 可以被重复一次。因此可以匹配字符串 "aab"。

مثال 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false```


#### الحل

اللغة: **ج**

طريقة 1 مهلة:

```c
​
​
bool isMatch(char * s, char * p){
    if (strlen(p) ==0)
        return strlen(s) == 0;



    if (strlen(p) == 1) {
        return (strlen(s) == 1 && (s[0] == p[0] || p[0] == '.'));
    }
    if (p[1] != '*') {
        if (strlen(s) == 0) return false;
        return (s[0] == p[0] || p[0] == '.') && isMatch(s++, p++);
    }
    while ((strlen(s) != 0) && (s[0] == p[0] || p[0] == '.')) {
        if (isMatch(s, p+2)) return true;
        s = s + 1;
    }
    return isMatch(s, p+2);
}

​
​

الطريقة الثانية:

​
​
bool isMatch(char * s, char * p) {
    if (strlen(p) == 0) return strlen(s) == 0;
    if (strlen(p) > 1 && p[1] == '*') {
        return isMatch(s, p+2) || ((strlen(s) != 0) && (s[0] == p[0] || p[0] == '.') && isMatch(s+1, p));
    } else {
        return (strlen(s) != 0) && (s[0] == p[0] || p[0] == '.') && isMatch(s+1, p+1);
    }
}
​
​

الطريقة الثالثة:

​
​
bool isMatch(char *  s, char *  p) {
    int m = strlen(s), n = strlen(p);

    int **dp = malloc((m + 1) * sizeof(int *));
    for (int i = 0; i < m + 1; i++) {
        int *table = malloc( (n + 1) * sizeof(int));
        dp[i] = table;
    }

    for (int i = 0; i < m + 1; i++) {
        for (int j = 0; j <n + 1; j++) {
            dp[i][j] = false;
        }
    }

    dp[0][0] = true;
    for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (j > 1 && p[j - 1] == '*') {
                dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
            } else {
                dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
            }
        }
    }
    return dp[m][n];
}

​
​

11. الحاوية التي تحتوي على أكبر عدد من النسخ المائية لـ Markdown

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

بالنظر إلى n الأعداد الصحيحة غير السالبة a<sub style=“display: inline;”>1</sub>, a<sub style=“display: inline;”>2, </sub>…, a<sub style=“display: inline;”>n،</sub> يمثل كل رقم نقطة في الإحداثيات (i، a<sub style=“display: مضمنة؛”>i</sub>). ارسم خطوطًا عمودية n ضمن الإحداثيات. نقطتا نهاية الخط العمودي i هما (i، a<sub style=“display: inline;”>i</sub>) و (i, 0). أوجد الخطين بحيث تكون الحاوية التي يشكلانها بالمحور x قادرة على استيعاب أكبر قدر من الماء.

ملاحظة: لا يمكنك إمالة الحاوية وتكون قيمة n على الأقل 2.

<small style=“display: inline;”>تمثل الخطوط الرأسية في الشكل مصفوفة الإدخال [1,8,6,2,5,4,8,3,7]. في هذه الحالة، الحد الأقصى لقيمة الماء (الموضح باللون الأزرق) الذي يمكن أن تحتويه الحاوية هو 49. </small>

مثال:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49```


#### الحل

اللغة: **ج**


الطريقة الأولى هي الأبطأ:

```c
​
​
int maxArea(int* height, int heightSize){
 
    int max = 0;
    for (int i = 0; i < heightSize; i++) {
        int m = height[i];
        for (int j = i+1; j < heightSize; j++) {
            int n = height[j];
            int min =m;
            if (min>n) {
                min = n;
            }
            
            int tmpmax = min * (j - i);
            if (tmpmax > max) {
                max = tmpmax;
            }
        }
    }
    
    return max;
}
​
​

الطريقة 2

​
//376 ms
int maxArea(int* height, int heightSize){
    
    int max = 0;
    int m  = 0;
    for (int i = 0; i < heightSize; i++) {
        if (height[i] > m) {
            m=height[i];
        }
        else{
            continue;
        }
        
        for (int j = i+1; j < heightSize; j++) {
            int n = height[j];
            int min =m;
            if (min>n) {
                min = n;
            }
            
            int tmpmax = min * (j - i);
            if (tmpmax > max) {
                max = tmpmax;
            }
        }
    }
    
    return max;
}

​

الطريقة 3

​执行用时为 4 ms 的范例
int maxArea(int* height, int heightSize) {
    int maxarea=0,left=0,right=heightSize-1;
    int area=0;
    while(left<right)
    {
        if(height[left]<height[right])
        {    area=height[left]*(right-left);
            left++;
            if(area>maxarea)
                maxarea=area;
        }else
        {
            area=height[right]*(right-left);
            right--;
            if(area>maxarea)
                maxarea=area;
        }
    }
    return maxarea;
}


​

الطريقة الرابعة

​执行用时为 8 ms 的范例
int maxArea(int* height, int heightSize)
{
    int min = 0, max = heightSize - 1;
    int area_max = 0;
    while (min < max) {
        int area = (max - min) * (height[min] < height[max] ? height[min] : height[max]);
        area_max = area > area_max ? area : area_max;
        if (height[min] < height[max]) {
            while (++min < max && height[min] <= height[min - 1]) {
                continue;
            }
        } else {
            while (min < --max && height[max] <= height[max + 1]) {
                continue;
            }
        }
    }
    return area_max;
}


​

12. تحويل عدد صحيح إلى رقم روماني

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

تتضمن الأرقام الرومانية الأحرف السبعة التالية: I، وV، وX، وL، وC، وD، وM.

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000```

على سبيل المثال، يتم كتابة الرقم الروماني 2 بالشكل `II`، وهو عبارة عن رقمين متوازيين. 12 مكتوب كـ `XII`، وهو `X` + `II`. يتم كتابة 27 كـ `XXVII`، وهو `XX` + `V` + `II`.

عادةً ما تكون الأرقام الأصغر في الأرقام الرومانية على يمين الأعداد الأكبر. ولكن هناك حالات خاصة. على سبيل المثال، 4 لا يتم كتابته كـ `IIII`، ولكن كـ `IV`. الرقم 1 يقع على يسار الرقم 5 ويمثل رقماً يساوي الرقم الأكبر 5 ناقص الرقم الأصغر 1 للحصول على الرقم 4. وبالمثل، يتم تمثيل الرقم 9 كـ `IX`. تنطبق هذه القاعدة الخاصة فقط على الحالات الستة التالية:

* يمكن وضع `I` على الجانب الأيسر من `V` (5) و`X` (10) لتمثيل 4 و9.
* يمكن وضع `X` على الجانب الأيسر من `L` (50) و`C` (100) لتمثيل 40 و90. 
* يمكن وضع `C` على الجانب الأيسر من `D` (500) و`M` (1000) لتمثيل 400 و900.

إذا كان لديك عدد صحيح، قم بتحويله إلى أرقام رومانية. تأكد من أن الإدخال يقع في النطاق من 1 إلى 3999.

**مثال 1:**

输入: 3 输出: “III”```

مثال 2:

输入: 4
输出: "IV"```

**مثال 3:**

输入: 9 输出: “IX”```

مثال 4:

输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

مثال 5:

输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.```


#### الحل

اللغة: **ج**

```c
​
​
char * intToRoman(int num){
​
}
​
​

مراجعة

نصائح

شارك